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

Question

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 n'importe quel type. Est-ce implémenté en interne comme une table de hachage? Si non, qu'est-ce que c'est?

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, telle que rédigée par Tim Peters, here.

Voilà pourquoi vous ne pouvez pas utiliser quelque chose « non indexables » comme une clé 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 read more about hash tables ou check how it has been implemented in python et why it is implemented that way.

Answer 2

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

Answer 3

Si vous êtes intéressé par les détails techniques, un article dans Beautiful Code traite des composants internes de l'implémentation dict de Python.

Answer 4

Pour élargir 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'] 

Answer 5

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

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

Pourtant, il ne casse pas le dictionnaire:

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

Sanity chèque:

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

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

(Soit dit en passant, ce en Python 2.7.10. Même chose en Python et 3.5.0 avec 3.4.3 une collision à hash(1.1) == hash(214748749.8).)