Come creare una tabella hash

Question

Vorrei prima menzionare che ho esaminato altre domande che chiedevano la stessa cosa su questo sito e su altri siti. Spero di ottenere una buona risposta, perché il mio obiettivo è duplice:

1. Per prima cosa, vorrei imparare come creare una tabella hash.
2. In secondo luogo, trovo che molte risposte su Stack Overflow tendono ad assumere un certo livello di conoscenza su un argomento che spesso non è presente, specialmente per i nuovi tipi. Detto questo, spero di modificare il mio messaggio principale per includere una spiegazione del processo un po 'più approfondito una volta che me ne accorgo.

---

sul corso principale:

Come li capisco finora, una tabella hash è un array di liste (o una struttura dati simile), che spera di, in modo ottimale, ha il minor numero di collisioni il più possibile per preservare la sua lodevole complessità O (1). Quanto segue è il mio processo in corso:

Così il mio primo passo è quello di creare un array di puntatori:

Elem ** table; 
table = new Elem*[size];//size is the desired size of the array 

Il secondo passo è quello di creare una funzione di hashing (molto semplice).

int hashed = 0; 
hashed = (atoi(name.c_str()) + id) % size; 
//name is a std string, and id is a large integer. Size is the size of the array. 

mio terzo passo sarebbe quello di creare qualcosa per rilevare le collisioni, che è la parte che sono attualmente a.

Ecco alcuni pseudo-codice:

while(table[hashedValue] != empty) 
    hashedValue++ 

else 
    put in the list at that index. 

E 'relativamente poco elegante, ma io sono ancora al "che cosa è questo" stadio. Sopportami.

C'è qualcos'altro? Ho perso qualcosa o fatto qualcosa in modo errato?

Grazie

Answer 1

maniglia non trovando slot vuoti e il ridimensionamento della tabella.

Answer 2

Ti manca una definizione per Elem. Non è banale, in quanto dipende dal fatto che si desideri una tabella di hash chaining o hash.

Answer 3

Una funzione di hash produce lo stesso valore per gli stessi dati. Il controllo della collisione, tuttavia, modifica quel valore, il che significa che il valore dell'hash non dipende solo dall'input, ma anche dalla presenza di altri elementi nella mappa hash. Questo è un male, dato che non sarai mai in grado di accedere effettivamente all'elemento che hai inserito prima attraverso il suo nome, solo attraverso l'iterazione sulla mappa.

In secondo luogo, il controllo di collisione è vulnerabile agli errori di overflow/intervallo, poiché si aumenta semplicemente il valore hash senza confrontarsi con la dimensione della mappa (sebbene, come ho detto prima, non si dovrebbe nemmeno farlo).