sirve - object equals java

hashCode, implementación y relación con HashMap

Question

Así que hice otra pregunta relacionada aquí: función hash de cadena java con efecto de avalancha , pero ahora tengo una pregunta diferente relacionada.

Lo que establecí en esa pregunta fue que la función hashCode () para Cadena no tiene un efecto de avalancha. Esto significa, por ejemplo, que si tengo las cadenas "k1", "k2", "k3" y llamo hashCode () en cada uno, los valores devueltos serán contiguos.

Ahora, en base a mi recuerdo de las estructuras de datos 101, tenía la impresión de que esto es algo malo. Porque suponiendo que HashMap elija cubos por un algoritmo, algo así como:

class HashMap {
    private int capacity;
    private int chooseBucket(String key) {
        return key.hashCode() % capacity;
    }
}

Significaría que claves similares se almacenan en cubos contiguos, lo que lleva a una mayor tasa de colisiones, degradando el tiempo de búsqueda de O grande de O (1) para ser ... quién sabe qué tan mal ... quizás sea peor que O (log n )

Los tipos de respuestas que obtuve a mi primera pregunta fueron como ''no se necesita el efecto de avalancha aquí'', ''es solo para funciones de hash de criptografía'' y ''la implementación de hashCode para cadenas es rápida y funciona bien para pequeños mapas hash ''.

Lo cual me confunde. Todas las estructuras de datos son rápidas cuando son pequeñas. ¿Sun no proporcionaría una función predeterminada de código hash que funcionaría bien para grandes conjuntos de datos? Ahí es cuando el rendimiento de HashMap realmente importa de todos modos, ¿no?

¿O me estoy perdiendo algo? Por favor iluminame.

Answer 1

Almacenar claves en depósitos contiguos no causa degradación del rendimiento. Almacenar claves en el mismo cubo (por ejemplo, encadenamiento ) sí lo hace. Cuando se utiliza el encadenamiento para resolver colisiones hash:

• En el peor de los casos, cada valor de hash es el mismo, por lo que todos los elementos terminan en el mismo contenedor, en cuyo caso obtiene un rendimiento de O (n) (suponiendo que las cadenas son listas enlazadas)
• El mejor de los casos: cada valor de hash es diferente, por lo que cada elemento termina en un cubo diferente, por lo que se obtiene el rendimiento de O (1) esperado.

Los códigos Hash para usar en tablas hash (y similares) no necesitan un efecto de avalancha .

Answer 2

Leí una entrada de blog de Eric Lippert el otro día titulada Pautas y reglas para GetHashCode . Aunque los ejemplos de código son relevantes para C #, la mayoría de los principios generales se aplican igualmente bien a Java. Vale la pena leer este artículo si quiere saber más sobre para qué se utilizan los códigos hash y cómo se deben generar.

En particular, el siguiente bit parece particularmente relevante para su pregunta:

Pauta: la distribución de códigos hash debe ser "aleatoria"

Por una "distribución aleatoria" me refiero a que si hay aspectos comunes en los objetos que se procesan, no debería haber similitudes similares en los códigos hash producidos.

Answer 3

Si observa el código fuente de HashMap, se llama a la función hash con el valor key.hashCode (), lo que significa que realiza su propia forma de asignar un hash. Un punto del que debes estar seguro es no obedecer el contrato de igual y código hash. Sugeriría que, si está buscando una mejora en el rendimiento, examine el código fuente y comprenda la cantidad de cubetas disponibles y el uso óptimo de la misma.

Answer 4

Una función de hash para algo así como un HashMap debe ser razonablemente única para su conjunto de claves, pero la relación entre las claves (es decir, cómo se combinan dos teclas) no tiene que ser aleatoria. Lo que realmente queremos evitar es un grupo de objetos en un solo cubo que haría que la búsqueda de ese cubo sea costosa.

En el caso de HashMaps y Strings tiene que asignar esas claves hash en algún tipo de desplazamiento a un contenedor accesible al azar, como una matriz para la que hay una serie de soluciones, pero si dos teclas están "cerradas", todavía dará como resultado que sean colocado en diferentes cubos, que es todo lo que realmente nos importa.

Para contenedores de mapas muy grandes (piense en miles de millones de claves) probablemente querremos ser un poco más listos, pero eso parece más allá de lo que se diseñó para HashMap de Java.

