Tutorial della struttura dei dati della tabella hash

Nell'informatica, la parola "mappa" significa collegare un elemento in un set su un altro elemento in un altro set. Immagina che su una pagina ci siano parole in un cerchio a sinistra e sul lato destro della stessa pagina, c'è un altro cerchio all'interno del quale ci sono altre parole. Supponiamo che in ogni cerchio le parole siano scritte a caso, sparse all'interno del cerchio. Inoltre, supponiamo che le parole nel cerchio sinistro siano chiamate chiavi e che le parole nel cerchio destro siano chiamate valori. Se una freccia viene estratta da ogni parola a sinistra a ogni parola a destra, allora si direbbe che i tasti sono stati mappati sui valori.

Supponiamo di essere il proprietario di un grande negozio di forniture nella contea in cui vivi. Supponiamo di vivere in una vasta area, che non è un'area commerciale. Non sei l'unico con un negozio di forniture nella zona; Hai alcuni concorrenti. E poi ti viene in mente che dovresti registrare i numeri di telefono dei tuoi clienti in un libro di allenamento. Naturalmente, il libro di esercizi è piccolo e non puoi registrare tutti i numeri di telefono per tutti i tuoi clienti.

Quindi decidi di registrare solo i numeri di telefono dei tuoi clienti abituali. E così hai una tabella con due colonne. La colonna a sinistra ha i nomi dei clienti e la colonna a destra ha i numeri di telefono corrispondenti. In questo modo, c'è una mappatura tra nomi dei clienti e numeri di telefono. La colonna destra della tabella può essere considerata come la tabella hash core. I nomi dei clienti sono ora chiamati tasti e i numeri di telefono sono chiamati valori. Si noti che quando un cliente continua il trasferimento, dovrai annullare la sua riga, consentendo la riga vuota o essere sostituita con quella di un nuovo cliente normale. Si noti inoltre che con il tempo, il numero di clienti normali può aumentare o diminuire, quindi il tavolo può crescere o ridursi.

Come un altro esempio di mappatura, supponiamo che ci sia un club di agricoltori in una contea. Certo, non tutti gli agricoltori saranno membri del club. Alcuni membri del club non saranno membri regolari (presenti e contributi). Il bar può decidere di registrare i nomi dei membri e la loro scelta di bevande. Sviluppa una tabella di due colonne. Nella colonna di sinistra, scrive i nomi dei membri del club. Nella colonna di destra, scrive la corrispondente scelta di bevande.

C'è un problema qui: ci sono duplicati nella colonna di destra. Cioè, lo stesso nome di un drink si trova più di una volta. In altre parole, membri diversi bevono la stessa bevanda dolce o la stessa bevanda alcolica, mentre altri membri bevono una bevanda dolce o alcolica diversa. L'uomo bar decide di risolvere questo problema inserendo una colonna stretta tra le due colonne. In questa colonna centrale, a partire dall'alto, numera le righe che iniziano da zero (i.e. 0, 1, 2, 3, 4, ecc.), scendendo, un indice per riga. Con questo, il suo problema è risolto, mentre un nome membro ora mappa a un indice e non al nome di una bevanda. Quindi, poiché una bevanda è identificata da un indice, un nome del cliente viene mappato all'indice corrispondente.

La colonna di valori (bevande) da sola forma la tabella hash di base. Nella tabella modificata, la colonna di indici e i loro valori associati (con o senza duplicati) formano una tabella hash normale - la definizione completa di una tabella hash è riportata di seguito. I tasti (prima colonna) non fanno necessariamente parte della tabella hash.

Come un altro esempio di nuovo, considera un server di rete in cui un utente del suo computer client può aggiungere alcune informazioni, eliminare alcune informazioni o modificare alcune informazioni. Ci sono molti utenti per il server. Ogni nome utente corrisponde a una password memorizzata nel server. Coloro che mantengono il server possono vedere i nomi utente e la password corrispondente, e quindi essere in grado di corrompere il lavoro degli utenti.

Quindi il proprietario del server decide di produrre una funzione che crittografa una password prima che venga memorizzata. Un utente accede al server, con la sua normale password compresa. Tuttavia, ora, ogni password è archiviata in un modulo crittografato. Se qualcuno vede una password crittografata e cerca di accedere usandola, non funzionerà, perché accedere, riceve una password compresa dal server e non una password crittografata.

