Sto cercando di capire i tavoli hash - qualcuno può spiegarmelo - chiaramente?

Panoramica della tabella hash semplice

Come aggiornamento, una tabella hash è un modo per memorizzare un valore sotto una chiave specifica in una struttura dati. Ad esempio, potrei memorizzare il valore "a" sotto la chiave 1 , e successivamente recuperarlo cercando la chiave 1 nella tabella hash.

L'esempio più semplice di una tabella di hash che posso pensare in cima alla mia testa è una tabella hash che può solo memorizzare interi, dove la chiave per la voce della tabella hash è anche il valore che viene memorizzato. Diciamo che la tua tabella è di dimensione 8, ed è fondamentalmente una matrice in memoria:

---------------------------------
|   |   |   |   |   |   |   |   |
---------------------------------
  0   1   2   3   4   5   6   7  

Funzione hash

Le funzioni di hash ti danno un indice su dove memorizzare il tuo valore. Una semplice funzione di hash per questa tabella sarebbe quella di aggiungere 1 al valore che si desidera memorizzare, quindi mod it per 8 (la dimensione della tabella). In altre parole, la tua funzione di hash è (n+1)%8 , dove n è il numero intero che desideri memorizzare.

Inserti

Se vuoi inserire un valore in questa tabella hash, chiami la tua funzione di hash (in questo caso (n+1)%8 ) sul valore che vuoi inserire per darti un indice. Ad esempio, se vogliamo inserire 14, chiameremmo (14 + 1) % 8 e ottieni indice 7 , quindi inseriremo il valore nell'indice 7 .

---------------------------------
|   |   |   |   |   |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

Allo stesso modo, possiamo inserire 33, 82 e 191 in questo modo:

---------------------------------
|191|   |33 |82 |   |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

Collisioni

Ma cosa succede se proviamo a inserire qualcosa che colliderebbe con una voce? 2 dovrebbe andare nell'indice 3 , ma è preso da 82. Ci sono molti modi per risolvere questo problema, il più semplice è chiamare la nostra funzione di hash ancora e ancora ripetutamente finché non troviamo uno spazio vuoto.

Quindi la logica è la seguente:

1. (2 + 1)% 8 = 3
2. Indice 3 è completo
3. Spina 3 nella nostra funzione di hash. ( 3 + 1)% 8 = 4 , che è vuoto.
4. Inserisci il nostro valore nell'indice 4 .

Ora la tabella hash appare così, con il valore 2 memorizzato all'indice 4 .

---------------------------------
|191|   |33 |82 |2  |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

Il lato negativo di questa soluzione è che presto, il nostro tavolo si riempirà! Se sai che la dimensione dei tuoi dati è limitata, questo non dovrebbe essere un problema se la tua tabella è abbastanza grande da contenere tutti i valori possibili. Se vuoi essere in grado di contenere di più, puoi gestire le collisioni in modo diverso. Torniamo al punto in cui eravamo prima di inserire 2.

---------------------------------
|191|   |33 |82 |   |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

Se ricordi, (2+1)%8 ci dà indice 3 , che è preso. Se non si desidera riempire la tabella hash, è possibile utilizzare ciascun indice tabella come elenco collegato e aggiungerlo all'elenco in tale indice. Quindi, invece di chiamare di nuovo la funzione di hash, semplicemente aggiungeremo l'elenco all'indice 3 :

            -----
            | 2 |
---------------------------------
|191|   |33 |82 |   |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

Questo elenco può quindi aumentare quanto la memoria lo consente. Posso inserire 18 e sarà aggiunto a 2:

            -----
            |18 |
            -----
            | 2 |
---------------------------------
|191|   |33 |82 |   |   |   |14 |
---------------------------------
  0   1   2   3   4   5   6   7  

Ricerche

I valori di ricerca nella tabella hash sono veloci, dato che la tabella hash ha dimensioni piuttosto grandi. Basta chiamare la funzione hash e ottenere l'indice. Diciamo che vuoi vedere se 82 è nel tuo tavolo. La funzione di ricerca chiamerebbe (82+1)%8 = 3 e guarda l'elemento nell'indice 3 e lo restituisce per te. Se hai cercato 16, la funzione di ricerca sembrerebbe nell'indice 1 e vedrai che non esiste.

Le ricerche devono anche gestire le collisioni!

Se si tenta di cercare il valore 2, la tabella hash dovrebbe utilizzare la stessa logica di collisione utilizzata per la memorizzazione dei dati come per il recupero dei dati. A seconda del modo in cui il tuo hash table funziona, dovresti o hash il tasto più e più volte fino a trovare la voce che stai cercando (o trovare uno spazio vuoto), o continueresti a scorrere l'elenco collegato fino a quando non hai trovato l'elemento (o arrivato alla fine della lista)

