¿Hay una función hash "suficientemente buena" para el programador promedio?

Question

Se nos dice que debemos implementar hashCode() para nuestras clases, pero la mayoría de la gente como yo no tiene una idea real de cómo hacer esto o qué pasa si lo hacemos "mal". Por ejemplo, necesito una función hash para indexar nodos en un árbol (Finding the most frequent subtrees in a collection of (parse) trees). En este caso, necesito generar hashcodes recursivamente en base a nodos hijo ordenados, p.

hashCode = function(child1.hashCode, child2.hashCode, ...) 

En un recent discussion de hashcodes respuestas incluyeron un hash para cadenas (basado en una larga Prime y 31) y también bitshifting. The String hash es:

// adapted from String.hashCode() 
public static long hash(String string) { 
    long h = 1125899906842597L; // prime 
    int len = string.length(); 

    for (int i = 0; i < len; i++) { 
    h = 31*h + string.charAt(i); 
    } 
    return h; 
} 

No me interesan las colisiones ni la seguridad. ¿Existe una "función universal" para combinar códigos hash de objetos ordenados que harán más bien que daño (y más bien que no llamarlo en absoluto)?

¿También hay un sitio donde podemos buscar casos comunes? cadenas, listas, etc.)

No especifiqué un idioma, ya que esperaba que hubiera enfoques universales. Pero si es muy específico del idioma, indique el idioma y por qué no es universal.

ACTUALIZACIÓN Dos sugerencias son para utilizar el generador de hashCode del IDE. Eso parece un excelente incumplimiento; Aquí es Netbeans:

public int hashCode() { 
    int hash = 5; 
// objects 
    hash = 97 * hash + (this.rootElement != null ? this.rootElement.hashCode() : 0); 
    hash = 97 * hash + (this.tableElement != null ? this.tableElement.hashCode() : 0); 
// a string 
    hash = 97 * hash + (this.tag != null ? this.tag.hashCode() : 0); 
    return hash; 
} 

Answer 1

Hay un excelente hashCode() en Joshua Bloch's Effective Java. El ejemplo del Capítulo 3, "Métodos comunes a todos los objetos" era gratis (bueno, solía estar de vuelta cuando había una página en el sitio anterior de Sun. Si busca, puede que todavía encuentre una versión en PDF de ese capítulo alrededor algun lado).

También podría ver la fuente para HashCodeBuilder en Apache Commons Lang, pero simplemente no la copie para la clase sin citarla. Es un tiempo bien empleado para realmente aprender sobre esto: te hará una mejor persona.

Answer 2

Si estás en Windows, puede utilizar HashData().

Answer 3

Aunque me falta la etiqueta, supongo que estás hablando de Java.

Una solución "floja" viene con Eclipse 3.5, que generará códigos hash con solo presionar un botón. toString() y equals(), también. ¡Muy agradable! Sospecho que puede encontrar una funcionalidad similar en IDEA y NetBeans.

Aparte de eso, prácticamente cualquier función hash que genere consistentemente el mismo valor para la misma entrada funcionará. Esto (probablemente) solo afectará la eficiencia de cosas como HashMaps.

Answer 4

Si habla de la definición de hashcodes para clases personalizadas, la mejor opción es definir algún tipo de concatenación matemática de todas las funciones de hashcode de sus campos.

Al definir el código hash, su objetivo es normalmente minimizar las colisiones, por lo que si hace algo como esto, normalmente estará libre de errores.

hashcode=(field1.hashcode()*7)+(field2.hashcode()*3)+(field3.hashcode()*51)... 

Answer 5

En cualquier entorno administrado, la implementación sin procesar de una función hash de objetos es la dirección de la memoria en sí.Si no le importan las propiedades de una función hash, cualquier valor servirá, siempre que exista algún tipo de relación de equivalencia entre instancias separadas que representen el mismo valor.

Si está familiarizado con el diseño de bases de datos relacionales, piense en la clave principal de su objeto? ¿Qué valores constituyen la clave principal?

decir que es a, b and c, bueno, entonces su ejecución de código hash se vería así

return a.hashCode()^b.hashCode()^c.hashCode(); 

^es el XOR (O exclusivo) operación bit a bit, de esta manera se pueden encadenar juntos cualquier número de valores para formar un valor hash, y aún mantener un margen decente.

Answer 6

Para responder a su pregunta de qué puede salir mal: el código hash generado por su función se utilizará para encontrar el lugar para las instancias de su clase si lo coloca en una tabla hash (diccionario/mapa). Si tu función de hash genera demasiadas colisiones, el rendimiento de tus hashtables puede ser tan malo como O (n).

Answer 7

Esta es una función que combina código hash que utilizo (en C#):

public static int CombineHashCodes(params int[] hashCodes) 
{ 
    unchecked 
    { 
     var result = 0; 
     foreach (var hash in hashCodes) 
      result = (result * 397)^hash; 
     return result; 
    } 
} 

El razonamiento intuitivo es que el aspecto de combinación es el operador XOR. Así es como .NET 4 lo hace por Tuples:

public static int CombineHashCodes(int h1, int h2) 
{ 
    return ((h1 << 5) + h1)^h2; 
}