In questo caso, la password compresa è la chiave e la password crittografata è il valore. Se la password crittografata si trova in una colonna di password crittografate, quella colonna è una tabella hash di base. Se quella colonna è preceduta da un'altra colonna con indici a partire da zero, in modo che ogni password crittografata sia associata a un indice, quindi sia la colonna di indici che la colonna della password crittografata, formano una normale tabella hash. Le chiavi non fanno necessariamente parte della tabella hash.

Nota, in questo caso, che ogni chiave, che è una password compresa, corrisponde a un nome utente. Quindi, esiste un nome utente che corrisponde a una chiave che è mappata a un indice, che è associato a un valore che è una chiave crittografata.

La definizione di funzione hash, la definizione completa di una tabella hash, il significato di un array e altri dettagli sono riportate di seguito. Devi avere conoscenza in puntatori (riferimenti) e liste collegate, per apprezzare il resto di questo tutorial.

Significato della funzione hash e tabella hash

Vettore

Un array è un insieme di posizioni di memoria consecutive. Tutte le posizioni hanno le stesse dimensioni. Il valore nella prima posizione è accessibile con l'indice, 0; Il valore nella seconda posizione è accessibile con l'indice, 1; Si accede al terzo valore con l'indice, 2; quarto con indice, 3; e così via. Un array non può normalmente aumentare o restringere. Per modificare la dimensione (lunghezza) di un array, è necessario creare un nuovo array e valori corrispondenti copiati nel nuovo array. I valori di un array sono sempre dello stesso tipo.

Funzione hash

Nel software, una funzione hash è una funzione che prende una chiave e produce un indice corrispondente per una cella di array. L'array è di dimensioni fisse (lunghezza fissa). Il numero di chiavi è di dimensioni arbitrarie, generalmente più grandi della dimensione dell'array. L'indice risultante dalla funzione hash è chiamato valore hash o un digest o un codice hash o semplicemente un hash.

Tavolo hash

Una tabella hash è un array con valori, ai cui indici, le chiavi sono mappate. Le chiavi sono mappate indirettamente ai valori. In effetti, si dice che le chiavi siano mappate sui valori, poiché ogni indice è associato a un valore (con o senza duplicati). Tuttavia, la funzione che esegue la mappatura (i.e. hashing) mette in relazione le chiavi degli indici dell'array e non proprio ai valori, poiché potrebbero esserci duplicati nei valori. Il seguente diagramma illustra una tabella hash per i nomi delle persone e i loro numeri di telefono. Le celle dell'array (slot) sono chiamate secchi.

Si noti che alcuni secchi sono vuoti. Una tabella hash non deve necessariamente avere valori in tutti i suoi secchi. I valori nei secchi non devono necessariamente essere in ordine crescente. Tuttavia, gli indici con cui sono associati sono in ordine crescente. Le frecce indicano la mappatura. Si noti che le chiavi non sono in un array. Non devono essere in nessuna struttura. Una funzione hash prende qualsiasi chiave ed ha un indice per un array. Se non vi è alcun valore nel secchio associato all'indice hash, un nuovo valore può essere messo in quel secchio. La relazione logica è tra la chiave e l'indice e non tra la chiave e il valore associato all'indice.

I valori di un array, come quelli di questa tabella hash, sono sempre dello stesso tipo di dati. Una tabella hash (secchi) può collegare i tasti ai valori di diversi tipi di dati. In questo caso, i valori dell'array sono tutti puntatori, che indicano diversi tipi di valore.

Una tabella hash è un array con una funzione hash. La funzione prende un tasto e hashile un indice corrispondente, e quindi collega i tasti ai valori, nell'array. Le chiavi non devono far parte della tabella hash.

Perché array e non elenco collegato per la tabella hash

L'array per una tabella hash può essere sostituito da una struttura dei dati dell'elenco collegato, ma ci sarebbe un problema. Il primo elemento di un elenco collegato è naturalmente all'indice, 0; Il secondo elemento è naturalmente all'indice, 1; Il terzo è naturalmente all'indice, 2; e così via. Il problema con l'elenco collegato è che per recuperare un valore, l'elenco deve essere ripetuto e questo richiede tempo. L'accesso a un valore in un array è di accesso casuale. Una volta noto l'indice, il valore è ottenuto senza iterazione; Questo accesso è più veloce.

