Définitions, contrats et coûts
Comprendre hachage, égalité, collisions et déduplication.
| Notion | À retenir |
|---|---|
| Dictionnaire | Associe une clé hachable à une valeur ; recherche O(1) moyen sous hypothèses, O(n) au pire. |
| Ensemble | Teste l’appartenance et supprime les doublons ; aucun ordre de parcours métier garanti. |
| Clé | Égalité et hachage doivent être compatibles ; les mutations ne doivent pas changer le hachage. |
Vérifier sur un exemple
Compter des occurrences
Initialisez le compteur absent avant de l’incrémenter.
Python
Python # frequency_table.py
values = ["red", "blue", "red"]
counts = {}
for value in values:
counts[value] = counts.get(value, 0) + 1
print(sorted(counts.items()))
# Expected output:
# [('blue', 1), ('red', 2)]Résultat expliqué. Le tri stabilise seulement l’affichage. Construire le compteur est O(n) moyen avec clés bornées ; trier k clés ajoute O(k log k).
Erreur à éviter. Ne présentez pas un coût moyen comme une garantie au pire. Une liste ne peut pas être une clé de dict.
Deux clés distinctes peuvent-elles avoir le même hachage ?
Oui. Une collision doit être résolue à l’aide du mécanisme de stockage et de l’égalité.