Fonction de hachage : fonctionnement interne et gestion des collisions
Comprenez comment Python hache les objets, comment l’adressage ouvert et le chaînage résolvent les collisions, et pourquoi le O(1) moyen peut se dégrader en O(n).
Fonction de hachage : fonctionnement interne et gestion des collisions est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu’est-ce qu’une table de hachage ?
Une table de hachage (dictionnaire en Python) associe des clés à des valeurs à l’aide d’une fonction de hachage qui convertit toute clé en un indice entier dans un tableau sous-jacent. Une fonction de hachage idéale répartit uniformément les clés dans le tableau, ce qui permet d’obtenir en moyenne une recherche, une insertion et une suppression en O(1). Le tableau sous-jacent est appelé table de hachage ou tableau de compartiments.
En Python, dict est une table de hachage hautement optimisée. Comprendre ses mécanismes internes vous aide à raisonner sur le comportement dans le pire des cas et à choisir des clés appropriées.
# Python dict is a hash map
hm = {}
hm['alice'] = 95
hm['bob'] = 87
hm['carol'] = 91
print(hm['alice']) # O(1) lookup: 95
print('bob' in hm) # O(1) membership: True
del hm['bob'] # O(1) deletion
print(hm) # {'alice': 95, 'carol': 91}Fonctions de hachage et méthode __hash__
Python appelle __hash__(key) pour calculer un entier à partir de la clé, puis prend cet entier modulo la taille de la table afin de trouver l’indice du compartiment. Les types intégrés comme int, str et tuple disposent d’implémentations de hachage intégrées rapides. list et dict ne sont pas hachables (ils sont modifiables, et les modifier invaliderait tout hachage enregistré).
Une bonne fonction de hachage répartit uniformément les clés, est déterministe et se calcule rapidement. Le hachage des chaînes de caractères de Python est randomisé d’une exécution à l’autre (il s’agit d’une fonctionnalité de sécurité) — utilisez PYTHONHASHSEED=0 pour le désactiver afin d’obtenir des résultats reproductibles lors de la vérification.
# Built-in hash in Python
print(hash(42)) # integer hashes to itself (CPython)
print(hash('hello')) # string hash (randomised per run)
print(hash((1, 2, 3))) # tuple hash: depends on contents
# Unhashable types
try:
hash([1, 2, 3]) # lists are mutable -> not hashable
except TypeError as e:
print('Error:', e)
# Custom class: define __hash__ and __eq__
class Point:
def __init__(self, x, y): self.x = x; self.y = y
def __hash__(self): return hash((self.x, self.y))
def __eq__(self, other): return self.x == other.x and self.y == other.y
points = {Point(1, 2): 'A', Point(3, 4): 'B'}
print(points[Point(1, 2)]) # 'A'Collisions : quand deux clés produisent le même compartiment
Une collision se produit lorsque deux clés distinctes produisent le même indice de compartiment. Les collisions sont inévitables (principe des tiroirs : une infinité de clés pour un nombre fini de compartiments). Les deux stratégies classiques de résolution sont le chaînage et l’adressage ouvert. Python utilise une variante de l’adressage ouvert avec une exploration pseudo-aléatoire.
Le chaînage stocke une liste chaînée (ou un tableau dynamique) dans chaque compartiment ; toutes les clés qui entrent en collision dans ce compartiment forment une chaîne. L’adressage ouvert recherche le prochain compartiment vide selon une séquence d’exploration.
# Simplified chaining hash map
class ChainingHashMap:
def __init__(self, capacity=8):
self.capacity = capacity
self.buckets = [[] for _ in range(capacity)]
def _idx(self, key):
return hash(key) % self.capacity
def put(self, key, val):
bucket = self.buckets[self._idx(key)]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, val)
return
bucket.append((key, val))
def get(self, key):
for k, v in self.buckets[self._idx(key)]:
if k == key:
return v
return None
hm = ChainingHashMap()
hm.put('a', 1); hm.put('b', 2)
print(hm.get('a')) # 1
print(hm.get('c')) # NoneAdressage ouvert : exploration linéaire
Avec l’exploration linéaire, lorsqu’une collision se produit à l’indice i, la table vérifie i+1, i+2, ... (en revenant au début après la fin) jusqu’à trouver un emplacement vide. La recherche doit explorer la même séquence pour trouver la clé. Les suppressions nécessitent un marqueur de « tombe » plutôt que de vider l’emplacement, afin de ne pas interrompre la chaîne d’exploration.
Le regroupement constitue le principal inconvénient : une fois qu’un groupe d’emplacements remplis s’est formé, les insertions suivantes dans cette zone étendent le groupe, ce qui dégrade les performances jusqu’à O(n).
class LinearProbingHashMap:
DELETED = object() # tombstone sentinel
def __init__(self, capacity=8):
self.capacity = capacity
self.keys = [None] * capacity
self.vals = [None] * capacity
self.size = 0
def _probe(self, key):
idx = hash(key) % self.capacity
while self.keys[idx] is not None and self.keys[idx] != key:
idx = (idx + 1) % self.capacity
return idx
def put(self, key, val):
idx = self._probe(key)
if self.keys[idx] is None:
self.size += 1
self.keys[idx] = key
self.vals[idx] = val
def get(self, key):
idx = self._probe(key)
if self.keys[idx] == key:
return self.vals[idx]
return None
hm = LinearProbingHashMap()
hm.put('x', 10); hm.put('y', 20)
print(hm.get('x')) # 10Facteur de charge et redimensionnement
Le facteur de charge est le rapport entre le nombre d’entrées stockées et la capacité totale : α = n/m. Lorsque α augmente, la probabilité de collision augmente et les performances se dégradent. Le dictionnaire de Python est redimensionné (sa capacité est doublée) lorsque le facteur de charge dépasse environ 2/3. Le redimensionnement consiste à rehacher toutes les entrées existantes dans la nouvelle table plus grande — une opération en O(n) qui se produit peu fréquemment, ce qui maintient le coût amorti des insertions à O(1).
import sys
d = {}
prev_size = sys.getsizeof(d)
for i in range(30):
d[i] = i
new_size = sys.getsizeof(d)
if new_size != prev_size:
print(f'Resized at n={i+1}: {prev_size} -> {new_size} bytes')
prev_size = new_sizeO(1) en moyenne contre O(n) dans le pire des cas
Avec une bonne fonction de hachage, les collisions sont rares et la longueur attendue d’une chaîne reste constante, quelle que soit la valeur de n. La recherche, l’insertion et la suppression sont donc en O(1) en moyenne. Toutefois, un scénario du pire des cas — par exemple une entrée volontairement hostile qui associe toutes les clés au même compartiment — dégrade toutes les opérations jusqu’à O(n). La graine de hachage randomisée de Python atténue cette attaque, mais n’élimine pas théoriquement le pire des cas.
Pour votre analyse lors d’un entretien, dites : « O(1) en moyenne, O(n) dans le pire des cas en raison des collisions ».
# Python randomised hash seed prevents worst-case hash-flooding
import os
print('PYTHONHASHSEED:', os.environ.get('PYTHONHASHSEED', 'random'))
# By default Python randomises the hash of strings each run
# This prevents an attacker from crafting keys that all collide
# To reproduce results in testing: PYTHONHASHSEED=0 python script.pydict, defaultdict ou Counter en Python
Python propose trois variantes de tables de hachage qu’il est utile de connaître. dict est la table à usage général ; l’accès à une clé absente lève KeyError. defaultdict(factory) renvoie une valeur par défaut lors de l’accès à une clé absente (utile pour rassembler des listes ou effectuer des comptages). Counter est une sous-classe spécialisée destinée au comptage d’objets hachables ; elle prend également en charge les opérations arithmétiques entre compteurs.
from collections import defaultdict, Counter
# defaultdict for grouping
groups = defaultdict(list)
for word in ['apple', 'ant', 'banana', 'bee', 'avocado']:
groups[word[0]].append(word)
print(dict(groups))
# {'a': ['apple','ant','avocado'], 'b': ['banana','bee']}
# Counter for frequency
c = Counter('abracadabra')
print(c.most_common(3)) # [('a',5),('b',2),('r',2)]
print(c['a'] - Counter('aa')['a']) # counter subtractionTable de hachage ou ensemble de hachage
Un ensemble de hachage ne stocke que des clés (sans valeurs associées) et prend en charge la vérification d’appartenance, l’insertion et la suppression en O(1). Le set de Python est un ensemble de hachage. Utilisez un ensemble lorsque vous devez seulement répondre à la question « cet élément existe-t-il ? », sans stocker de données associées. Utilisez un dictionnaire lorsque vous devez associer des valeurs (comptages, résultats, etc.) à des clés.
# set for membership testing
visited = set()
for node in [1, 3, 5, 3, 7, 1]:
if node not in visited:
print('New node:', node)
visited.add(node)
# Set operations: union, intersection, difference
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
print('Union:', A | B) # {1,2,3,4,5,6}
print('Intersection:', A & B) # {3,4}
print('Difference:', A - B) # {1,2}Implémenter une table de hachage à partir de zéro (version entretien)
Les recruteurs vous demandent parfois d’implémenter une table de hachage élémentaire. Les composants essentiels sont les suivants : un tableau de compartiments de taille fixe (utilisez 16 ou 1024), chaque compartiment étant une liste de paires (clé, valeur) pour le chaînage, une fonction de hachage (utilisez le hachage intégré de Python % la capacité), et un redimensionnement lorsque le facteur de charge dépasse 0,7. Mentionner spontanément le redimensionnement et le facteur de charge démontre une connaissance approfondie.
class HashMap:
def __init__(self, capacity=16):
self.capacity = capacity
self.size = 0
self.buckets = [[] for _ in range(capacity)]
def _hash(self, key):
return hash(key) % self.capacity
def put(self, key, val):
b = self.buckets[self._hash(key)]
for i, (k, v) in enumerate(b):
if k == key:
b[i] = (key, val)
return
b.append((key, val))
self.size += 1
if self.size / self.capacity > 0.7:
self._resize()
def get(self, key, default=None):
for k, v in self.buckets[self._hash(key)]:
if k == key:
return v
return default
def _resize(self):
old = self.buckets
self.capacity *= 2
self.buckets = [[] for _ in range(self.capacity)]
self.size = 0
for bucket in old:
for k, v in bucket:
self.put(k, v)
hm = HashMap()
for i in range(20):
hm.put(i, i * 2)
print(hm.get(10)) # 20
print(hm.capacity) # should have resizedQuand les tables de hachage échouent : clés non hachables
Seuls les objets hachables peuvent servir de clés de dictionnaire. En Python, un objet est hachable s’il possède une méthode __hash__ et une méthode __eq__, et si sa valeur de hachage ne change pas pendant sa durée de vie. Les listes, les ensembles et les dictionnaires sont modifiables et ne sont donc pas hachables. Les tuples et les ensembles figés sont des solutions hachables qui peuvent remplacer les listes et les ensembles lorsqu’ils servent de clés.
Un piège courant lors des entretiens : le regroupement d’anagrammes nécessite d’utiliser un tuple trié (et non une liste triée) comme clé du dictionnaire.
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # tuple is hashable; list is not
groups[key].append(s)
return list(groups.values())
print(groupAnagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]Résumé : complexité des tables de hachage
Les tables de hachage offrent une complexité moyenne en O(1) pour l’insertion, la suppression et la recherche — elles constituent le fondement de nombreuses solutions optimales d’entretien. Les hypothèses essentielles sont les suivantes : une bonne fonction de hachage répartit uniformément les clés, le facteur de charge reste limité (le redimensionnement le garantit) et les objets servant de clés sont immuables et hachables. Lorsque ces hypothèses sont respectées, les tables de hachage transforment les parcours linéaires en O(n) en recherches en O(1), ce qui permet des solutions comme la somme de deux nombres en O(n) plutôt qu’en O(n²).
Vérification rapide
Vérifiez votre compréhension des concepts de Structures de données et algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris : une table de hachage associe des clés à des indices de compartiments à l’aide d’une fonction de hachage et atteint une complexité moyenne de O(1) pour ses opérations, les collisions sont résolues par chaînage (une liste chaînée par compartiment) ou par adressage ouvert (exploration du prochain emplacement vide), et seuls les objets immuables et hachables peuvent servir de clés de dictionnaire — utilisez des tuples plutôt que des listes lorsqu’une clé représentant une séquence est nécessaire. Ensuite, nous résoudrons le problème de la somme de deux nombres et ses nombreuses variantes d’entretien.
Questions Fréquemment Posées
La leçon « Fonction de hachage : fonctionnement interne et gestion des collisions » est-elle gratuite ?
Oui — le texte complet de « Fonction de hachage : fonctionnement interne et gestion des collisions » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Fonction de hachage : fonctionnement interne et gestion des collisions » ?
Comprenez comment Python hache les objets, comment l’adressage ouvert et le chaînage résolvent les collisions, et pourquoi le O(1) moyen peut se dégrader en O(n). Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « Fonction de hachage : fonctionnement interne et gestion des collisions » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Fonction de hachage : fonctionnement interne et gestion des collisions
- Two-Sum et ses nombreuses variantes
- Comptage des fréquences et regroupement
- Plus longue séquence consécutive et cache LRU