Implementazione Hashtable

Question

Mi è stato chiesto di recente "come implementeresti una hastable". So che l'algoritmo di hashing è fondamentale poiché meno collisioni sono le migliori prestazioni del WRT, ma quale struttura algoritmo/dati deve essere impiegata per fornire un tempo costante ammortizzato {O (1)} per insert/delete/lookups?

Answer 1

tabelle hash hanno due possibilità principali:

1. indirizzamento aperto, che è un semplice array [matrice dinamica actualy se si potete lasciare il vostro tavolo crescere al volo]. Una volta che un conflitto si è verificato, è necessario utilizzare una seconda funzione di hash per trovare l'ingresso successivo a cui verrà mappato l'elemento. Nota che questa soluzione ha alcuni problemi [che possono essere risolti] quando la tua tabella hash consente anche le eliminazioni. [Bollo speciale per antipasti "cancellati"]
2. concatenamento - in questa soluzione, ogni portata nel matrice è una lista collegata - che contiene tutti gli elementi hash per questo antipasto. Qui: tutti gli elementi associati a un certo valore sono presenti nell'elenco.

La parte importante sulle tabelle hash [in entrambe le soluzioni] al fine di consentire armotorized O (1) inserire/del/guardare in alto - è l'assegnazione di un tavolo più grande e rimasticare una volta è stato raggiunto un pre definito load factor.

EDIT: complessità analsis:
Assumere un fattore di carico di p per qualche p < 1.

1. La probabilità di "collisione" in ogni accesso è p Così la media di matrice accessi è: Sigma(i * p^(i-1) * (1-p)) for each i in [1,n] Questo vi dà: Sigma(i * p^(i-1) * (1-p)) = (1-p) * Sigma(i * p^(i-1)) <= (1-p) * 1/(p-1)^2 = 1-p = CONST. [dai un'occhiata alla correttezza di Sigma(i * p^(i-1)) < 1/(p-1)^2 in wolfram alpha]. In tal modo risultante in media un numero costante di accessi alla matrice. Inoltre: potrebbe essere necessario riprendere tutti gli elementi dopo aver raggiunto il fattore di caricamento, con conseguente accesso O(n) all'array. Ciò si traduce in operazioni n * O(1) [aggiunta di n elementi] e 1 * O(n) op [rifasamento], in modo da ottenere: (n * O(1) + 1 * O(n))/n = O(1) tempo armotorizzato.
2. Molto simile a (1), ma l'analisi viene eseguita sugli accessi alla lista. Ogni operazione richiede esattamente un accesso di matrice e un numero variante di accessi di elenchi, con la stessa analisi di prima.