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

Question

L’une des structures de données de base de Python est le dictionnaire, qui permet d’enregistrer des "clés". pour rechercher " valeurs " de tout type. Est-ce implémenté en interne comme une table de hachage? Si non, de quoi s'agit-il?

Answer 1

Oui, il s’agit d’un mappage de hachage ou d’une table de hachage. Vous pouvez lire une description de l'implémentation dict de python, écrite par Tim Peters, ici .

C’est pourquoi vous ne pouvez pas utiliser quelque chose d’inévitable comme clé de dictée, 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 pour en savoir plus sur les tables de hachage ou vérifiez comment cela a été implémenté dans python et pourquoi il est mis en œuvre de cette façon .

Answer 2

Un dictionnaire Python ne doit pas se résumer à une table dans hash (). Par expérimentation brutale, 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'

Contrôle de santé:

>>> 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 alors dict () utilise un hachage différent.

(En passant, ceci dans Python 2.7.10. Même histoire dans Python 3.4.3 et 3.5.0 avec une collision à hash (1.1) == hash (214748749.8) .)

Answer 3

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

Answer 4

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']