¿Cómo debería definir una buena hashCode para una lista enlazada circular en Java?

Question

Me han creado una estructura de datos de lista vinculada circular que representa una palabra, y cada elemento de la lista es una letra de la palabra. En la parte inferior de mi pregunta son las definiciones de clase de la lista y los elementos de la lista.

El propósito de la estructura de la lista de datos es ser capaz de comparar palabras cíclicos. Así que ... "foto" y "turepic" son la misma palabra cíclico, por lo que las dos listas serán iguales.

Así que equals() anulación cuando se comparan dos listas, y he leído que cada vez que tiene que anular equals(), usted tiene que anular también hashCode(). Sin embargo, realmente no tengo una buena idea de cómo hacerlo.

¿Cómo debería definir una buena hashCode por lo que he levantado? ¿Qué cosas debo tener en cuenta? En el ejemplo de la "imagen" y "turepic", las dos listas son iguales por lo que su hashCode necesita ser el mismo. Algunas ideas?

Gracias, Hristo

public class Letter {
 char value;
 Letter theNextNode;

 /**
  * Default constructor for an element of the list.
  * 
  * @param theCharacter - the value for this node.
  */
 Letter(char theCharacter) {
  this.value = theCharacter;
 }
}


public class CircularWord {

 /*
  * Class Variables
  */
 Letter head;
 Letter tail;
 Letter theCurrentNode;

 int iNumberOfElements;


 /**
  * Default Constructor. All characters that make up 'theWord' are stored in a 
  * circular linked list structure where the tail's NEXT is the head. 
  */
 public CircularWord(String theWord) {

  char[] theCharacters = theWord.toCharArray();

  for (int iIndex = 0; iIndex < theCharacters.length; iIndex++) {
   this.addElement(theCharacters[iIndex]);
  }

  this.theCurrentNode = head;
  this.iNumberOfElements = theCharacters.length;
 }
}

Answer 1

¿Qué tal la suma de los hashcodes de todos los elementos dentro de su lista, cada uno multiplicado por un valor arbitrario?

Algo así como

hashCode = 1;
for (char c : myChars) {
    hashCode += 31 * c;
}

Answer 2

Así que quieres un cálculo código hash que da resultados iguales para "foto" y "turepic", pero (preferentemente) diferente del código hash de ejemplo "Eruptic". Así, no es suficiente simplemente sumar los hashcodes de las letras contenidas en la palabra - es necesario tener alguna información de posición también, pero aún así, debe ser independiente de la permutación real de la palabra. Es necesario definir las "clases de equivalencia", y calcular siempre el mismo código hash para cada miembro de la clase.

La forma más sencilla de lograr esto es a seleccionar un miembro específico de la clase de equivalencia y siempre utilizar el código hash de esa variación para todas las palabras equivalentes . P.ej. seleccione la primera variante alfabéticamente (gracias @ Michael para resumirlo de forma concisa). Por "foto" et al., Que sería "cturepi". Tanto "foto" y "turepic" (y todas las demás variaciones equivalentes) deben devolver el código hash de "cturepi". Ese código hash podría calcularse por el método LinkedList estándar, o cualquier otra forma preferida.

Se podría decir que este cálculo es muy caro. Es cierto, sin embargo, se podría almacenar en caché el resultado, por lo que sólo el primer cálculo sería costoso. Y supongo que la selección de la primera variante alfabético podría ser optimizado bastante tanto en el caso común (en comparación con la solución trivial de generar todas las permutaciones en la clase de equivalencia específica, a continuación, los clasifica y recoger la primera).

por ejemplo. en muchas de las palabras, la primera letra alfabéticamente es único ( "foto" es uno de ellos - la primera letra alfabéticamente es 'c', y sólo hay una 'c' en ella). Por lo que sólo necesita encontrar que, a continuación, calcular el código hash a partir de ahí. Si no es única, es necesario comparar el segundo, tercero, etc. letras después de eso, hasta que encuentre una diferencia (o uno se voltea).

Actualizar - 2 ejemplos

• "abracadabra" contiene 5 Aes. La 2da caracteres después de la 'a son 'b', 'c', 'd', 'b' y 'a', respectivamente. Así, en la segunda ronda de la comparación se puede concluir que la variación más pequeña es lexicográfico "aabracadabr".
• "ABAB" contiene un 2' de, y una 'b' después de cada (y luego uno se voltea, alcanzando una 'A' de nuevo, por lo que los extremos de misiones allí). Así que hay dos idénticos lexicográfico variaciones más pequeñas de la misma. Pero ya que son idénticos, es obvio que producen el mismo código hash.

