Un dictionnaire Python est-il un exemple de table de hachage?

L'une des structures de données de base en Python est le dictionnaire, qui permet d'enregistrer des «clés» pour rechercher des «valeurs» de tout type. Est-ce implémenté en interne sous forme de table de hachage? Sinon, qu'est-ce que c'est?

Oui, c'est un mappage de hachage ou une table de hachage. Vous pouvez lire une description de l'implémentation de dict de python, écrite par Tim Peters, ici .

C'est pourquoi vous ne pouvez pas utiliser quelque chose de 'non hachable' comme clé de dict, comme une liste:

>>> a = {}
>>> b = ['some', 'list']
>>> hash(b)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: list objects are unhashable
>>> a[b] = 'some'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: list objects are unhashable

Vous pouvez en savoir plus sur les tables de hachage ou vérifier comment elles ont été implémentées en python et pourquoi elles sont implémentées de cette façon .

Il doit y avoir plus dans un dictionnaire Python qu'une recherche de table sur hash (). Par expérimentation brute, j'ai trouvé cette collision de hachage :

>>> hash(1.1)
2040142438
>>> hash(4504.1)
2040142438

Pourtant, cela ne casse pas le dictionnaire:

>>> d = { 1.1: 'a', 4504.1: 'b' }
>>> d[1.1]
'a'
>>> d[4504.1]
'b'

Verification sanitaire:

>>> for k,v in d.items(): print(hash(k))
2040142438
2040142438

Il existe peut-être un autre niveau de recherche au-delà de hash () qui évite les collisions entre les clés du dictionnaire. Ou peut-être que dict () utilise un hachage différent.

(Au fait, ceci en Python 2.7.10. Même histoire en Python 3.4.3 et 3.5.0 avec une collision à hash(1.1) == hash(214748749.8).)

Oui. En interne, il est implémenté sous forme de hachage ouvert basé sur un polynôme primitif sur Z / 2 ( source ).

Pour développer l'explication de nosklo:

a = {}
b = ['some', 'list']
a[b] = 'some' # this won't work
a[tuple(b)] = 'some' # this will, same as a['some', 'list']