De quels composants se compose une table de hachage?

Une table de hachage se compose de deux composants principaux:

1. Tableau (ou liste) de cellules (seaux): C'est la structure principale de stockage. Chaque cellule peut contenir un ou plusieurs éléments de données (paires clé-valeur).

2. Fonction de hachage: Algorithme qui transforme la clé d'entrée en un indice numérique, utilisé pour déterminer la cellule où l'élément de données correspondant doit être stocké ou trouvé.

De plus, pour résoudre les collisions (situations où différentes clés sont hachées au même indice), on utilise des mécanismes tels que:

• Méthode de chaînage: Chaque cellule stocke une liste (par exemple, une liste chaînée) d'éléments hachés à cet indice.
• Méthode d'adressage ouvert: En cas de collision, l'algorithme recherche la prochaine cellule libre selon une stratégie déterminée (sondage linéaire, sondage quadratique, double hachage).

# Exemple de fonction de hachage simple
def simple_hash(cle, taille_tableau):
    # Transformation de la clé en un nombre
    if isinstance(cle, str):
        valeur_hash = sum(ord(caractère) for caractère in cle)
    elif isinstance(cle, int):
        valeur_hash = cle
    else:
        raise TypeError("Type de clé non supporté")

    # Retourner l'indice dans la taille du tableau
    return valeur_hash % taille_tableau

# Exemple de composant de tableau de cellules pour la méthode de chaînage
class HashTable:
    def __init__(self, taille):
        self.taille = taille
        self.array = [[] for _ in range(self.taille)] # Tableau de listes (chaînages)

    def inserer(self, cle, valeur):
        indice = simple_hash(cle, self.taille)
        self.array[indice].append((cle, valeur)) # Ajout du couple clé-valeur à la liste

    def rechercher(self, cle):
        indice = simple_hash(cle, self.taille)
        for k, v in self.array[indice]:
            if k == cle:
                return v
        return None # Clé non trouvée