Quale proprietà del pattern di bit è quella che causa collisioni?

Question

Stavo leggendo sull'approccio di Java per randomizzare le chiavi di hash here
Apparentemente l'idea è di assicurarsi che i bit inferiori siano "casuali" per aiutare la distribuzione ma sto cercando di capirlo di più.
Quindi se abbiamo una tabella di dimensione 10 allora i numeri 0,10,20,30,40 ecc cadono tutti nel secchio 0, i numeri 1,11,21,31 ecc cadono nel secchio 1 ecc. (Usando il modulo 10) .
Quindi, cambiando i pattern di bit, potresti farli andare su diversi bucket invece di passare al bucket 0.
Ma quello di cui non sono chiaro è quale sia la proprietà che fa in modo che i bit di ordine basso influiscano su questo e dobbiamo randomizzare loro. Quindi abbiamo:

0000 0000 (0) 
0000 1010 (10) 
0001 0100 (20) 
0001 1110 (30) 
0010 1000 (40) 

Qual è la regolarità nei bit di ordine basso che li rende posizione per lo stesso slot?
Forse sono confuso su quanto segue? La mia comprensione è che è un po 'di regolarità nei bit di basso ordine che causano collisioni e proviamo a randomizzare bit per compensare

Answer 1

Alcune funzioni di hash fanno un lavoro davvero brutto di randomizzazione di bit di basso ordine.

Un caso classico è l'uso di indirizzi hardware come hash per riferimenti oggetto ("puntatori" in C), che altrimenti sarebbe un modo ragionevole di ottenere a buon mercato un numero univoco per un ID oggetto. Funzionerebbe bene se il numero di bucket della tabella hash fosse un numero primo, ma per le implementazioni hash in cui il numero di bucket è sempre una potenza di 2, il fatto che tutti gli hash siano divisibili per 8 significherebbe che la maggior parte dei bucket erano vuoti.

Questo è un caso estremo, ma ogni volta che i dati da sottoporre a hash non sono distribuiti uniformemente e la funzione di hash tende a preservare i bit di ordine inferiore, si troverà qualche errore nelle assegnazioni del bucket.

Answer 2

Java HashMap utilizza una tabella hash di due potenze. Se si usa normalmente l'operazione resto/modulo come funzione di compressione, si finisce col prendere i bit più bassi del codice hash come indice del bucket. Se i codici hash sono multipli di una potenza due, alcuni dei bit più bassi saranno sempre zero e si finirà per utilizzare una frazione dei bucket disponibili.

Esempio concreto: si supponga di disporre di 32 bucket e di codici hash multipli di 8. La tabella utilizza solo i 5 bit meno significativi del codice e 3 di questi sono sempre 0. Pertanto, solo 2 bit determinano il bucket, e si usa solo 4 dei 32 secchi:

XXXXXX00000 -> bucket 0 
XXXXXX01000 -> bucket 8 
XXXXXX10000 -> bucket 16 
XXXXXX11000 -> bucket 24 

Fortunatamente le cose non sono così male in Java, perché HashMap non usa solo le parti più basse del codice hash: si rimescola i bit in modo che non è così facile da produrre accidentalmente scenari sbagliati. Ecco un estratto dal implementazione HashMap di OpenJDK:

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