Molti libri e tutorial dicono che la dimensione di una tabella hash deve essere un numero primo per distribuire uniformemente le chiavi in tutti i bucket. Ma Java HashMap utilizza sempre una dimensione che è una potenza di due. Non dovrebbe usare un numero primo? Cosa c'è di meglio, un "primo" o un "potere di due" come dimensione della tabella hash?Java: un numero "primo" o una "potenza di due" come dimensione HashMap?
Utilizzando una potenza di due maschere efficacemente i bit più in alto del codice hash. Pertanto, in questo scenario, una funzione di hash di scarsa qualità potrebbe rivelarsi particolarmente negativa.
di Java HashMap mitiga questo di diffidare hashCode() implementazione dell'oggetto e applying a second level of hashing to its result:
applica una funzione di hash supplementare per un dato hashCode, che difende contro poveri funzioni hash qualità. Questo è fondamentale perché HashMap utilizza tabelle hash power-of-two, che altrimenti incontrano collisioni per hashCode che non differiscono in bit inferiori.
Se si dispone di una buona funzione di hash, o fare qualcosa di simile a quello che HashMap fa, non importa se si utilizza numeri primi ecc come la dimensione della tabella.
Se, d'altra parte, la funzione di hash è di scarsa qualità o sconosciuta, utilizzare un numero primo sarebbe una scommessa più sicura. Tuttavia, renderà le tabelle dinamicamente più difficili da implementare, poiché all'improvviso sarà necessario essere in grado di produrre numeri primi invece di moltiplicare le dimensioni per un fattore costante.
Per curiosità: perché? (o avete riferimenti/collegamenti che spieghino questo)? –
+1 per l'aggiornamento –
Sei sicuro che la dimensione della tabella non sia importante? Non è il punto di una buona funzione di hash per diffondere i dati attraverso la tabella, al fine di ridurre il numero di collisioni? Ma se la tabella è molto piccola, le collisioni aumenteranno, indipendentemente dalla funzione hash. Mi sto perdendo qualcosa? – pamphlet
L'implementazione HashMap standard ha un metodo hash che rielabora l'hashcode dell'oggetto per evitare quel trabocchetto. Il commento prima the hash() method legge:
/**
* Retrieve object hash code and applies a supplemental hash function to the
* result hash, 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.
*/
Dal punto puntualità/calcolo di vista potenze di due dimensioni possono essere calcolati con solo bit di mascheramento che è più veloce di divisione intera che sarebbe necessaria altrimenti.
L'unico modo per sapere quale è il migliore tra primo e power-of-two è quello di confrontarlo.
Molti anni fa, durante la scrittura di un assemblatore la cui performance dipendeva fortemente dalla ricerca di simboli talbe, l'ho testato utilizzando un grande blocco di identificatori generati. Anche con una mappatura ingenua, ho trovato che il power-of-two, come previsto, aveva una distribuzione meno uniforme e catene più lunghe di un numero primo di bucket di dimensioni simili. Funzionava ancora più velocemente, a causa della velocità della selezione del secchio per mascheramento dei bit.
Sospetto fortemente che gli sviluppatori di java.util non avrebbero fatto ricorso all'hashing e al power-of-two aggiuntivi senza doverli confrontare con un numero primo di bucket. È una cosa molto ovvia da fare quando si progetta una struttura dati hash.
Per questo motivo, sono sicuro che le dimensioni rehash e power-of-two offrono prestazioni migliori per le tipiche mappe di hash Java rispetto a un numero primo di bucket.
Probabilmente si dovrebbero usare tabelle hash di dimensioni primarie se si utilizza quadratic probing per la risoluzione delle collisioni. Se si dispone di una tabella di dimensioni primarie, il sondaggio quadratico colpirà metà delle voci, meno se non è un numero primo. Quindi potresti non trovare un posto adatto per archiviare la tua voce anche se il tuo hash table è meno della metà pieno. Poiché le mappe hash di Java non utilizzano il sondaggio quadratico, non è necessario utilizzare i numeri primi come dimensioni.
Dubito che in realtà lo diano esattamente, e se lo fanno loro sbagliano. Questo è solo un modo per farlo. – EJP