Aller au contenu

Dictionnaires

Table de hachage et dictionnaires⚓︎

Vidéo de Fred BOISSAC (11:01)

I. Dictionnaire en Python⚓︎

Un dictionnaire en Python est une structure de données qui permet de stocker des paires clé-valeur.
Chaque clé dans un dictionnaire est unique et est associée à une valeur.
Les dictionnaires sont très utiles pour stocker des données qui peuvent être rapidement récupérées via des clés uniques.

Exemple :

🐍 Editeur
# Création d'un dictionnaire
eleve = {
    "nom": "Alice",
    "age": 16,
    "cours": ["Mathématiques", "NSI"],
    "note_moyenne": 15.5
}

# Accès aux éléments du dictionnaire
print(eleve["nom"])         # Affiche "Alice"
print(eleve["age"])         # Affiche 16
print(eleve["cours"])       # Affiche ["Mathématiques", "NSI"]
print(eleve["note_moyenne"]) # Affiche 15.5

# Ajout d'un nouvel élément
eleve["etablissement"] = "Lycée Phoreniépce"
print(eleve["etablissement"])  # Affiche "Lycée Phoreniépce"

# Modification d'une valeur existante
eleve["age"] = 17
print(eleve["age"])         # Affiche 17

# Suppression d'un élément
del eleve["note_moyenne"]
print(eleve)                # Affiche le dictionnaire sans la clé "note_moyenne"
▶️ Console
Alice
16
['Mathématiques', 'NSI']
15.5
Lycée Phoreniépce
17
{'nom': 'Alice', 'age': 17, 'cours': ['Mathématiques', 'NSI'], 'etablissement': 'Lycée Phoreniépce'}

II. Table de hachage⚓︎

Une table de hachage est une structure de données qui permet de stocker des paires clé-valeur et de retrouver les valeurs associées aux clés très rapidement. En Python, les dictionnaires sont implémentés sous forme de tables de hachage. Chaque clé est transformée par une fonction de hachage en un indice unique, ce qui permet un accès très rapide aux valeurs.

Exemple de fonctionnement d'une table de hachage :

  • Fonction de hachage : Convertit une clé en un indice.

  • Stockage : Utilise cet indice pour stocker la valeur dans une table (un tableau).

Voici un exemple pour illustrer comment une table de hachage fonctionne en utilisant un dictionnaire en Python :

Exemple simplifié d'une table de hachage :

🐍 Editeur
class TableDeHachage:
    def __init__(self):
        self.table = [None] * 10  # Création d'une table de taille 10

    def fonction_de_hachage(self, cle):
        return hash(cle) % len(self.table)  # Utilisation de la fonction hash de Python

    def ajouter(self, cle, valeur):
        index = self.fonction_de_hachage(cle)
        if self.table[index] is None:
            self.table[index] = []
        self.table[index].append((cle, valeur))

    def obtenir(self, cle):
        index = self.fonction_de_hachage(cle)
        if self.table[index] is not None:
            for (k, v) in self.table[index]:
                if k == cle:
                    return v
        return None

# Utilisation de la table de hachage
hash_table = TableDeHachage()
hash_table.ajouter("nom", "Alice")
hash_table.ajouter("age", 16)

print(hash_table.obtenir("nom"))  # Affiche "Alice"
print(hash_table.obtenir("age"))  # Affiche 16
print(hash_table.obtenir("adresse"))  # Affiche None, car la clé n'existe pas
▶️ Console
Alice
None
None

III. Comparaison⚓︎

  • Dictionnaire : utilisé directement en Python pour un accès rapide aux éléments via des clés uniques. C'est une implémentation de table de hachage optimisée et prête à l'emploi.

  • Table de hachage : concept de base sur lequel les dictionnaires sont construits. Il montre comment les données sont organisées pour un accès efficace.

Important

Les dictionnaires en Python sont très efficaces grâce à l'utilisation des tables de hachage, permettant une complexité temporelle moyenne de \(O(1)\) pour les opérations d'insertion, de suppression et de recherche.

IV. Mécanisme d'un dictionnaire en Python⚓︎

🐍 Editeur
class TableHachage():

    def __init__(self):
        self.taille = 26
        self.memoire = [None for i in range(self.taille)]

    def get_hash(self, chaine):
        return ord(chaine[0])-65

    def set(self, cle, valeur):
        self.memoire[self.get_hash(cle)] = valeur

    def get(self, cle):
        return self.memoire[self.get_hash(cle)]
▶️ Console
>>> dico = TableHachage()
>>> dico.set('Bill', 'Microsoft')
>>> dico.set('Allan', 'Enigma')
>>> print(dico.get('Bill'))
Microsoft
>>> print(dico.memoire)
['Enigma', 'Microsoft', None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]

