Publicités

La table de hachage est une structure de données qui stocke des 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 on connaît l’index de la donnée désirée.

C’est ainsi qu’elle 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. La table de hachage utilise un tableau comme support de stockage et utilise la technique du hachage pour générer un index où un élément doit être inséré ou doit être localisé à partir de.

Hashing

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

Fonction de hachage

  • (1,20)
  • (2,70)
  • (42,80)
  • (4,25)
  • (12,44)
  • (14,32)
  • (17,11)
  • (13,78)
  • (37,98)
Sr.Non. Key Hash Index 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
7 17 17 % 20 = 17 17
8 13 13 % 20 = 13 13
9 37 37 % 20 = 17 17

Linear Probing

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 le prochain emplacement vide dans le tableau en regardant dans la cellule suivante jusqu’à ce que nous trouvions une cellule vide. Cette technique est appelée sondage linéaire.

Sr.No. Key Hash Array Index Après sondage linéaire, Array Index
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

Opérations de base

Voici les opérations primaires de base d’une table de hachage.

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

  • Insertion – Insère un élément dans une table de hachage.

  • suppression – Supprime un élément d’une table de hachage.

DataItem

Définir un élément de données ayant certaines données et une clé, sur la base duquel la recherche doit être effectuée dans une table de hachage.

struct DataItem { int data; int key;};

Méthode de hachage

Définir une méthode de hachage pour calculer le code de hachage de la clé de l’élément de données.

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

Opération de recherche

Quand un élément doit être recherché, calculer le code de hachage de la clé passée et localiser l’élément en utilisant ce code de hachage comme index dans le tableau. Utilisez le sondage linéaire pour obtenir l’élément en avance si l’élément n’est pas trouvé au 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 != NULL) { if(hashArray->key == key) return hashArray; //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } return NULL; }

Opération d’insertion

Chaque fois qu’un élément doit être inséré, calculez le code de hachage de la clé passée et localisez l’élément en utilisant ce code de hachage comme indice dans le tableau. Utilisez une sonde linéaire pour un emplacement vide, si un élément est trouvé au 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 != NULL && hashArray->key != -1) { //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } hashArray = item; }

Opération de suppression

Chaque fois qu’un élément doit être supprimé, calculez le code de hachage de la clé passée et localisez l’index en utilisant ce code de hachage comme index dans le tableau. Utilisez le sondage linéaire pour obtenir l’élément à venir si un élément n’est pas trouvé au code de hachage calculé. Lorsqu’il est trouvé, stockez-y un élément factice pour garder 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 !=NULL) { if(hashArray->key == key) { struct DataItem* temp = hashArray; //assign a dummy item at deleted position hashArray = dummyItem; return temp; } //go to next cell ++hashIndex; //wrap around the table hashIndex %= SIZE; } return NULL; }

Pour connaître l’implémentation du hachage dans le langage de programmation C, veuillez cliquer ici.

Publicités

.