Collisione

La funzione hash prende una chiave e hashes l'indice corrispondente, per leggere il valore associato o per inserire un nuovo valore. Se lo scopo è quello di leggere un valore, non vi è alcun problema (nessun problema), finora. Tuttavia, se lo scopo è quello di inserire un valore, l'indice hash può già avere un valore associato e questa è una collisione; Il nuovo valore non può essere messo dove c'è già un valore. Ci sono modi per risolvere la collisione - vedi sotto.

Perché si verifica la collisione

Nell'esempio del negozio di forniture sopra, i nomi dei clienti sono le chiavi e i nomi delle bevande sono i valori. Si noti che i clienti sono troppi, mentre l'array ha una dimensione limitata e non può prendere tutti i clienti. Quindi, solo le bevande di clienti normali sono conservate nell'array. La collisione si verificherebbe quando un cliente non regolare diventa regolare. I clienti per il negozio formano un set di grandi dimensioni, mentre il numero di secchi per i clienti nell'array è limitato.

Con le tabelle hash, sono i valori per le chiavi che sono molto probabili, che vengono registrati. Quando una chiave che non era probabile, diventa probabile, probabilmente ci sarebbe una collisione. In effetti, la collisione si verifica sempre con le tabelle di hash.

Nozioni di base sulla risoluzione delle collisioni

Due approcci alla risoluzione delle collisioni sono chiamati concatenamento separato e indirizzamento aperto. In teoria, le chiavi non dovrebbero essere nella struttura dei dati o non dovrebbero far parte della tabella hash. Tuttavia, entrambi gli approcci richiedono che la colonna chiave abbia preceduto la tabella hash e diventi parte della struttura generale. Invece di essere i tasti nella colonna dei tasti, i puntatori dei tasti possono essere nella colonna dei tasti.

Una tabella hash pratica include una colonna di tasti, ma questa colonna chiave non fa ufficialmente parte della tabella hash.

Entrambi gli approccio per la risoluzione possono avere secchi vuoti, non necessariamente alla fine dell'array.

Incatenamento separato

In incapaci separati, quando si verifica una collisione, il nuovo valore viene aggiunto a destra (non sopra o sotto) del valore riscosso. Quindi due o tre valori finiscono per avere lo stesso indice. Raramente più di tre dovrebbero avere lo stesso indice.

Più di un valore può davvero avere lo stesso indice in un array? - NO. Quindi, in molti casi, il primo valore per l'indice è un puntatore a una struttura dei dati dell'elenco collegato, che contiene i valori uno, due o tre colpiti. Il seguente diagramma è un esempio di una tabella hash per il concatenamento separato dei clienti e i loro numeri di telefono:

I secchi vuoti sono contrassegnati con la lettera x. Il resto degli slot ha puntatori a elenchi collegati. Ogni elemento dell'elenco collegato ha due campi di dati: uno per il nome del cliente e l'altro per il numero di telefono. Il conflitto si verifica per le chiavi: Peter Jones e Suzan Lee. I valori corrispondenti sono costituiti da due elementi di un elenco collegato.

Per le chiavi in ​​conflitto, il criterio per inserire il valore è lo stesso criterio utilizzato per individuare (e leggere) il valore.

Affronta apertura

Con l'indirizzamento aperto, tutti i valori sono archiviati nell'array del secchio. Quando si verifica il conflitto, il nuovo valore viene inserito in un secchio vuoto nuovo il valore corrispondente per il conflitto, seguendo alcuni criteri. Il criterio utilizzato per inserire un valore in conflitto è lo stesso criterio utilizzato per individuare (cercare e leggere) il valore.

Il seguente diagramma illustra la risoluzione dei conflitti con indirizzamento aperto:

La funzione hash prende la chiave, Peter Jones e hashes l'indice, 152, e memorizza il suo numero di telefono al secchio associato. Dopo un po 'di tempo, la funzione hash ha lo stesso indice, 152 dalla chiave, Suzan Lee, che si scontra con l'indice per Peter Jones. Per risolverlo, il valore per Suzan Lee è memorizzato nel secchio dell'indice successivo, 153, che era vuoto. La funzione hash hash l'indice, 153 per la chiave, Robin Hood, ma questo indice è già stato utilizzato per risolvere il conflitto per una chiave precedente. Quindi il valore per Robin Hood è posto nel prossimo secchio vuoto, che è quello dell'indice 154.

