What is a Hash Table?
Leçon 2 sur 14 du cours Tables de hachage - Série sur les structures de données n°4 de Coddy.
Une table de hachage est une structure de données qui stocke des paires clé-valeur, comme un dictionnaire qui recherche des entrées par leur clé. La magie réside dans la vitesse : une table de hachage bien construite trouve, insère ou supprime une entrée en temps moyen O(1), quel que soit le nombre d'entrées qu'elle contient.
L'astuce est la fonction de hachage. Chaque clé est convertie en un index de compartiment (bucket), de sorte que nous savons exactement où chercher sans parcourir toute la table. Lorsque deux clés différentes atterrissent dans le même compartiment (une collision), nous les gardons ensemble dans une liste à cet emplacement. Cette stratégie est appelée le chaînage.
Les cinq opérations principales sur une table de hachage sont :
- Put : Stocker une paire clé-valeur, ou mettre à jour la valeur si la clé existe déjà.
- Get : Rechercher la valeur pour une clé donnée.
- ContainsKey : Vérifier si une clé est stockée dans la table.
- Remove : Supprimer une paire clé-valeur.
- Size : Retourner le nombre de paires actuellement stockées.
Créons une classe HashMap !
Essayez vous-même
Cette leçon ne comprend pas de défi de code.