La table de hachage vous permet d’implémenter une structure de données de tableau associatif (dictionnaire) avec des performances moyennes O(1) pour les opérations d’insertion, de suppression et de recherche.
Vous trouverez ci-dessous un exemple de l’implémentation la plus simple d’une carte de hachage dans nodeJS :
Comment ça marche ? Surveillez vos mains :
- À l’intérieur de la carte de hachage se trouve un tableau
- À l’intérieur de l’élément du tableau se trouve un pointeur vers le premier nœud de la liste chaînée
- La mémoire est allouée à un tableau de pointeurs (par exemple, 65 535 éléments)
- Ils implémentent une fonction de hachage, la clé du dictionnaire est l’entrée, et en sortie elle peut tout faire, mais à la fin elle renvoie l’index de l’élément du tableau
Comment fonctionne l’enregistrement :
- A l’entrée, il y a une paire de clés – valeur
- La fonction de hachage renvoie l’index par clé
- Obtenir un nœud de liste chaînée à partir d’un tableau par index
- Vérifiez si cela correspond à la clé
- Si cela correspond, remplacez la valeur
- S’il ne correspond pas, passez au nœud suivant jusqu’à ce que nous trouvions ou trouvions un nœud avec la clé requise.
- Si le nœud n’est toujours pas trouvé, créez-le à la fin de la liste chaînée
Fonctionnement de la recherche par clé :
- A l’entrée, il y a une paire de clés – valeur
- La fonction de hachage renvoie l’index par clé
- Obtenir un nœud de liste chaînée à partir d’un tableau par index
- Vérifiez si cela correspond à la clé
- Si cela correspond, renvoyez la valeur
- S’il ne correspond pas, passez au nœud suivant jusqu’à ce que nous trouvions ou trouvions un nœud avec la clé requise.
Pourquoi avons-nous besoin d’une liste chaînée dans un tableau ? En raison de collisions possibles lors du calcul de la fonction de hachage. Dans ce cas, plusieurs paires clé-valeur différentes seront situées au même index dans le tableau, auquel cas la liste chaînée est parcourue pour trouver la clé requise.
Sources
https://ru.wikipedia.org/wiki/Hash table
https://www.youtube.com/watch?v=wg8hZxMRwcw
Code source
https://gitlab.com/demensdeum/datastructures