Metodi di risoluzione dei conflitti per il concatenamento separato e l'indirizzo aperto

Il concatenamento separato ha i suoi metodi per risolvere i conflitti e l'affronta aperta ha anche i suoi metodi per risolvere i conflitti.

Metodi per risolvere conflitti di incapaci separati

I metodi per le tabelle hash concapettate separate sono brevemente spiegati:

Concapazione separata con elenchi collegati

Questo metodo è come spiegato sopra. Tuttavia, ogni elemento dell'elenco collegato non deve necessariamente avere il campo chiave (E.G. campo nome cliente sopra).

Concapazione separata con celle della testa dell'elenco

In questo metodo, il primo elemento dell'elenco collegato è memorizzato in un secchio dell'array. Ciò è possibile, se il tipo di dati per l'array, è l'elemento dell'elenco collegato.

Concapazione separata con altre strutture

Qualsiasi altra struttura di dati, come l'albero di ricerca binaria auto -bilanciante che supporta le operazioni richieste, può essere utilizzato al posto dell'elenco collegato - Vedi in seguito.

Metodi per risolvere i conflitti di indirizzamento aperto

Un metodo per risolvere il conflitto nell'indirizzamento aperto è chiamato sequenza di sonda. Tre sequenze di sonda ben note vengono brevemente spiegate ora:

Sondaggio lineare

Con sondaggio lineare, quando si verifica un conflitto, viene cercato il secchio vuoto più vicino sotto il secchio in conflitto. Inoltre, con sondaggio lineare, sia la chiave che il suo valore sono memorizzati nello stesso secchio.

Sondaggio quadratico

Supponiamo che il conflitto si verifichi all'indice H. Lo slot vuoto successivo (secchio) all'indice H + 1² si usa; Se è già occupato, allora quello vuoto successivo a H + 2² viene utilizzato, se è già occupato, allora quello vuoto successivo a H + 3² viene utilizzato, e così via. Ci sono varianti a questo.

Doppio hashing

Con il doppio hashing, ci sono due funzioni di hash. Il primo calcola (hash) l'indice. Se si verifica un conflitto, il secondo usa la stessa chiave per determinare fino a che punto il valore dovrebbe essere inserito. C'è di più in questo - vedi più tardi.

Perfetta funzione hash

Una funzione hash perfetta è una funzione hash che non può provocare alcuna collisione. Ciò può accadere quando l'insieme di chiavi è relativamente piccolo e ogni chiave mappa a un particolare numero intero nella tabella hash.

Nel set di caratteri ASCII, i caratteri della parte superiore possono essere mappati alle corrispondenti lettere minuscole usando una funzione hash. Le lettere sono rappresentate nella memoria del computer come numeri. Nel set di caratteri ASCII, A è 65, B è 66, C è 67, ecc. e A è 97, B è 98, C è 99, ecc. Per mappare da a a a, aggiungi da 32 a 65; Per mappare da B a B, aggiungere da 32 a 66; Per mappare da C a C, aggiungere da 32 a 67; e così via. Qui, le lettere maiuscole sono le chiavi e le lettere minuscole sono i valori. La tabella hash per questo può essere un array i cui valori sono gli indici associati. Ricorda, i secchi dell'array possono essere vuoti. Quindi i secchi nell'array da 64 a 0 possono essere vuoti. La funzione hash aggiunge semplicemente 32 al numero di codice del caso superiore per ottenere l'indice, e quindi la lettera minuscola. Una tale funzione è una funzione hash perfetta.

Hashing dagli indici interi agli interi

Esistono diversi metodi per il numero di hashing. Uno di questi si chiama metodo (funzione) di divisione modulo.

La funzione di hashing della divisione modulo

Una funzione nel software per computer non è una funzione matematica. In Computing (software), una funzione è costituita da una serie di dichiarazioni precedute da argomenti. Per la funzione di divisione modulo, le chiavi sono numeri interi e sono mappati sugli indici della matrice di secchi. L'insieme di chiavi è grande, quindi solo le chiavi che sono molto probabili che si verificano nell'attività sarebbero mappate. Quindi le collisioni si verificano quando le chiavi improbabili devono essere mappate.

Nella dichiarazione,

20/6 = 3r2

