Come devo fare per ottimizzare una tabella hash per una determinata popolazione?

Question

Dire che ho una popolazione di coppie chiave-valore che ho intenzione di memorizzare in una tabella hash. La popolazione è fissa e non cambierà mai. Quali ottimizzazioni sono disponibili per rendere la tabella hash il più veloce possibile? Su quali ottimizzazioni dovrei concentrarmi? Questo presuppone che io abbia molto spazio. Ci sarà un numero ragionevole di coppie (dire non più di 100.000).

MODIFICA: Desidero ottimizzare la ricerca. Non mi interessa quanto tempo ci vuole per costruire.

Answer 1

Mi piacerebbe assicurarmi che l'hash della vostra chiave a valori univoci. Ciò assicurerà che ogni ricerca sia costante e quindi, il più velocemente possibile.

Poiché non è possibile avere più di 100.000 chiavi, è possibile avere 100.000 valori hash.

Inoltre, assicurarsi di utilizzare il costruttore che prende uno int per specificare la capacità iniziale (Impostarlo su 100.000) e un valore flottante per impostare il fattore di carico. (Usare 1) Inoltre, per fare ciò è necessario disporre di una funzione di hash perfetta per le proprie chiavi. Ma questo comporterà la ricerca più veloce possibile, nella minor quantità di memoria.

Answer 2

Assicurarsi che non ci siano collisioni. Se non ci sono collisioni, è garantito O (1) tempo di ricerca costante. La prossima ottimizzazione sarebbe quindi la ricerca.

Utilizzare un profilatore per ottimizzare pezzo per pezzo. È difficile senza questo.

Answer 3

L'ottimizzazione deve essere eseguita nel metodo hashCode della chiave class. La cosa da tenere a mente è implementare questo metodo per evitare collisioni.

Answer 4

In generale, per ottimizzare una tabella hash, si desidera ridurre al minimo le collisioni nella determinazione del proprio hash, quindi i bucket non conterranno più di un elemento e la ricerca hash verrà restituita immediatamente.

Il più delle volte, ciò significa che è necessario misurare l'output della funzione hash nello spazio del problema. Quindi suppongo di raccomandare di esaminare quello

Answer 5

Se è possibile creare una tabella hash di grandi dimensioni in modo che non ci siano collisioni, sarà l'ideale. Dal momento che i tuoi inserimenti e ricerche saranno fatti in tempo costante.

Ma se ciò non è possibile, provare a scegliere una funzione di hash in modo tale che le chiavi vengano distribuite uniformemente nella tabella hash.

Answer 6

Perfect hashing algorithms affrontare il problema, ma non può ridimensionare a 100k oggetti. Ho trovato un Java MPH package, ma non l'ho provato.

Answer 7

Se la popolazione è nota al momento della compilazione, la soluzione ottimale consiste nell'utilizzare una funzione hash minima (MPH). Lo Wikipedia page su questo argomento si collega a diversi strumenti Java che possono generarli.

Answer 8

Ottenere l'algoritmo di hashing perfetto per assegnare valori univoci a oggetti 100K è quasi impossibile. Considera il paradosso del compleanno. La data in cui le persone nascono può essere considerata un algoritmo di hashing perfetto, ma se hai più di 23 persone hai più probabilità di avere una collisione, e questo è in una tabella di 365 date.

Quindi, quanto è grande un tavolo per non avere collisioni in 100K?

Se le chiavi sono stringhe, la strategia ottimale è un albero, non binario ma n-ramo per ogni carattere. Se i tasti sono solo in minuscolo, è più semplice, poiché ne hai bisogno solo 26 ogni volta che crei un ramo.

Iniziamo con 26 tasti. Seguire il primo carattere, ad esempio f f potrebbe avere un valore associato. E potrebbe avere sotto-alberi. Cerca un sottoalbero di o. Questo porta a più sottoalberi, quindi cerca il prossimo o. (Sapevi dove stava andando!). Se questo non ha un valore associato, o colpiamo un sottoalbero nullo sulla strada, sappiamo che il valore non è stato trovato.

È possibile ottimizzare lo spazio sull'albero in cui si colpisce un punto di unicità. Supponiamo che tu abbia un key january e diventi unico al 4 ° personaggio. A questo punto in cui si assegna il valore, si memorizza anche la stringa effettiva associata. Nel nostro esempio potrebbe esserci un valore associato a foo ma la chiave a cui si riferisce potrebbe essere cibo, non foo.

Penso che i motori di ricerca di Google utilizzino una tecnica simile a questa.

Answer 9

La domanda chiave è qual è la tua chiave. (Nessun gioco di parole.) Come altri hanno sottolineato, l'obiettivo è di minimizzare il numero di collisioni di hash. Se è possibile ottenere il numero di collisioni hash a zero, ovvero la funzione di hash genera un valore univoco per ogni chiave che viene effettivamente passata ad esso, si avrà un hash perfetto.

Si noti che in Java, una funzione di hash ha in realtà due passaggi: prima la chiave viene eseguita attraverso la funzione hashCode per la sua classe. Quindi calcoliamo un valore di indice nella tabella hash prendendo questo valore modulo la dimensione della tabella hash.

Penso che le persone che parlano della funzione di hash perfetta tendano a dimenticare quel secondo passaggio. Anche se hai scritto una funzione hashCode che ha generato un valore univoco per ogni chiave passata, potresti comunque ottenere un hash assolutamente terribile se questo valore modulo la dimensione della tabella hash non è univoco. Ad esempio, supponiamo di avere 100 chiavi e la funzione hashCode restituisce i valori 1, 1001, 2001, 3001, 4001, 5001, ... 99001. Se la tabella hash ha 100.000 slot, questo sarebbe un hash perfetto. Ogni chiave ha il suo spazio. Ma se ha 1000 slot, hanno tutti hash nello stesso slot. Sarebbe il peggior hash possibile.

Considerare quindi la costruzione di una buona funzione di hash. Prendi i casi estremi. Supponiamo che la tua chiave sia una data. Sai che le date saranno tutte nel gennaio dello stesso anno. Quindi utilizza il giorno del mese in quanto il valore hash dovrebbe essere buono come quello che otterrà: tutto eseguirà un hash su un numero intero univoco in un intervallo limitato. D'altra parte, se le tue date fossero tutte le primissime del mese per molti anni e molti mesi, prendere il giorno del mese sarebbe un terribile hash, dato che ogni vera chiave sarebbe mappata su "1".

Il mio punto è che se si desidera ottimizzare il proprio hash, è necessario conoscere la natura dei dati. Qual è l'attuale gamma di valori che otterrai?