Struttura dei dati e algoritmi - Tabella hash
La tabella hash è una struttura dati che memorizza i dati in modo associativo. In una tabella hash, i dati vengono archiviati in un formato array, in cui ogni valore di dati ha il proprio valore di indice univoco. L'accesso ai dati diventa molto veloce se conosciamo l'indice dei dati desiderati.
Diventa così una struttura dati in cui le operazioni di inserimento e ricerca sono molto veloci indipendentemente dalla dimensione dei dati. Hash Table utilizza un array come supporto di memorizzazione e utilizza la tecnica hash per generare un indice in cui deve essere inserito un elemento o da cui deve essere individuato.
Hashing
L'hashing è una tecnica per convertire un intervallo di valori chiave in un intervallo di indici di un array. Useremo l'operatore modulo per ottenere un intervallo di valori chiave. Si consideri un esempio di tabella hash di dimensione 20 e gli elementi seguenti devono essere archiviati. Gli articoli sono nel formato (chiave, valore).
- (1,20)
- (2,70)
- (42,80)
- (4,25)
- (12,44)
- (14,32)
- (17,11)
- (13,78)
- (37,98)
Sr.No. | Chiave | Hash | Indice array |
---|---|---|---|
1 | 1 | 1% 20 = 1 | 1 |
2 | 2 | 2% 20 = 2 | 2 |
3 | 42 | 42% 20 = 2 | 2 |
4 | 4 | 4% 20 = 4 | 4 |
5 | 12 | 12% 20 = 12 | 12 |
6 | 14 | 14% 20 = 14 | 14 |
7 | 17 | 17% 20 = 17 | 17 |
8 | 13 | 13% 20 = 13 | 13 |
9 | 37 | 37% 20 = 17 | 17 |
Sondaggio lineare
Come possiamo vedere, può accadere che la tecnica di hashing venga utilizzata per creare un indice dell'array già utilizzato. In tal caso, possiamo cercare la successiva posizione vuota nell'array guardando nella cella successiva finché non troviamo una cella vuota. Questa tecnica è chiamata sondaggio lineare.
Sr.No. | Chiave | Hash | Indice array | Dopo il rilevamento lineare, indice di matrice |
---|---|---|---|---|
1 | 1 | 1% 20 = 1 | 1 | 1 |
2 | 2 | 2% 20 = 2 | 2 | 2 |
3 | 42 | 42% 20 = 2 | 2 | 3 |
4 | 4 | 4% 20 = 4 | 4 | 4 |
5 | 12 | 12% 20 = 12 | 12 | 12 |
6 | 14 | 14% 20 = 14 | 14 | 14 |
7 | 17 | 17% 20 = 17 | 17 | 17 |
8 | 13 | 13% 20 = 13 | 13 | 13 |
9 | 37 | 37% 20 = 17 | 17 | 18 |
Operazioni di base
Di seguito sono riportate le operazioni principali di base di una tabella hash.
Search - Cerca un elemento in una tabella hash.
Insert - inserisce un elemento in una tabella hash.
delete - Elimina un elemento da una tabella hash.
DataItem
Definire un elemento di dati con alcuni dati e una chiave, in base al quale deve essere condotta la ricerca in una tabella hash.
struct DataItem {
int data;
int key;
};
Metodo hash
Definire un metodo di hashing per calcolare il codice hash della chiave dell'elemento dati.
int hashCode(int key){
return key % SIZE;
}
Operazione di ricerca
Ogni volta che si deve cercare un elemento, calcolare il codice hash della chiave passata e individuare l'elemento utilizzando tale codice hash come indice nell'array. Utilizzare il rilevamento lineare per portare l'elemento avanti se l'elemento non viene trovato nel codice hash calcolato.
Esempio
struct DataItem *search(int key) {
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty
while(hashArray[hashIndex] != NULL) {
if(hashArray[hashIndex]->key == key)
return hashArray[hashIndex];
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= SIZE;
}
return NULL;
}
Inserisci operazione
Ogni volta che deve essere inserito un elemento, calcolare il codice hash della chiave passata e individuare l'indice utilizzando tale codice hash come indice nell'array. Utilizzare il rilevamento lineare per la posizione vuota, se viene trovato un elemento nel codice hash calcolato.
Esempio
void insert(int key,int data) {
struct DataItem *item = (struct DataItem*) malloc(sizeof(struct DataItem));
item->data = data;
item->key = key;
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty or deleted cell
while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1) {
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= SIZE;
}
hashArray[hashIndex] = item;
}
Elimina operazione
Ogni volta che un elemento deve essere eliminato, calcolare il codice hash della chiave passata e individuare l'indice utilizzando tale codice hash come indice nell'array. Utilizzare il rilevamento lineare per portare l'elemento avanti se un elemento non viene trovato nel codice hash calcolato. Una volta trovato, memorizza un elemento fittizio lì per mantenere intatte le prestazioni della tabella hash.
Esempio
struct DataItem* delete(struct DataItem* item) {
int key = item->key;
//get the hash
int hashIndex = hashCode(key);
//move in array until an empty
while(hashArray[hashIndex] !=NULL) {
if(hashArray[hashIndex]->key == key) {
struct DataItem* temp = hashArray[hashIndex];
//assign a dummy item at deleted position
hashArray[hashIndex] = dummyItem;
return temp;
}
//go to next cell
++hashIndex;
//wrap around the table
hashIndex %= SIZE;
}
return NULL;
}
Per conoscere l'implementazione dell'hash nel linguaggio di programmazione C, fare clic qui .