Les tables de hash sont des structures de données particulières permettant de répondre à certaines limitations des types séquence tels que les chaînes de caractères, les listes ou tuples. Python propose deux implémentations des tables de hash: les dictionnaires et les sets (ensembles).

Les types séquences ont été pensés pour l'accès, la modification, l'effacement en fonction d'un numéro de séquence mais pas pour le test d'appartenance (le mot clé in du langage).

La fonction %timeit permet de faire quelques expérimentations simples:

# Parcourir une petite liste pour vérifier si le caractère 'x'
# est présent
%timeit 'x' in range(100)                                                                    
2.74 µs ± 33.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
 
# Parcourir une liste 100 fois plus grande que la précédente
# prendra environ 100 fois plus de temps
%timeit 'x' in range(10_000)                                                                 
344 µs ± 7.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
 
# Parcourir une liste 100 fois plus grande que la précédente
# prendra encore 100 fois plus de temps
%timeit 'x' in range(1_000_000)                                                              
32.1 ms ± 936 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

L'opération de test d'appartenance sur une liste est linéaire et dépendant directement du nombre d'éléments de la liste.

Autre limitation, on accède à un élément d'une liste via un indice mais on pourrait vouloir le faire avec un label, une chaîne de caractère pour augmenter la lisibilité:

# Définition d'une liste contenant des dates de naissances
dates_naiss = [ 1978, 1986]
 
# Dans une liste on accède aux éléments via leur indice.
# Pour modifier le premier élément de la liste
date_naiss[0] = 1933
 
 
# Dans cette liste je ne peux pas associer un label, un nom, à une date
# soit indicer non plus avec des entiers mais des chaînes de caractères.
# C'est syntaxiquement incorrect
date_naiss['bernard'] = 1964
 
TypeError: list indices must be integers or slices, not str

La table de hash est une structure de données qui permet de répondre à ces deux limitations.

La structure dite “table de hash” se compose à la fois d'un tableau à n entrées et d'une fonction de hash qui a pour rôle de créer une correspondance entre un objet quelconque et une entrée du tableau. Des objets différents peuvent être stockés dans une même entrée du tableau (on dit qu'il y a collision). Dans une table de hash, les temps des opérations d'insertion, d'effacement et de recherche ne dépendent plus du nombre total d'éléments mais du temps de calcul de la fonction de hash.

L'efficacité de la table de hash est conditionnée par la taille du tableau qui limite les collisions et la la capacité de la fonction de hash a bien répartir les objets dans les différentes entrées du tableau.

En python les tables de hash ont été implémentée de façon très efficace, l'utilisateur n'a pas à se préoccuper de la fonction de hash ou de la taille du tableau. python adapte gère automatiquement afin de garantir le meilleur résultat.

Les opérations sur les tables de hash sont indépendantes du nombre d'éléments. Elles permettent également d'indexer des valeurs non pas avec des entiers comme dans une liste mais avec par exemple une chaîne de caractère. En python il existe deux implémentation de tables de hash que sont les sets et les dictionnaires.