6.1 Définition et structure d'une table de hachage
Une table de hachage est une structure de données qui permet de retrouver, insérer et supprimer rapidement des éléments en utilisant une fonction de hachage pour calculer les indices dans un tableau ou une liste. Les tables de hachage sont généralement utilisées pour implémenter des tableaux associatifs, également connus sous le nom de dictionaries.
Aspects importants d'une table de hachage
Tableau : C'est le composant principal d'une table de hachage, il stocke des pointeurs vers des éléments ou des listes d'éléments.
Fonction de hachage : Une fonction qui transforme les clés du dictionary en indices de tableau.
Collisions : Situation où deux clés différentes ont la même valeur de hachage. Diverses méthodes sont utilisées pour résoudre les collisions, telles que les chaînes (chaining) ou l'adressage ouvert (open addressing).
Exemple de dictionary :
{
"apple": 101,
"banana": 102,
"cherry": 103
}
Exemple de structure de table de hachage :
| Indice | Valeur |
|---|---|
| 0 | None |
| 1 | [('apple', 101)] |
| 2 | None |
| 3 | [('banana', 102)] |
| 4 | None |
| 5 | None |
| 6 | None |
| 7 | [('cherry', 103)] |
| 8 | None |
| 9 | None |
6.2 Opérations principales sur une table de hachage
Les opérations principales sur une table de hachage : insertion, recherche, suppression
1. Insertion : Processus d'ajout d'un nouvel élément (paire clé-valeur) à une table de hachage.
Étapes de l'insertion :
- Calculer la valeur de hachage de la clé à l'aide de la fonction de hachage.
- Trouver l'indice dans le tableau en se basant sur la valeur de hachage.
- Si un élément est déjà présent à cet indice dans le tableau (collision), ajouter l'élément dans la liste (en cas de chaînes) ou trouver un indice disponible suivant (en cas d'adressage ouvert).
Exemple d'insertion dans une table de hachage avec chaînes :
class HashTable:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
if self.table[index] is None:
self.table[index] = [(key, value)]
else:
for i, kv in enumerate(self.table[index]):
k, v = kv
if k == key:
self.table[index][i] = (key, value)
return
self.table[index].append((key, value))
# Exemple d'utilisation :
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)
2. Recherche : Processus de recherche de la valeur associée à une clé donnée dans une table de hachage.
Étapes de la recherche :
- Calculer la valeur de hachage de la clé à l'aide de la fonction de hachage.
- Trouver l'indice dans le tableau en se basant sur la valeur de hachage.
- Vérifier la présence de la clé dans la liste des éléments (en cas de chaînes) ou à l'indice (en cas d'adressage ouvert).
Exemple de recherche dans une table de hachage avec chaînes :
class HashTable:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def search(self, key):
index = self.hash_function(key)
if self.table[index] is None:
return None
for k, v in self.table[index]:
if k == key:
return v
return None
# Exemple d'utilisation :
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana")) # Affiche : 2
print(hash_table.search("grape")) # Affiche : None
3. Suppression : Processus de suppression d'un élément (paire clé-valeur) d'une table de hachage.
Étapes de la suppression :
- Calculer la valeur de hachage de la clé à l'aide de la fonction de hachage.
- Trouver l'indice dans le tableau en se basant sur la valeur de hachage.
- Supprimer l'élément de la liste (en cas de chaînes) ou définir la valeur à l'indice à
None(en cas d'adressage ouvert).
Exemple de suppression dans une table de hachage avec chaînes :
class HashTable:
def __init__(self, size):
self.size = size
self.table = [None] * size
def hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self.hash_function(key)
if self.table[index] is None:
self.table[index] = [(key, value)]
else:
for i, kv in enumerate(self.table[index]):
k, v = kv
if k == key:
self.table[index][i] = (key, value)
return
self.table[index].append((key, value))
def delete(self, key):
index = self.hash_function(key)
if self.table[index] is None:
return
for i, kv in enumerate(self.table[index]):
k, v = kv
if k == key:
del self.table[index][i]
return
# Exemple d'utilisation :
hash_table = HashTable(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.table)
hash_table.delete("banana")
print(hash_table.table)
print(hash_table.search("banana")) # Affiche : None
6.3 Complexité temporelle des tables de hachage
Complexité temporelle des opérations dans une table de hachage
Insertion :
- Cas moyen :
O(1) - Cas pire :
O(n)(en cas de grand nombre de collisions ou si tous les éléments se retrouvent au même endroit)
Recherche :
- Cas moyen :
O(1) - Cas pire :
O(n)(en cas de grand nombre de collisions ou si tous les éléments se retrouvent au même endroit)
Suppression :
- Cas moyen :
O(1) - Cas pire :
O(n)(en cas de grand nombre de collisions ou si tous les éléments se retrouvent au même endroit)
Explication :
Cas moyen : En moyenne, la fonction de hachage distribue uniformément les éléments dans la table et chaque élément se trouve dans sa propre cellule unique, garantissant un temps d'accès constant O(1).
Cas pire : Dans le pire des cas, tous les éléments se retrouvent dans une même cellule à cause d'une mauvaise fonction de hachage ou d'un grand nombre de collisions. Alors, la table de hachage se transforme en liste chaînée et la complexité temporelle des opérations devient O(n).
6.4 Exemples d'utilisation des tables de hachage
1. Implémentation d'un dictionary (tableau associatif)
Les tables de hachage sont souvent utilisées pour implémenter des dictionaries, qui permettent de stocker des paires clé-valeur et d'assurer un accès rapide par clé.
Exemple :
# Création d'un dictionary
dictionary = {}
# Insertion d'éléments
dictionary["apple"] = 1
dictionary["banana"] = 2
dictionary["cherry"] = 3
# Recherche d'élément
print(dictionary["banana"]) # Affiche : 2
# Suppression d'élément
del dictionary["cherry"]
# Vérification de l'existence d'une clé
if "apple" in dictionary:
print("La clé 'apple' existe dans le dictionary") # Affiche : La clé 'apple' existe dans le dictionary
Maintenant, tu sais un peu plus sur le dictionary en Python et comment il est structuré.
2. Mise en cache des résultats de calculs
Les tables de hachage sont utilisées pour mettre en cache les résultats de calculs coûteux afin d'accélérer les requêtes suivantes.
Exemple :
# Cache pour stocker les résultats
cache = {}
def expensive_computation(x):
if x in cache:
return cache[x]
result = x * x # Exemple de calcul coûteux
cache[x] = result
return result
# Utilisation du cache
print(expensive_computation(10)) # Affiche : 100 (calcul et mise en cache)
print(expensive_computation(10)) # Affiche : 100 (depuis le cache)
3. Comptage de la fréquence des mots dans un texte
Les tables de hachage sont utilisées pour compter le nombre d'occurrences de chaque mot dans un texte.
Exemple :
from collections import defaultdict
text = "this is a simple text with some simple words this is simple"
word_count = defaultdict(int)
for word in text.split():
word_count[word] += 1
# Affichage des résultats
for word, count in word_count.items():
print(f"Le mot '{word}' apparaît {count} fois")
4. Recherche de doublons dans une liste
Les tables de hachage sont utilisées pour rechercher efficacement les doublons dans une liste.
def find_duplicates(arr):
seen = set()
duplicates = []
for item in arr:
if item in seen:
duplicates.append(item)
else:
seen.add(item)
return duplicates
# Exemple d'utilisation
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr)) # Affiche : [2, 4]
GO TO FULL VERSION