Die seltsame Java-Hash-function verstehen

Im Folgenden finden Sie den Quellcode für eine Hash-function in java.util.HashMap . Die Kommentare erklären gut genug, was es bewirkt. aber wie? Was machen die Operatoren ^ und >>> ? Kann jemand erklären, wie der Code tatsächlich funktioniert, was die Kommentare sagen ?

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

   

Dunno ‘über Englisch, aber hier ist ein bisschen Code und die Beispielausgabe:

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

Welche Drucke:

 11111111111111111111111111111111 00000000000000000000111111111111 00000000000011111111111111111111 00000000000011111111000000000000 11111111111100000000111111111111 00000001111111111110000000011111 00001111111111110000000011111111 00001110000000001110000011100000 11110001111100001110111100011111 

Der Code teilt also die Hash-function in Schritte auf, so dass Sie sehen können, was passiert. Die erste Verschiebung von 20 Positionen xor mit der zweiten Verschiebung von 12 Positionen erzeugt eine Maske, die 0 oder mehr der unteren 20 Bits von int invertieren kann. Sie können also eine gewisse Zufälligkeit in die unteren Bits einfügen, die von den potenziell besser verteilten höheren Bits Gebrauch macht. Dies wird dann über xor auf den ursprünglichen Wert angewendet, um diese Zufälligkeit zu den unteren Bits hinzuzufügen. Die zweite Verschiebung von 7 Positionen x oder die Verschiebung von 4 Positionen erzeugt eine Maske, die 0 oder mehr der unteren 28 Bits umkehren kann, was wiederum eine gewisse Zufälligkeit zu den unteren Bits und zu einigen der signifikanteren bringt, indem das vorherige xor groß geschrieben wird die bereits einige der Verteilung an den unteren Bits adressiert. Das Endergebnis ist eine gleichmäßigere Verteilung von Bits durch den Hash-Wert.

Da die Hashmap in Java den Bucket-Index berechnet, indem Sie den Hash mit der Anzahl der Buckets kombinieren, müssen Sie die unteren Bits des Hash-Werts gleichmäßig verteilen, um die Einträge gleichmäßig in jeden Bucket zu verteilen.

Zum Beweis der Aussage, dass dies die Anzahl der Kollisionen begrenzt, habe ich keine Eingabe. Sehen Sie hier auch einige gute Informationen zum Aufbau von Hash-functionen und ein paar Details darüber, warum der xor zweier Zahlen zur zufälligen Verteilung von Bits im Ergebnis neigt.

>>> ist ein Bitshift mit Nullfüllung.

^ ist ein XOR.

XOR wird auch exklusiv oder – es ist ein mathematischer Operator, der zwei Zahlen kombiniert. Siehe http://en.wikipedia.org/wiki/Exclusive_or

Ein Rechtsbitshift um n ist wie das Abfallen der n niedrigsten Bits von der Zahl. Wenn also die Zahl 00010111 und Sie sie um 1 nach rechts verschieben, erhalten Sie 00001011 .

Hier ist ein Artikel, der Integer-Hash-functionen und einige der Überlegungen, auf die sie ausgelegt sind , diskutiert . Es ist nicht sehr detailliert, aber der wichtigste Punkt ist:

Die Operationen müssen eine Kette von Berechnungen verwenden, um Lawine zu erreichen. Avalanche bedeutet, dass ein einzelnes Bit der Differenz in der Eingabe dazu führt, dass etwa die Hälfte der Ausgangsbits unterschiedlich ist.

Im Grunde ist es das Ziel der zusätzlichen Hash-function, alle Regelmäßigkeiten in der Eingabe zu entfernen, da diese dazu führen können, dass die Hash-Tabelle degeneriert.

^ ist bitweise XOR , >>> ist bit shift .

>>> scheint eine vorzeichenlose rechte bitweise Verschiebung zu sein, und ^ ist bitweise XOR

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

Es ist eine Kombination aus bitweisem Exklusiv-ODER und vorzeichenloser Rechtsverschiebung.

Sehen Sie hier für mehr Erklärung: http://www.roseindia.net/java/master-java/bitwise-bitshift-operators.shtml