Structure des données et algorithmes - Table de hachage

Hash Table est une structure de données qui stocke les données de manière associative. Dans une table de hachage, les données sont stockées dans un format de tableau, où chaque valeur de données a sa propre valeur d'index unique. L'accès aux données devient très rapide si l'on connaît l'index des données souhaitées.

Ainsi, il devient une structure de données dans laquelle les opérations d'insertion et de recherche sont très rapides quelle que soit la taille des données. Hash Table utilise un tableau comme support de stockage et utilise la technique de hachage pour générer un index où un élément doit être inséré ou à partir duquel il doit être localisé.

Hashing

Le hachage est une technique pour convertir une plage de valeurs de clé en une plage d'index d'un tableau. Nous allons utiliser l'opérateur modulo pour obtenir une plage de valeurs clés. Prenons un exemple de table de hachage de taille 20, et les éléments suivants doivent être stockés. Les éléments sont au format (clé, valeur).

  • (1,20)
  • (2,70)
  • (42,80)
  • (4,25)
  • (12,44)
  • (14,32)
  • (17,11)
  • (13,78)
  • (37,98)
N ° Sr. Clé Hacher Index du tableau
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
sept 17 17% 20 = 17 17
8 13 13% 20 = 13 13
9 37 37% 20 = 17 17

Palpage linéaire

Comme nous pouvons le voir, il peut arriver que la technique de hachage soit utilisée pour créer un index déjà utilisé du tableau. Dans un tel cas, nous pouvons rechercher l'emplacement vide suivant dans le tableau en regardant dans la cellule suivante jusqu'à ce que nous trouvions une cellule vide. Cette technique est appelée sonde linéaire.

N ° Sr. Clé Hacher Index du tableau Après un palpage linéaire, index de tableau
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
sept 17 17% 20 = 17 17 17
8 13 13% 20 = 13 13 13
9 37 37% 20 = 17 17 18

Opérations de base

Voici les principales opérations de base d'une table de hachage.

  • Search - Recherche un élément dans une table de hachage.

  • Insert - insère un élément dans une table de hachage.

  • delete - Supprime un élément d'une table de hachage.

Élément de données

Définissez un élément de données contenant des données et une clé, sur la base desquels la recherche doit être effectuée dans une table de hachage.

struct DataItem {
   int data;
   int key;
};

Méthode de hachage

Définissez une méthode de hachage pour calculer le code de hachage de la clé de la donnée élémentaire.

int hashCode(int key){
   return key % SIZE;
}

Opération de recherche

Chaque fois qu'un élément doit être recherché, calculez le code de hachage de la clé passée et localisez l'élément en utilisant ce code de hachage comme index dans le tableau. Utilisez le sondage linéaire pour faire avancer l'élément si l'élément n'est pas trouvé au niveau du code de hachage calculé.

Exemple

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;        
}

Insérer une opération

Chaque fois qu'un élément doit être inséré, calculez le code de hachage de la clé transmise et recherchez l'index en utilisant ce code de hachage comme index dans le tableau. Utilisez un sondage linéaire pour un emplacement vide, si un élément est trouvé au niveau du code de hachage calculé.

Exemple

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;        
}

Supprimer l'opération

Chaque fois qu'un élément doit être supprimé, calculez le code de hachage de la clé transmise et recherchez l'index en utilisant ce code de hachage comme index dans le tableau. Utilisez le sondage linéaire pour faire avancer l'élément si un élément n'est pas trouvé dans le code de hachage calculé. Une fois trouvé, stockez-y un élément factice pour conserver intactes les performances de la table de hachage.

Exemple

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;        
}

Pour en savoir plus sur l'implémentation du hachage dans le langage de programmation C, veuillez cliquer ici .