Sommario

Quindi, le tabelle hash sono un buon modo per archiviare e accedere rapidamente a coppie chiave-valore. In questo esempio abbiamo usato la stessa chiave del valore, ma nelle tabelle di hash del mondo reale le chiavi non sono così limitate. Le funzioni di hash funzioneranno sulle chiavi per generare un indice e quindi la chiave / il valore può essere memorizzato in quell'indice. Le tabelle hash non sono pensate per essere ripetute, anche se è possibile farlo. Come puoi vedere, le tabelle hash possono avere un sacco di spazi vuoti e scorrere tra loro sarebbe una perdita di tempo. Anche se la tabella hash ha la logica per ignorare le ricerche di spazio vuoto nel suo iteratore, ti conviene utilizzare una struttura dati progettata per iteratori, come gli elenchi collegati.

Immagina una biblioteca con migliaia di libri. Devi organizzare i libri in modo che tu possa trovarli per titolo il più rapidamente possibile.

Un modo (comune) per farlo è ordinare i libri in ordine alfabetico. Se il titolo inizia con dire "G", trovi l'area "G", quindi cerca la seconda lettera, pronuncia "ö", quindi "d", "e", "l", restringendo la ricerca, e così via , finché non trovi il libro. Questo, tuttavia, potrebbe richiedere molto tempo e inoltre, quando arrivano nuovi libri, a volte è necessario riorganizzare il layout per fare spazio ai nuovi arrivati.

Questa è la ricerca binaria. Va bene.

C'è, tuttavia, un modo più rapido per farlo. Diciamo che si elencano tutte le librerie e gli scaffali, e quindi per ogni libro si calcola un numero speciale, si spera univoco, che si associa a una libreria / scaffale in cui trovare il libro. Il modo in cui si calcola la "chiave" non importa molto fintanto che dà un numero dall'aspetto casuale. Ad esempio, puoi aggiungere codici carattere di tutte le lettere nel titolo e poi dividerlo per un numero primo (probabilmente non il metodo migliore, ma funziona comunque).

Questo è hashing. È molto più veloce, perché non è necessario passare attraverso interi scaffali e scaffali a guardare la lettera successiva nel titolo. L'hashing è solitamente un'operazione one-shot, a meno che non si abbia una "collisione" quando due o più libri si risolvono sulla stessa chiave. Ma va bene, sai che si trovano l'uno accanto all'altro e, a seconda della qualità della funzione hash, non dovrebbero essercene troppi sotto la stessa chiave.

Le tabelle hash hanno alcune limitazioni e capricci (rimodellamento / ridimensionamento), che mantengono la ricerca binaria come un concorrente valido. Non è tutto nero e amp; bianco per quanto riguarda il metodo è migliore. Ma questa è una storia diversa.

P.S. Scusa se non rispondi direttamente alla tua domanda (scrivi una tabella hash in PHP), ma questo è dettagli e si chiama "programmazione";)

La tabella hash in PHP, per quanto ne so, viene semplicemente implementata tramite:

$my_hash = array(
    1 => "Bob",
    2 => "Alice",
    3 => "Jack"
);

Quindi accedi ai dati tramite chiamate come:

echo $my_hash[2]; // Will echo "Alice"

Si utilizza la funzione foreach () per scorrere i contenuti dell'array.

Il modo migliore per capire le tabelle hash è leggere qualcosa come link , ma grosso modo si riduce a questo: il lato sinistro di ogni riga all'interno di quella chiamata array () sono le chiavi. Queste chiavi verranno sottoposte a un calcolo hash e il risultato è un hash. Probabilmente hai già visto gli hash MD5 o SHA, sembra abbastanza simile a questo. Una parte specifica di questo hash, in genere i primi caratteri X, ma a volte l'hash completo, verrà utilizzata per identificare i cosiddetti "bucket", ovvero le aree di archiviazione per i valori (il lato destro).

Quindi ogni volta che accedi al tuo hashtable, usi la chiave per ottenere il valore. La chiave viene nuovamente calcolata su un hash e l'hash viene utilizzato per cercare rapidamente il valore associato. Quindi le tabelle hash consentono una ricerca più rapida rispetto alla semplice ricerca lineare se tutto è stato appena archiviato. L'unico svantaggio è che alcune implementazioni di hash soffrono di collisioni, che è lo stesso hash calcolato per due chiavi diverse. In generale, non è qualcosa di cui ti devi preoccupare molto.

Spero che questo fornisca qualche background, ma per favore prova a leggere di più sull'argomento se ti interessa. La mia spiegazione è molto rudimentale e sono sicuro che ci siano abbastanza buchi, ma dovrebbe bastare per una rapida spiegazione.