Table de hachage expliquée: qu'est-ce que c'est et comment l'implémenter

Une table de hachage, également appelée carte de hachage, est une structure de données qui mappe les clés aux valeurs. Il s'agit d'une partie d'une technique appelée hachage, dont l'autre est une fonction de hachage. Une fonction de hachage est un algorithme qui produit un index de l'endroit où une valeur peut être trouvée ou stockée dans la table de hachage.

Quelques remarques importantes sur les tables de hachage:

  1. Les valeurs ne sont pas stockées dans un ordre trié.
  2. Vous tenez compte des collisions potentielles. Cela se fait généralement avec une technique appelée chaînage. Le chaînage signifie créer une liste chaînée de valeurs, dont les clés correspondent à un certain index.

Implémentation d'une table de hachage

L'idée de base du hachage est de distribuer des paires clé / valeur sur un tableau d'espaces réservés ou «compartiments» dans la table de hachage.

Une table de hachage est généralement un tableau de listes liées. Lorsque vous souhaitez insérer une paire clé / valeur, vous devez d'abord utiliser la fonction de hachage pour mapper la clé à un index dans la table de hachage. Étant donné une clé, la fonction de hachage peut suggérer un index où la valeur peut être trouvée ou stockée:

index = f(key, array_size)

Cela se fait souvent en deux étapes:

hash = hashfunc(key) index = hash % array_size

L'utilisation de cette méthode hashest indépendante de la taille de la table de hachage. hashest réduit à un index - un nombre compris entre 0, le début du tableau et array_size - 1, la fin du tableau - à l'aide de l'opérateur modulo (%).

Considérez la chaîne suivante, S:

string S = “ababcd”

Vous devez compter la fréquence de tous les personnages S. Le moyen le plus simple de procéder consiste à parcourir tous les caractères possibles et à compter la fréquence de chacun, un par un.

Cela fonctionne, mais c'est lent - la complexité temporelle d'une telle approche est O (26 * N), Nla taille de la chaîne étant Smultipliée par 26 caractères possibles de AZ.

void countFre(string S) { for(char c = ‘a’;c <= ‘z’;++c) { int frequency = 0; for(int i = 0;i < S.length();++i) if(S[i] == c) frequency++; cout << c << ‘ ‘ << frequency << endl; } }

Production:

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Jetons un coup d'œil à une solution qui utilise le hachage.

Prenez un tableau et utilisez la fonction de hachage pour hacher les 26 caractères possibles avec les indices du tableau. Ensuite, parcourez Set augmentez la valeur du caractère actuel de la chaîne avec l'index correspondant pour chaque caractère.

La complexité de cette approche de hachage est O (N), où N est la taille de la chaîne.

int Frequency[26]; int hashFunc(char c) { return (c - ‘a’); } void countFre(string S) { for(int i = 0;i < S.length();++i) { int index = hashFunc(S[i]); Frequency[index]++; } for(int i = 0;i < 26;++i) cout << (char)(i+’a’) << ‘ ‘ << Frequency[i] << endl; }

Production

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Collisions de hachage

Étant donné que votre carte de hachage sera probablement beaucoup plus petite que la quantité de données que vous traitez, les collisions de hachage sont inévitables. Il existe deux approches principales pour gérer les collisions: le chaînage et l'adressage ouvert .

Chaînage

Comme mentionné précédemment, le chaînage signifie que chaque paire clé / valeur de la table de hachage, la valeur est une liste liée de données plutôt qu'une seule cellule.

Par exemple, imaginez que la clé 152 contienne la valeur «John Smith». Si la valeur "Sandra Dee" est ajoutée à la même clé, "Sandra Dee" est ajoutée en tant qu'autre élément à la clé 152, juste après "John Smith".

152: [["John Smith", "p01"]] ... 152: [["John Smith", "p01"] ["Sandra Dee", "p02"]]

Le principal inconvénient du chaînage est l'augmentation de la complexité temporelle. Au lieu de 0 (1) comme avec une table de hachage régulière, chaque recherche prendra plus de temps car nous devons parcourir chaque liste chaînée pour trouver la valeur correcte.

Adressage ouvert

L'adressage ouvert signifie qu'une fois qu'une valeur est mappée sur une clé déjà occupée, vous vous déplacez le long des clés de la table de hachage jusqu'à ce que vous en trouviez une qui est vide. Par exemple, si "John Smith" a été mappé sur 152, "Sandra Dee" sera mappé sur le prochain index ouvert:

152: ["John Smith", "p01"] ... 152: ["John Smith", "p01"], 153: ["Sandra Dee", "p02"]

Le principal inconvénient de l'adressage ouvert est que, lorsque vous recherchez des valeurs, elles peuvent ne pas correspondre à la mappe de clés à laquelle vous les attendez. Au lieu de cela, vous devez parcourir différentes parties de la table de hachage pour trouver la valeur que vous recherchez.