Numérique et Sciences Informatiques > Algorithmique : Structures de Données Avancées > Tables de Hachage > Opérations principales (insertion, recherche, suppression)

Tables de hachage : Opérations Fondamentales

Découvrez le fonctionnement des tables de hachage et leurs opérations clés : insertion, recherche et suppression. Comprenez leur utilité en informatique et comment les implémenter efficacement.

Introduction aux Tables de Hachage

Les tables de hachage sont des structures de données qui permettent de stocker et de récupérer des informations très rapidement. Elles sont basées sur le concept de fonction de hachage, qui transforme une clé (par exemple, un nom, un numéro) en un indice dans un tableau. Imaginez un grand casier où chaque case correspond à un indice. La fonction de hachage nous dit dans quelle case ranger un objet spécifique.

Fonctionnement de la Fonction de Hachage

La fonction de hachage prend une clé en entrée et produit un indice (un nombre entier) qui correspond à l'emplacement où la donnée sera stockée dans le tableau. Une bonne fonction de hachage doit distribuer les clés de manière uniforme pour éviter les collisions (deux clés qui produisent le même indice).

Opération : Insertion

L'insertion consiste à ajouter une nouvelle paire clé-valeur dans la table de hachage. Voici les étapes :

  1. Calculer l'indice à l'aide de la fonction de hachage : indice = fonction_de_hachage(clé)
  2. Placer la valeur à cet indice dans le tableau.
Si l'indice est déjà occupé (collision), on utilise des techniques de résolution de collisions (voir plus loin).

Opération : Recherche

La recherche consiste à retrouver une valeur associée à une clé donnée. Voici les étapes :

  1. Calculer l'indice à l'aide de la fonction de hachage : indice = fonction_de_hachage(clé)
  2. Vérifier si la clé est présente à cet indice.
  3. Si oui, retourner la valeur associée. Sinon, retourner 'Non trouvé'.
S'il y a eu des collisions lors de l'insertion, il faut parcourir les éléments à cet indice pour retrouver la bonne clé.

Opération : Suppression

La suppression consiste à retirer une paire clé-valeur de la table de hachage. Voici les étapes :

  1. Calculer l'indice à l'aide de la fonction de hachage : indice = fonction_de_hachage(clé)
  2. Vérifier si la clé est présente à cet indice.
  3. Si oui, supprimer la paire clé-valeur. Selon la méthode de résolution des collisions, il peut être nécessaire de réorganiser les éléments suivants.
Une suppression mal gérée peut perturber les recherches ultérieures.

Gestion des Collisions

Les collisions se produisent lorsque deux clés différentes produisent le même indice via la fonction de hachage. Il existe plusieurs méthodes pour gérer les collisions :

  • Chainage séparé (Separate Chaining) : Chaque indice du tableau pointe vers une liste chaînée (ou une autre structure de données) qui contient toutes les paires clé-valeur ayant le même indice.
  • Adressage ouvert (Open Addressing) : En cas de collision, on cherche un autre emplacement libre dans le tableau. Il existe différentes stratégies d'adressage ouvert (sondage linéaire, sondage quadratique, double hachage).
Le choix de la méthode de gestion des collisions impacte les performances des opérations.

Exemple concret

Imaginez une table de hachage pour stocker des noms d'élèves et leurs notes. La clé est le nom de l'élève, et la valeur est sa note. La fonction de hachage pourrait simplement calculer la somme des codes ASCII des lettres du nom, modulo la taille de la table. Par exemple, pour le nom 'Alice', on pourrait avoir :fonction_de_hachage('Alice') = (ord('A') + ord('l') + ord('i') + ord('c') + ord('e')) % taille_tableSi la table est de taille 10, et que la somme des codes ASCII modulo 10 donne 3, alors la note d'Alice serait stockée à l'indice 3 de la table.

Ce qu'il faut retenir

  • Les tables de hachage permettent un accès rapide aux données en utilisant une fonction de hachage.
  • Les opérations principales sont l'insertion, la recherche et la suppression.
  • Les collisions se produisent lorsque deux clés donnent le même indice, et doivent être gérées avec des techniques comme le chaînage séparé ou l'adressage ouvert.
  • Le choix d'une bonne fonction de hachage et d'une bonne méthode de gestion des collisions est crucial pour l'efficacité de la table de hachage.

← Tables de Hachage : Complexité des Opérations Évaluation d'Expressions Arithmétiques →

FAQ

  • Qu'est-ce qui se passe si ma fonction de hachage renvoie toujours le même indice ?

    Si la fonction de hachage renvoie toujours le même indice, toutes les clés vont entrer en collision. Cela transforme la table de hachage en une simple liste chaînée (si vous utilisez le chaînage séparé), et les performances de recherche deviennent O(n) au lieu de O(1) en moyenne.
  • Quelle est la différence entre le chaînage séparé et l'adressage ouvert ?

    Avec le chaînage séparé, chaque indice de la table pointe vers une liste chaînée qui contient toutes les clés qui ont été hachées à cet indice. Avec l'adressage ouvert, si un indice est déjà occupé, on cherche un autre emplacement libre dans la table. Le chaînage séparé utilise plus de mémoire (pour les listes chaînées), mais peut être plus performant si les collisions sont fréquentes.