7.1 Définition des collisions dans une table de hachage
Une collision dans une table de hachage se produit lorsque deux clés différentes sont hachées au même indice de tableau. Cela conduit à ce que plus d'un élément essaie d'occuper la même cellule dans la table de hachage.
Exemple de collision :
Supposons que nous ayons une simple fonction de hachage qui retourne le reste de la division de la clé par la taille du tableau. Pour les clés 5 et 15 avec une taille de tableau de 10, les deux clés donneront le même indice: 5 % 10 = 5 et 15 % 10 = 5. C'est une collision.
Un autre exemple :
Disons que vous créez un dictionnaire de noms, et vous avez une simple fonction de hachage qui retourne la première lettre du nom. Mais il se trouve que 80 % des noms commencent par la lettre "A". Ce n'est pas juste une collision, c'est un problème.
7.2 Méthodes de résolution des collisions – chaînage
Il existe plusieurs méthodes de résolution des collisions dans les tables de hachage. Les deux méthodes les plus courantes sont le chaînage (chaining) et l'adressage ouvert (open addressing).
Chaînage (Chaining)
Avantages :
- Simplicité de mise en œuvre.
- Efficace avec un petit nombre de collisions.
- Moins dépendant de la densité de remplissage de la table de hachage.
Inconvénients :
- Nécessite de la mémoire supplémentaire pour les pointeurs dans la liste chaînée.
- La performance peut diminuer avec un grand nombre de collisions à cause de chaînes longues.
Exemple de mise en œuvre de la méthode de chaînage :
Tu peux juste étudier la particularité du fonctionnement de la fonction insert, mais j'ai décidé de fournir le code complet pour plus de commodité.
class HashTableChaining:
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 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
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 = HashTableChaining(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana")) # Output: 2
hash_table.delete("banana")
print(hash_table.search("banana")) # Output: None
7.3 Méthode numéro deux – adressage ouvert
La méthode d'adressage ouvert consiste à rechercher la prochaine cellule disponible dans le tableau si une collision se produit. Il existe différentes stratégies pour rechercher une nouvelle cellule : itération linéaire (linear probing), itération quadratique (quadratic probing) et double hachage (double hashing).
Avantages :
- Ne nécessite pas de mémoire supplémentaire pour stocker des pointeurs.
- Représentation des données plus compacte.
Inconvénients :
- La performance peut significativement diminuer avec une haute densité de remplissage de la table.
- Nécessite plus de ressources computationnelles pour résoudre les collisions.
Exemples de stratégies d'adressage ouvert
Itération linéaire (Linear Probing) :
- Itération avec un pas de 1 :
index = (index + 1) % size. - Simple, mais peut mener à la "clusterisation".
Itération quadratique (Quadratic Probing) :
- Itération avec un pas croissant au carré :
index = (index + i^2) % size. - Réduit le problème de clusterisation, mais plus complexe à implémenter.
Double hachage (Double Hashing) :
- Utilisation d'une deuxième fonction de hachage pour calculer le pas :
index = (index + i * hash2(key)) % size. - Moins de problèmes de clusterisation, mais plus complexe à implémenter.
Exemple de mise en œuvre de la méthode d'adressage ouvert (itération linéaire) : Je vais fournir le code complet, pour simplifier, tu peux juste regarder le fonctionnement de la fonction insert
class HashTableOpenAddressing:
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)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = (key, value)
return
index = (index + 1) % self.size
if index == original_index:
raise Exception("Hash table is full")
self.table[index] = (key, value)
def search(self, key):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
return self.table[index][1]
index = (index + 1) % self.size
if index == original_index:
break
return None
def delete(self, key):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = None
return
index = (index + 1) % self.size
if index == original_index:
break
# Exemple d'utilisation :
hash_table = HashTableOpenAddressing(10)
hash_table.insert("apple", 1)
hash_table.insert("banana", 2)
hash_table.insert("cherry", 3)
print(hash_table.search("banana")) # Output: 2
hash_table.delete("banana")
print(hash_table.search("banana")) # Output: None
7.4 Impact des collisions sur la table de hachage
Impact des collisions sur la performance.
Temps d'accès moyen :
- Dans des conditions idéales (sans collision), le temps d'accès moyen aux éléments dans une table de hachage est
O(1). - Les collisions augmentent le temps d'accès, car il faut gérer les chaînes ou explorer les cellules, ce qui augmente le nombre d'opérations.
Augmentation de la longueur des chaînes :
- Dans la méthode de chaînage, l'augmentation de la longueur des chaînes avec un grand nombre de collisions peut conduire à un temps d'accès linéaire
O(n)pour les opérations de recherche, d'insertion et de suppression. - Les chaînes longues augmentent le nombre de comparaisons nécessaires pour rechercher ou insérer un élément.
Complexité spatiale :
- La méthode de chaînage nécessite une mémoire supplémentaire pour stocker les pointeurs dans les listes chaînées.
- Dans la méthode d'adressage ouvert, remplir la table au-delà d'un certain niveau (généralement environ 70-80%) augmente considérablement le nombre de collisions et, par conséquent, le temps d'accès.
Clusterisation : Dans la méthode d'adressage ouvert (surtout avec l'itération linéaire), il se produit une clusterisation lorsque plusieurs cellules consécutives deviennent occupées, ce qui augmente la probabilité de collisions et détériore la performance.
Exemple d'analyse de l'impact des collisions sur la performance :
C'est vraiment pour ceux qui aiment creuser plus profondément
import time
import random
# Itération linéaire
class HashTableOpenAddressing:
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)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = (key, value)
return
index = (index + 1) % self.size
if index == original_index:
raise Exception("Hash table is full")
self.table[index] = (key, value)
def search(self, key):
index = self.hash_function(key)
original_index = index
while self.table[index] is not None:
if self.table[index][0] == key:
return self.table[index][1]
index = (index + 1) % self.size
if index == original_index:
break
return None
# Génération d'une grande quantité de données pour l'insertion
hash_table = HashTableOpenAddressing(1000)
keys = [random.randint(1, 10000) for _ in range(800)]
# Insertion des données et mesure du temps
start_time = time.time()
for key in keys:
hash_table.insert(key, key)
print(f"Temps d'insertion : {time.time() - start_time:.6f} secondes")
# Recherche des données et mesure du temps
start_time = time.time()
for key in keys:
hash_table.search(key)
print(f"Temps de recherche : {time.time() - start_time:.6f} secondes")
GO TO FULL VERSION