20 è il dividendo, 6 è il divisore e 3 rimanenti 2 è il quoziente. Il resto 2 è anche chiamato modulo. Nota: è possibile avere un modulo di 0.

Per questo hashing, la dimensione del tavolo è di solito una potenza di 2, E.G. 64 = 2⁶ o 256 = 2⁸, eccetera. Il divisore per questa funzione di hashing è un numero primo vicino alla dimensione dell'array. Questa funzione divide la chiave per il divisore e restituisce il modulo. Il modulo è l'indice dell'array di secchi. Il valore associato nel secchio è un valore di tua scelta (valore per la chiave).

Tasti di lunghezza variabile di hashing

Qui, le chiavi del set di chiavi sono testi di diverse lunghezze. Interesi diversi possono essere archiviati nella memoria usando lo stesso numero di byte (la dimensione di un carattere inglese è un byte). Quando le chiavi diverse sono di dimensioni di byte diverse, si dice che siano di lunghezza variabile. Uno dei metodi per hashing di lunghezze variabili è chiamato hashing di conversione radix.

Hashing di conversione di Radix

In una stringa, ogni carattere nel computer è un numero. In questo metodo,

Codice hash (indice) = x₀UN^{K - 1}+X₁UN^{K - 2}+… +X_{K - 2}UN¹+X_{K - 1}UN⁰

Dove (x0, x1, ..., xk - 1) sono i caratteri della stringa di input e A è un radix, E.G. 29 (vedi più tardi). K è il numero di caratteri nella stringa. C'è di più in questo - vedi più tardi.

Chiavi e valori

In una coppia chiave/valore, un valore potrebbe non essere necessariamente un numero o un testo. Può anche essere un record. Un record è un elenco scritto in orizzontale. In una coppia chiave/valore, ogni tasto può effettivamente fare riferimento ad un altro testo, numero o record.

Array associativo

Un elenco è una struttura di dati, in cui gli elementi dell'elenco sono correlati e c'è una serie di operazioni che operano nell'elenco. Ogni elemento dell'elenco può consistere in una coppia di elementi. La tabella hash generale con le sue chiavi può essere considerata come una struttura dei dati, ma è più un sistema che una struttura di dati. Le chiavi e i loro valori corrispondenti non dipendono tra loro. Non sono molto legati l'uno all'altro.

D'altra parte, un array associativo è una cosa simile, ma le chiavi e i loro valori sono molto dipendenti l'uno dall'altro; Sono molto legati tra loro. Ad esempio, puoi avere una serie associativa di frutta e loro colori. Ogni frutto ha naturalmente il suo colore. Il nome del frutto è la chiave; Il colore è il valore. Durante l'inserimento, ogni chiave viene inserita con il suo valore. Durante l'eliminazione, ogni chiave viene eliminata con il suo valore.

Un array associativo è una struttura di dati della tabella hash composta da coppie chiave/valore, in cui non vi è alcun duplicato per le chiavi. I valori possono avere duplicati. In questa situazione, le chiavi fanno parte della struttura. Cioè, le chiavi devono essere archiviate, mentre, con il tavolo generale, le chiavi non devono essere memorizzate. Il problema dei valori duplicati è naturalmente risolto dagli indici della matrice di secchi. Non confondere tra valori duplicati e collisione a un indice.

Poiché un array associativo è una struttura di dati, ha almeno le seguenti operazioni:

Operazioni di array associative

inserire o aggiungere

Questo inserisce una nuova coppia chiave/valore nella raccolta, mappando la chiave per il suo valore.

riassegnare

Questa operazione sostituisce il valore di una chiave particolare a un nuovo valore.

eliminare o rimuovere

Questo rimuove una chiave più il suo valore corrispondente.

cercare

Questa operazione cerca il valore di una chiave particolare e restituisce il valore (senza rimuoverla).

Conclusione

Una struttura dei dati della tabella hash è costituita da un array e una funzione. La funzione è chiamata funzione hash. La funzione mappa i valori nell'array attraverso gli indici dell'array. Le chiavi non devono necessariamente far parte della struttura dei dati. Il set di chiavi è generalmente più grande dei valori memorizzati. Quando si verifica una collisione, viene risolta dall'approccio di concatenamento separato o dall'approccio di indirizzamento aperto. Un array associativo è un caso speciale della struttura dei dati della tabella hash.