Comprender la extraña función hash de Java

A continuación se muestra el código fuente de una función hash en java.util.HashMap . Los comentarios explican bastante bien lo que está logrando. ¿pero cómo? ¿Qué están haciendo los operadores ^ y >>> ? ¿Alguien puede explicar cómo el código realmente hace lo que dicen los comentarios?

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

No sé nada de inglés, pero aquí hay un código y la salida de muestra:

 public static void main ( String[] args ) { int h = 0xffffffff; int h1 = h >>> 20; int h2 = h >>> 12; int h3 = h1 ^ h2; int h4 = h ^ h3; int h5 = h4 >>> 7; int h6 = h4 >>> 4; int h7 = h5 ^ h6; int h8 = h4 ^ h7; printBin ( h ); printBin ( h1 ); printBin ( h2 ); printBin ( h3 ); printBin ( h4 ); printBin ( h5 ); printBin ( h6 ); printBin ( h7 ); printBin ( h8 ); } static void printBin ( int h ) { System.out.println ( String.format ( "%32s", Integer.toBinaryString ( h ) ).replace ( ' ', '0' ) ); } 

Que impresiones:

 11111111111111111111111111111111 00000000000000000000111111111111 00000000000011111111111111111111 00000000000011111111000000000000 11111111111100000000111111111111 00000001111111111110000000011111 00001111111111110000000011111111 00001110000000001110000011100000 11110001111100001110111100011111 

Entonces, el código descompone la función hash en pasos para que pueda ver lo que está sucediendo. El primer cambio de 20 posiciones xor con el segundo cambio de 12 posiciones crea una máscara que puede voltear 0 o más de los 20 bits inferiores de la int. De modo que puede obtener algo de aleatoriedad insertada en los bits inferiores que hace uso de los bits superiores potencialmente mejor distribuidos. Esto se aplica a través de xor al valor original para agregar esa aleatoriedad a los bits más bajos. El segundo cambio de 7 posiciones xo el cambio de 4 posiciones crea una máscara que puede voltear 0 o más de los 28 bits inferiores, lo que trae algo de aleatoriedad nuevamente a los bits más bajos y a algunos de los más significativos capitalizando el anterior xor que ya abordaba parte de la distribución en los bits inferiores. El resultado final es una distribución más suave de bits a través del valor hash.

Como el hashmap en java calcula el índice del cubo al combinar el hash con el número de cubos, necesita tener una distribución pareja de los bits más bajos del valor del hash para distribuir las entradas de manera uniforme en cada cubo.

En cuanto a probar la afirmación de que esto limita el número de colisiones, no tengo ninguna entrada en esa. Además, consulte aquí para obtener una buena información sobre la construcción de funciones hash y algunos detalles sobre por qué el xor de dos números tiende a la distribución aleatoria de bits en el resultado.

>>> es un cambio de bits con cero relleno.

^ es un XOR.

XOR también se llama exclusivo o – es un operador matemático que combina dos números. Ver http://en.wikipedia.org/wiki/Exclusive_or

Un cambio de bits a la derecha por n es como soltar los n bits más bajos del número. Entonces, si el número es 00010111 , y lo 00010111 a la derecha por 1, obtendrías 00001011 .

Aquí hay un artículo que analiza las funciones hash enteras y algunas de las consideraciones para las que están diseñadas. No es muy detallado, pero el punto principal es este:

las operaciones deben usar una cadena de cálculos para lograr la avalancha. Avalancha significa que un solo bit de diferencia en la entrada hará que aproximadamente 1/2 de los bits de salida sea diferente.

Básicamente, el objective es que la función hash suplementaria elimine cualquier regularidad en la entrada, ya que podría hacer que la tabla hash se degenere.

^ es a nivel de bit XOR , >>> es bit shift .

>>> parece ser un desplazamiento a la derecha sin signo, y ^ es a nivel de bit XOR

http://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html

Es una combinación de O exclusiva en modo bit y desplazamiento a la derecha sin signo.

Consulte aquí para obtener más información: http://www.roseindia.net/java/master-java/bitwise-bitshift-operators.shtml