Actualización: Al final, todo se reduce a cuánto es lo que realmente necesita el código hash - es decir, usted planea poner sus listas circulares en una colección asociativo como Set o Map. Si no es así, se puede hacer con un simple, o incluso el método de hash trivial. Pero si se utiliza alguna colección asociativo en gran medida, una aplicación de hash triviales le da un montón de colisiones así el rendimiento subóptimo. En este caso, vale la pena intentarlo implementación de este método hash y medir si se paga por sí mismo en el rendimiento.

Actualización 3: código de ejemplo

Letter se dejó básicamente el mismo que el anterior, sólo hice la private campos, rebautizado theNextNode a next, y ha añadido getters / setters, según sea necesario.

En CircularWord he hecho algunos cambios más: tail caído y theCurrentNode, e hizo circular la palabra de verdad (es decir last.next == head). El constructor, toString y equals no son relevantes para calcular el código hash, por lo que se omiten por razones de simplicidad.

public class CircularWord {
    private final Letter head;
    private final int numberOfElements;

    // constructor, toString(), equals() omitted

    @Override
    public int hashCode() {
        return hashCodeStartingFrom(getStartOfSmallestRotation());
    }

    private Letter getStartOfSmallestRotation() {
        if (head == null) {
            return null;
        }
        Set<Letter> candidates = allLetters();
        int counter = numberOfElements;

        while (candidates.size() > 1 && counter > 0) {
            candidates = selectSmallestSuccessors(candidates);
            counter--;
        }
        return rollOverToStart(counter, candidates.iterator().next());
    }

    private Set<Letter> allLetters() {
        Set<Letter> letters = new LinkedHashSet<Letter>();
        Letter letter = head;

        for (int i = 0; i < numberOfElements; i++) {
            letters.add(letter);
            letter = letter.getNext();
        }
        return letters;
    }

    private Set<Letter> selectSmallestSuccessors(Set<Letter> candidates) {
        Set<Letter> smallestSuccessors = new LinkedHashSet<Letter>();

        char min = Character.MAX_VALUE;
        for (Letter letter : candidates) {
            Letter nextLetter = letter.getNext();
            if (nextLetter.getValue() < min) {
                min = nextLetter.getValue();
                smallestSuccessors.clear();
            }
            if (nextLetter.getValue() == min) {
                smallestSuccessors.add(nextLetter);
            }
        }
        return smallestSuccessors;
    }

    private Letter rollOverToStart(int counter, Letter lastCandidate) {
        for (; counter >= 0; counter--) {
            lastCandidate = lastCandidate.getNext();
        }
        return lastCandidate;
    }

    private int hashCodeStartingFrom(Letter startFrom) {
        int hash = 0;
        Letter letter = startFrom;
        for (int i = 0; i < numberOfElements; i++) {
            hash = 31 * hash + letter.getValue();
            letter = letter.getNext();
        }
        return hash;
    }

}

El algoritmo implementado en getStartOfSmallestRotation para encontrar el orden lexicográfico más pequeña rotación de la palabra es básicamente lo que describo arriba: comparar y seleccionar el orden lexicográfico más pequeño primero, segundo, tercero, etc. letras de cada rotación, dejando caer las letras mayores hasta que o bien hay solo candidato a la izquierda, o rodar sobre la palabra. Dado que la lista es circular, lo usoun contador para evitar un bucle infinito.

Al final, si tengo un solo candidato a la izquierda, puede estar en el medio de la palabra y que necesita para obtener el inicio de la rotación más pequeña palabra. Sin embargo, como esta es una lista simplemente enlazada, es incómodo de hacia atrás paso a paso en él. Por suerte, el contador bien me ayuda: se ha registrado el número de cartas que he comparado hasta ahora, pero en una lista circular, esto es equivalente a la cantidad de cartas que se puede mover hacia delante antes de volcarse. Así que sé cuántas cartas para seguir adelante con el fin de obtener de nuevo para el inicio de la rotación mínima palabra de lo que estoy buscando.

Espero que esto ayude a alguien - al menos fue divertido de escribir: -)

