Scelta di una dimensione del tavolo adatta per un hash

Question

Se ho un set di chiavi di 1000, qual è la dimensione adatta per la mia tabella Hash e come viene determinata?

Answer 1

Dipende dal fattore di carico (il punto "percentuale piena" in cui la tabella aumenterà le sue dimensioni e ridistribuirà i suoi elementi). Se sai di avere esattamente 1000 voci e quel numero non cambierà mai, puoi semplicemente impostare il fattore di carico su 1,0 e la dimensione iniziale su 1000 per la massima efficienza. Se non si era sicuri della dimensione esatta, è possibile lasciare il fattore di carico sul valore predefinito di 0,75 e impostare la dimensione iniziale su 1334 (dimensione prevista / LF) per davvero buone prestazioni, a un costo di memoria aggiuntiva.

Puoi usare il seguente costruttore per impostare il fattore di carico:

Hashtable(int initialCapacity, float loadFactor) 

Answer 2

Devi considerare anche la funzione hash.

una regola empirica suggerisce di raddoppiare le dimensioni del tavolo, in modo che ci sia spazio per espandersi e, si spera, mantenere piccolo il numero di collisioni.

Un'altra regola empirica è supporre che si stia eseguendo una sorta di hash relativo al modulo, quindi arrotondare le dimensioni della tabella al numero primo più grande successivo e utilizzare quel numero primo come valore del modulo.

Che tipo di cose hai hashing? Maggiori dettagli dovrebbero generare consigli migliori.

Answer 3

C'è qualche discussione su questi fattori nella documentazione per Hashtable

Answer 4

Lascialo crescere. Con queste dimensioni, la gestione automatica va bene. Oltre a ciò, 2 x size + 1 è una formula semplice. Anche i numeri primi sono abbastanza buoni, ma non appena il tuo set di dati raggiunge una certa dimensione, l'implementazione dell'hash potrebbe decidere di ripassare e ampliare la tabella.

Le tue chiavi stanno guidando l'efficacia e si spera siano abbastanza distinte.

In conclusione: poni la domanda sulla dimensione quando hai problemi come dimensioni o prestazioni lente, a parte questo: non preoccuparti!

Answer 5

Due volte va bene.

Non hai un grande keyset. Non preoccuparti delle discussioni difficili sull'implementazione di HashTable e vai per il 2000.

Answer 6

Vorrei ripetere ciò che https://stackoverflow.com/users/33229/wwwflickrcomphotosrene-germany detto sopra. 1000 non mi sembra un grande hash. Ho usato molti hashtable di quelle dimensioni in Java senza vedere molto in termini di problemi di prestazioni. E quasi mai mi preoccupo delle dimensioni o del fattore di carico.

Se hai eseguito un profiler sul tuo codice e hai stabilito che l'hashtable è il tuo problema, allora inizia a modificare. Altrimenti, non darei per scontato che hai un problema fino a quando non sei sicuro.

Dopotutto, nella maggior parte del codice, il problema delle prestazioni non è dove pensi che sia. Cerco di non anticipare.