Comprensione della strana funzione di hash Java

Question

Di seguito è riportato il codice sorgente per una funzione hash in java.util.HashMap. I commenti spiegano abbastanza bene cosa sta portando a compimento. ma come? Cosa fanno gli operatori ^ e >>>? Qualcuno può spiegare come effettivamente il codice fa cosa dicono i ?

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

Answer 1

Boh' su inglese, ma qui è un codice e l'output di esempio:

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

che stampa:

11111111111111111111111111111111 
00000000000000000000111111111111 
00000000000011111111111111111111 
00000000000011111111000000000000 
11111111111100000000111111111111 
00000001111111111110000000011111 
00001111111111110000000011111111 
00001110000000001110000011100000 
11110001111100001110111100011111 

Quindi, il codice si rompe la funzione di hash in fasi in modo da può vedere cosa sta succedendo. Il primo spostamento di 20 posizioni xo con il secondo turno di 12 posizioni crea una maschera che può capovolgere 0 o più dei 20 bit inferiori dell'int. In questo modo è possibile inserire un po 'di casualità nei bit in basso che fa uso dei bit superiori potenzialmente meglio distribuiti. Questo viene quindi applicato via xor al valore originale per aggiungere quella casualità ai bit più bassi.Il secondo spostamento di 7 posizioni xo lo spostamento di 4 posizioni crea una maschera che può capovolgere 0 o più dei 28 bit inferiori, il che porta di nuovo un po 'di casualità ai bit inferiori e ad alcuni dei più significativi capitalizzando il precedente xor che ha già affrontato parte della distribuzione ai bit più bassi. Il risultato finale è una distribuzione più fluida dei bit attraverso il valore hash.

Poiché l'hashmap in java calcola l'indice del bucket combinando l'hash con il numero di bucket, è necessario disporre di una distribuzione uniforme dei bit inferiori del valore hash per distribuire uniformemente le voci in ciascun bucket.

Come per dimostrare la dichiarazione che questo limita il numero di collisioni, su cui non ho alcun input. Inoltre, vedere here per alcune buone informazioni sulla creazione di funzioni hash e alcuni dettagli sul perché l'xor di due numeri tende alla distribuzione casuale di bit nel risultato.

Answer 2

>>> è un Bitshift con riempimento pari a zero.

^ è un XOR.

XOR viene anche chiamato esclusivo o - è un operatore matematico che combina due numeri. Vedi http://en.wikipedia.org/wiki/Exclusive_or

Un bithift di destra di n equivale a eliminare i bit più bassi del numero n. Quindi se il numero è 00010111 e lo hai spostato a destra di 1, riceverai 00001011.

Answer 3

^ è bitwise XOR, >>> è bit shift.

Answer 4

>>> sembra essere un senza segno spostamento a destra bit a bit, e ^ è XOR bit a bit

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

Answer 5

Si tratta di una combinazione di bit esclusivo e senza segno spostamento a destra.

Vedi qui per maggiori spiegazioni: http://www.roseindia.net/java/master-java/bitwise-bitshift-operators.shtml

Answer 6

Ecco un article that discusses integer hash functions e alcune delle considerazioni a cui sono stati progettati. Non è molto dettagliato, ma il punto principale è questo:

le operazioni devono utilizzare una catena di calcoli per ottenere valanghe. Avalanche significa che un singolo bit di differenza nell'ingresso renderà circa 1/2 dei bit di uscita diversi.

Fondamentalmente, l'obiettivo è la funzione di hash supplementare per rimuovere le regolarità nell'input, poiché queste potrebbero causare la degenerazione della tabella hash.