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 .