Est un dictionnaire Python un exemple d'une table de hachage?

Question

L'une des structures de base de données en Python est le dictionnaire, qui permet d'enregistrer des "clés" pour la recherche "valeurs" de n'importe quel type. Est-ce mis en œuvre à l'interne comme à une table de hachage? Si non, quel est-il?

Answer 1

Oui, c'est un hachage de la cartographie ou de la table de hachage. Vous pouvez lire une description de python dict mise en œuvre, comme l'écrit par Tim Peters, ici.

C'est pourquoi vous ne pouvez pas utiliser quelque chose de "pas hashable" comme dict clé, 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 lire plus sur les tables de hachage ou de vérifier comment il a été mis en œuvre en python.

Answer 2

Si vous êtes intéressé par les détails techniques, un article dans le Beau Code traite avec le fonctionnement interne de Python dict mise en œuvre.

Answer 3

Oui. En interne, il est mis en œuvre que d'ouvrir de hachage basée sur une primitive polynôme sur Z/2 (source).

Answer 4

Pour élargir nosklo l'explication:

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