Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Apprendre Table de Hachage | Structures de Données Avancées
Aperçu des Algorithmes et des Structures de Données

book
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)
12345678910111213141516171819202122232425262728293031323334353637383940
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'])
copy

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
1234567891011121314151617181920212223242526272829303132333435363738394041
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'])
copy

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.

question mark

Laquelle des techniques suivantes n'est pas une technique pour résoudre les collisions de fonction de hachage en utilisant l'adressage ouvert ?

Select the correct answer

Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 3. Chapitre 4
some-alt