Table de hachage simplifiee

Le dictionnaire Python (dict) est en fait une table de hachage. C'est l'une des structures de données les plus importantes en informatique, car elle permet d'acceder a une valeur par sa clé en O(1) en moyenne.

Le principe : une fonction de hachage transforme la clé en un nombre (un index dans un tableau). On stocke la paire (cle, valeur) a cet index. Si deux clés differentes donnent le meme index (collision), on les stocke dans une liste a cet index. C'est le chainage.

Imagine un casier a courrier avec 8 cases. Pour ranger une lettre, tu calcules le numéro de case a partir du nom du destinataire. Si deux personnes tombent dans la meme case, les lettres s'empilent dans cette case.

Implemente une classe TableHachage avec :
- __init__(taille=8) : crée un tableau de taille listes vides
- _hacher(cle) : retourne hash(cle) % self.taille
- insérer(cle, valeur) : insère ou met a jour la paire cle/valeur
- obtenir(cle) : retourne la valeur associee, ou None si absente
- supprimer(cle) : supprime la paire si elle existe

Exemple :
t = TableHachage()
t.insérer('nom', 'Alice')
t.obtenir('nom') renvoie 'Alice'
t.supprimer('nom')
t.obtenir('nom') renvoie None

Tests (3/4)

Inserer/Obtenir

t = TableHachage()
t.insérer('nom', 'Alice')
assert t.obtenir('nom') == 'Alice'

Mise a jour

t = TableHachage()
t.insérer('age', 25)
t.insérer('age', 30)
assert t.obtenir('age') == 30

Supprimer

t = TableHachage()
t.insérer('x', 1)
t.supprimer('x')
assert t.obtenir('x') is None

+ 0 tests cachés

Indices (3 disponibles)

Solution officielle

class TableHachage:
    def __init__(self, taille=8):
        self.taille = taille
        self.tableau = [[] for _ in range(taille)]

    def _hacher(self, cle):
        return hash(cle) % self.taille

    def inserer(self, clé, valeur):
        idx = self._hacher(cle)
        seau = self.tableau[idx]
        for i, (k, v) in enumerate(seau):
            if k == cle:
                seau[i] = (cle, valeur)
                return
        seau.append((cle, valeur))

    def obtenir(self, cle):
        idx = self._hacher(cle)
        for k, v in self.tableau[idx]:
            if k == cle:
                return v
        return None

    def supprimer(self, cle):
        idx = self._hacher(cle)
        self.tableau[idx] = [(k, v) for k, v in self.tableau[idx] if k != cle]

← Liste chainee simple Pile pour vérifier les parentheses →

solution.py

Bravo!

Table de hachage simplifiee

Tests (3/4)

Indices (3 disponibles)

Solution officielle