V. Gestion des collisions dans une table de hachage⚓︎

Dans une table de hachage, une collision se produit lorsque deux clés différentes produisent le même indice après avoir été passées par la fonction de hachage. La gestion des collisions est cruciale pour maintenir l'efficacité de la table de hachage.

Il existe plusieurs méthodes pour gérer les collisions :

  • Chaînage (chaining) ;
  • Adressage ouvert (open addressing) ;
  • etc.

5.1. Chaînage⚓︎

Le chaînage consiste à stocker plusieurs éléments dans une même position de la table de hachage en utilisant des structures de données supplémentaires comme des listes chaînées (ou simplement des listes en Python). Chaque indice de la table contient une liste de paires clé-valeur.

Exemple :

🐍 Editeur
class TableDeHachage:
    def __init__(self):
        self.table = [[] for _ in range(10)]  # Crée une table de hachage avec 10 listes vides

    def fonction_de_hachage(self, cle):
        return hash(cle) % len(self.table)

    def ajouter(self, cle, valeur):
        index = self.fonction_de_hachage(cle)
        for pair in self.table[index]:
            if pair[0] == cle:
                pair[1] = valeur  # Met à jour la valeur si la clé existe déjà
                return
        self.table[index].append([cle, valeur])  # Ajoute une nouvelle paire clé-valeur

    def obtenir(self, cle):
        index = self.fonction_de_hachage(cle)
        for pair in self.table[index]:
            if pair[0] == cle:
                return pair[1]
        return None

# Utilisation de la table de hachage avec chaînage
hash_table = TableDeHachage()
hash_table.ajouter("nom", "Alice")
hash_table.ajouter("age", 16)
hash_table.ajouter("adresse", "123 Rue Principale")

print(hash_table.obtenir("nom"))  # Affiche "Alice"
print(hash_table.obtenir("age"))  # Affiche 16
print(hash_table.obtenir("adresse"))  # Affiche "123 Rue Principale"

5.2. Adressage ouvert⚓︎

L'adressage ouvert stocke toutes les paires clé-valeur directement dans la table de hachage elle-même. Si une collision se produit, la table de hachage cherche une autre position libre en suivant une certaine séquence de recherche. Les méthodes courantes d'adressage ouvert incluent :

  • Sondage linéaire (linear probing) : recherche la prochaine position libre séquentiellement ;
  • Sondage quadratique (quadratic probing) : recherche la prochaine position libre en utilisant une fonction quadratique ;
  • Double hachage (double hashing) : utilise une seconde fonction de hachage pour déterminer l'intervalle de recherche.

Exemple de sondage linéaire :

🐍 Editeur
class TableDeHachage:
    def __init__(self):
        self.table = [None] * 10

    def fonction_de_hachage(self, cle):
        return hash(cle) % len(self.table)

    def ajouter(self, cle, valeur):
        index = self.fonction_de_hachage(cle)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == cle:
                self.table[index] = (cle, valeur)  # Met à jour la valeur si la clé existe déjà
                return
            index = (index + 1) % len(self.table)
            if index == original_index:
                raise Exception("Table de hachage pleine")
        self.table[index] = (cle, valeur)

    def obtenir(self, cle):
        index = self.fonction_de_hachage(cle)
        original_index = index
        while self.table[index] is not None:
            if self.table[index][0] == cle:
                return self.table[index][1]
            index = (index + 1) % len(self.table)
            if index == original_index:
                break
        return None

# Utilisation de la table de hachage avec adressage ouvert
hash_table = TableDeHachage()
hash_table.ajouter("nom", "Alice")
hash_table.ajouter("age", 16)
hash_table.ajouter("adresse", "123 Rue Principale")

print(hash_table.obtenir("nom"))  # Affiche "Alice"
print(hash_table.obtenir("age"))  # Affiche 16
print(hash_table.obtenir("adresse"))  # Affiche "123 Rue Principale"

5.3. Conclusion⚓︎

  • Chaînage : simple à implémenter et efficace lorsque les collisions sont fréquentes. La taille de la table de hachage peut être fixe, car les collisions sont gérées par des listes chaînées.
  • Adressage ouvert : évite l'utilisation de structures de données supplémentaires, mais nécessite une table de hachage plus grande et peut souffrir de clustering (groupements de collisions).

A retenir

En Python, les dictionnaires utilisent une forme optimisée de tables de hachage avec une combinaison de techniques pour gérer les collisions efficacement.
Ces techniques permettent d'assurer une complexité temporelle moyenne en \(O(1)\) pour les opérations de recherche, d'insertion et de suppression.