Una nota final: no tiene que usar el efecto de avalancha para producir claves bastante aleatorias para Cadenas. Desea elegir una función lo suficientemente aleatoria y rápida como sea posible.

Answer 5

Usted preguntó "O, ¿me estoy perdiendo algo? Por favor, ilumíname".

Sí, te estás olvidando de algo.

Dentro de la implementación de la clase HashMap, protege contra funciones de hash deficientes:

/**
 * Applies a supplemental hash function to a given hashCode, which
 * defends against poor quality hash functions.  This is critical
 * because HashMap uses power-of-two length hash tables, that
 * otherwise encounter collisions for hashCodes that do not differ
 * in lower bits. Note: Null keys always map to hash 0, thus index 0.
 */
static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

Entonces, los hashcodes resultantes en su ejemplo son:

k1 - Before: 3366 After: 3566
k2 - Before: 3367 After: 3567
k3 - Before: 3368 After: 3552

Entonces, incluso en su pequeño tamaño de muestra de 3 elementos, uno de ellos obtuvo un nuevo refrito. Ahora, esto no protege contra hashCodes agresivamente malvados ( return randomInt(); o return 4; simplemente no se puede proteger contra) pero guarda contra códigos return randomInt(); mal escritos .

También debo señalar que puede cambiar las cosas mucho al usar entradas no triviales. Considere por ejemplo las siguientes cadenas.

k1longer - Before: 1237990607 After: 1304548342
k2longer - Before: 2125494288 After: 2040627866
k3longer - Before: -1281969327 After: -1178377711

Observe qué tan diferentes son los bits más bajos: esos son los únicos elementos importantes para un hashcode son los bits más bajos. El tamaño del mapa de respaldo siempre es una potencia de dos. De hecho, está documentado de esa manera en el código:

/**
 * The table, resized as necessary. Length MUST Always be a power of two.
 */
transient Entry[] table;

El reajuste hace un trabajo bastante decente para asegurarse de que los bits superiores (que normalmente se ignoran en la tabla hash) todavía tienen un impacto en los bits inferiores. Aquí está el mapeo de las posiciones originales de hashcode y los bits que afectan:

00: 00000000000000000000000000000001
01: 00000000000000000000000000000010
02: 00000000000000000000000000000100
03: 00000000000000000000000000001000
04: 00000000000000000000000000010001
05: 00000000000000000000000000100010
06: 00000000000000000000000001000100
07: 00000000000000000000000010001001
08: 00000000000000000000000100010010
09: 00000000000000000000001000100100
10: 00000000000000000000010001001000
11: 00000000000000000000100010010000
12: 00000000000000000001000100100001
13: 00000000000000000010001001000010
14: 00000000000000000100010010000100
15: 00000000000000001000100100001000
16: 00000000000000010001001000010001
17: 00000000000000100010010000100010
18: 00000000000001000100100001000100
19: 00000000000010001001000010001001
20: 00000000000100010010000100010011
21: 00000000001000100100001000100110
22: 00000000010001001000010001001100
23: 00000000100010010000100010011000 # means a 1 in the 23rd bit position will  
24: 00000001000100100001000100110001  # cause positions 4, 5, 8, 12, and 20 to 
25: 00000010001001000010001001100010  # also be altered
26: 00000100010010000100010011000100
27: 00001000100100001000100110001001
28: 00010001001000010001001100010010
29: 00100010010000100010011000100100
30: 01000100100001000100110001001000
31: 10001001000010001001100010010000

Por lo tanto, su preocupación acerca de "degradar el tiempo de búsqueda de O grande de O (1) es ... quién sabe qué tan mal ... quizás sea peor que O (log n)" y "¿Sun no proporcionaría una función predeterminada de código hash que funcionará bien para grandes conjuntos de datos? " se pueden dejar de lado; tienen medidas de seguridad para evitar que eso suceda.

Si te ayuda a obtener un poco de paz, aquí están las etiquetas de autor para esta clase. Literalmente son todas estrellas en el mundo de Java. (los comentarios con # son míos)

 * @author  Doug Lea          # Formerly a Java Community Process Executive Committee member
 * @author  Josh Bloch        # Chief Java architect at Google, amongst other things
 * @author  Arthur van Hoff   # Done too many hardcore Java things to list...
 * @author  Neal Gafter       # Now a lead on the C# team at Microsoft, used to be team lead on javac