Answer 3

es lo que realmente necesita para utilizar su hashcodes? Si no tiene la intención de colocar los miembros de objetos de cualquier tipo de estructura de hash, se puede simplemente ignorar el problema:

public int hashCode() {
    return 5;
}

Esto satisface los requisitos que la igualdad de los casos tienen códigos hash iguales. A menos que yo sabía que tenía una mejor distribución de hash, esto probablemente podría funcionar bastante bien para mis propias necesidades.

Pero yo creo que tengo una idea que da una mejor distribución de los hashes. pseudo código:

hash = 0
for each rotation
    hash += hash(permutation)
end
hash %= MAX_HASH

Desde almohadilla () es probable que sea O (n), entonces este algoritmo es O (n ^ 2), que es un poco lento, pero hashes reflejan el método utilizado para las pruebas de equivalencia, la distribución de códigos hash es probablemente bastante decente. cualquier otro kernel (prod, xor) que es un trabajo voluntad conmutativa, así como la suma utilizado en este ejemplo.

Answer 4

int hashcode() {
    int hash = 0;
    for (c in list) {
        hash += c * c;
    }
    return hash;
}

Desde + es conmutativo, igualdad de palabras tengan igual hashcodes. El código hash no es muy discriminando (todas las permutaciones de letras reciben el mismo código hash), pero debe hacer el truco a menos que por lo general pone muchas permutaciones en el HashSet.

Nota: añado c * c en lugar de simplemente c el fin de obtener menos colisiones de letras distintas

.

Nota 2: La desigualdad de las listas con los códigos iguales de hash hacer no violan del contrato de código hash. Tales "colisiones" debe ser evitado, ya que reducen el rendimiento, pero no amenazan la corrección del programa. En general, las colisiones pueden no pueden evitar, aunque es ciertamente posible para evitarlos más que en mi respuesta, pero al hacerlo hace que el código hash más caros de cómputo, lo que podría más de comer cualquier ganancia de rendimiento.

Answer 5

1. definir equals() y hashCode() para Letter. Para ello, utilice solamente el campo char.
2. Para CircularWord, implementar hashCode() iterando de head a tail XOR'ing los valores respectivos de Letter.hashCode. Finalmente el resultado XOR con alguna constante.

---

Otra forma sería la de canonicalize las palabras Cicular, representándolos como algo parecido a:

public class CircularWord {

    private static Set<String> canonicalWords = new HashSet<String>();
    private String canonicalWord;
    private int offset;

    public CircularWord(String word) {
        // Looks for an equal cirular word in the set (according to our definition)
        // If found, set canonicalWord to it and calculate the offset.
        // If not found, put the word in the set, set canonical word to our argument and set offset to 0.
    }
    // Implementation of CircularWord methods using
    // canonicalWord and offset
}

A continuación, implementaría equals() y hashCode(), delegando en las implementaciones String.

Answer 6

Me leído mal su pregunta - Pensé que querías diferentes haschodes para "foto" y "turepic"; Creo que en este caso, se puede obtener una pista del hecho de que dos objetos que son iguales deben tener el mismo código hash, sino dos objetos que tienen el mismo código hash pueden no ser necesariamente iguales.

Así que usted puede utilizar la solución de Vivien que garantice que "foto" y "turepic" tendrá el mismo código hash. Sin embargo, esto también significa que "foto" y "pitcure" tendrían los mismos códigos hash también. En este caso, el método de equals tendrá que ser más inteligentes y tendrá que averiguar si los dos lista de letras representan en realidad la misma palabra. Esencialmente el método equals ayuda a resolver la colisión que se puede obtener de "imagen" / "turepic" y "pitcure".

Answer 7

Tenga en cuenta que hashcodes no son únicos. Dos objetos diferentes pueden hash en exactamente el mismo valor. Así código hash es insuficiente para determinar la igualdad; que tiene que hacer la comparación real de los iguales (). [COMENTARIO ESPECULATIVAS REMOVIDA. OMG]

código hash () simplemente puede devolver una constante en todos los casos. Esto puede afectar al rendimiento, pero es totalmente válida. Una vez que obtenga todo lo demás hecho, se puede trabajar en un código hash más eficiente () algoritmo.

Este es un buen artículo . Tenga en cuenta la sección 'perezosa código hash'.