Explicación de las constantes utilizadas al calcular el valor de hashcode de java.util.hash

Question

¿Puede alguien explicar el significado de estas constantes y por qué se eligen?

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); 
    } 

fuente: Biblioteca de Java-SE6

Answer 1

También he preguntado acerca de tales números "mágicos". Por lo que yo sé, son números mágicos.
Se ha demostrado mediante pruebas exhaustivas que los números impares y primos tienen prioridades interesantes que podrían usarse en el hashing (evite el agrupamiento primario/secundario, etc.).
Creo que la mayoría de los números vienen después de la investigación y las pruebas que prueban estadísticamente dar buenas distribuciones. ¿Por específicamente estos números de hacer eso, no tengo ni idea, pero tengo la impresión (esperemos colegas aquí me puede corregir si estoy lejos) ni los ejecutores saben por qué estos específicos números presentan estas cualidades

Answer 2

la comprensión de lo hace una buena función de hash es complicado, ya que de hecho hay muchas funciones diferentes que se utilizan y con fines ligeramente diferentes.

tablas hash de Java funcionan de la siguiente manera:

1. piden al objeto clave para producir su código hash. Es probable que la implementación del método hashCode() sea de calidad claramente variable (en el peor de los casos, devuelva un valor constante) y definitivamente no se adaptará a la tabla hash concreta con la que está trabajando.
2. Luego utilizan la función anterior para mezclar los bits un poco, de modo que la información presente en los bits altos también se mueve hacia abajo a los bits bajos. Esto es importante porque el siguiente ...
3. Toman el mod del código hash (w.r.t. el número de entradas de matriz de tabla hash) para obtener el índice en la matriz de cadenas de tablas hash. Existe una clara posibilidad de que la matriz de tabla hash tenga un tamaño equivalente a una potencia de 2, por lo que la mezcla de los bits en el paso 2 es importante para garantizar que no se descarten.
4. Luego recorren la cadena hasta que llegan a la entrada con una tecla igual (de acuerdo con el método equals()).

Para completar la imagen, el número de entradas en el conjunto de tablas hash no es constante; si las cadenas son demasiado largas, la matriz se reemplaza con una nueva matriz más grande y todo se vuelve a procesar. Eso es relativamente rápido y tiene buenas implicaciones de rendimiento para los patrones de uso normal (por ejemplo, lotes de put() seguidos de lotes de get() s).

Las constantes reales que se utilizan son bastante arbitraria (y probablemente son elegidos por experimentar con algunos simples corpus incluyendo cosas como un gran número de Integer y String valores), pero su propósito no es: recibir la información en todo el valor se extendió a la mayoría de los bits bajos en el valor aseguran que la información que está presente en la salida del hashCode() se usa lo mejor posible.

(No haría esto con hashing perfecto o hash criptográfico; a pesar de los nombres similares, tienen estrategias de implementación muy diferentes. El primero requiere conocimiento del espacio clave para evitar/reducir las colisiones, y el segundo necesita información que debe moverse en todas las direcciones, no solo en los bits bajos.)