Contenu du cours
Aperçu des Algorithmes et des Structures de Données
Aperçu des Algorithmes et des Structures de Données
Table de Hachage
Une table de hachage, également connue sous le nom de carte de hachage ou tableau associatif, est une structure de données qui stocke des paires clé-valeur. Elle offre des opérations d'insertion, de suppression et de recherche efficaces en mappant les clés aux valeurs correspondantes grâce à un processus appelé hachage.
La table de hachage peut être implémentée avec diverses structures de données, mais elle est plus couramment implémentée avec des tableaux et définit trois opérations : insertion, suppression et recherche d'un élément donné.
Remarque
La structure de données dictionnaire de Python implémente une table de hachage, offrant un stockage et une récupération efficaces des paires clé-valeur.
Complexité temporelle des opérations de base
Collisions
Mais il peut arriver que les valeurs de hachage soient les mêmes pour deux clés différentes ou plus. Cela s'appelle une collision. Nous avons donc besoin de moyens pour résoudre ce problème, et il existe deux approches principales.
La première est d'utiliser un mécanisme de chaînage. Si nous avons une collision (s'il y a déjà un élément dans la case du tableau avec un indice généré par la fonction de hachage), nous insérons le nouvel élément comme le prochain élément dans la liste associée à cet indice de tableau ou clé de dictionnaire.
import numpy as np class HashTable: def __init__(self, size): # Initialize the hash table with a specified size self.size = size # Create a dictionary where each key corresponds to an index in the hash table # and each value is an empty numpy array self.table = {i: np.array([]) for i in range(size)} def hash_function(self, key): # Simple modular hashing function to determine the index for a given key return key % self.size def insert(self, key, value): # Compute the index using the hash function index = self.hash_function(key) # Check if the array at the computed index is empty if len(self.table[index]) == 0: # If empty, initialize the array with a tuple containing the key-value pair self.table[index] = np.array([(key, value)]) else: # If not empty, append the key-value pair to the existing array self.table[index] = np.append(self.table[index], np.array([(key, value)])) print(f"The element with value {value} inserted into a hash table at index {index}") # Define key-value pairs pairs = [ {'Phone': 12345, 'Name': 'Will'}, {'Phone': 13492, 'Name': 'Sam'}, {'Phone': 23770, 'Name': 'Mike'}, {'Phone': 12345, 'Name': 'Jack'} ] # Initialize the hash table hash_table = HashTable(size=7) # Insert key-value pairs into the hash table for pair in pairs: hash_table.insert(pair['Phone'], pair['Name'])
Dans l'approche par chaînage, le pire des cas se produit lorsqu'une fonction de hachage mal conçue entraîne toutes les clés hachant au même indice. Cela fait que la table de hachage fonctionne essentiellement comme un tableau régulier, conduisant à une complexité temporelle O(N) pour les opérations d'insertion, de recherche et de suppression.
Le chaînage est généralement utilisé lorsque le nombre de clés est censé dépasser largement la mémoire allouée pour le tableau sous-jacent, et que le nombre exact de clés est incertain. Une fonction de hachage bien conçue est cruciale pour garantir que les opérations s'effectuent avec une complexité temporelle moyenne.
Adressage ouvert
La deuxième approche est appelée adressage ouvert. Dans ce cas, si une collision se produit et que la valeur est déjà présente dans l'emplacement avec l'index généré par la fonction de hachage, nous générons un nouvel index et essayons l'emplacement correspondant jusqu'à ce que nous trouvions celui disponible.
Nous pouvons implémenter diverses méthodes d'adressage ouvert :
- sondage linéaire (lorsque nous incrémentons un index de 1) ;
- sondage quadratique (lorsque nous incrémentons un index d'un degré de 2) ;
- double hachage (lorsque nous générons une nouvelle valeur de hachage basée sur la précédente).
import numpy as np class HashTable: def __init__(self, size): # Define an empty dictionary to represent the hash table self.table = {} # Initialize the hash table with 'None' values for each index for i in range(size): self.table[i] = None def hash_function(self, key): # Simple modular hash function return key % len(self.table) def insert(self, key, value): index = self.hash_function(key) # Check if the current index is available if self.table[index] is None: self.table[index] = value else: # Perform linear probing until an available index is found while self.table[index] is not None: print(f'Index {index} is already occupied. Trying index {index + 1}') index += 1 self.table[index] = value print(f'The element with value {value} inserted into a hash table at index {index}') # Define key-value pairs pairs = [ {'Phone': 12345, 'Name': 'Will'}, {'Phone': 13492, 'Name': 'Sam'}, {'Phone': 23770, 'Name': 'Mike'}, {'Phone': 12345, 'Name': 'Jack'} ] # Initialize the hash table hash_table = HashTable(size=7) # Insert key-value pairs into the hash table for pair in pairs: hash_table.insert(pair['Phone'], pair['Name'])
C'est une approche plus efficace par rapport au chaînage, mais il peut arriver que les valeurs dans notre tableau sous-jacent soient distribuées de manière inégale, et qu'il y ait de grands clusters présents. Dans ce cas, l'efficacité de cette approche diminue.
Ainsi, nous pouvons en conclure que les deux approches, dans leur efficacité, dépendent fortement d'une bonne implémentation d'une fonction de hachage. Construire une bonne fonction de hachage est un problème majeur en informatique. Nous voulons avoir une fonction de hachage qui nous offre une distribution égale des éléments dans une structure de données.
Merci pour vos commentaires !
