Ist ein Python-Wörterbuch ein Beispiel für eine Hash-Tabelle?

Question

Eine der grundlegenden Datenstrukturen in Python ist das Wörterbuch, mit dem man "Schlüssel" für die Suche nach "Werten" eines beliebigen Typs aufzeichnen kann. Wird das intern als Hash-Tabelle implementiert? Wenn nicht, was ist es?

Answer 1

Ja, es ist eine Hash-Zuordnung oder Hash-Tabelle. Sie können eine Beschreibung von pythons dict-Implementierung lesen, wie von Tim Peters, here geschrieben.

Deshalb sollten Sie nicht etwas ‚nicht hashable‘ als dict Schlüssel, wie eine Liste verwenden können:

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

Sie können read more about hash tables oder check how it has been implemented in python und why it is implemented that way.

Answer 2

Ja. Intern wird es als offenes Hashing basierend auf einem primitiven Polynom über Z/2 implementiert (source).

Answer 3

Wenn Sie sich für die technischen Details interessieren, behandelt ein Artikel in Beautiful Code die Interna von Python dict Implementierung.

Answer 4

auf Erklärung des nosklo erweitern:

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

Answer 5

Es gibt mehr zu einem Python-Wörterbuch als ein Nachschlagen in einer Tabelle auf Hash() sein muss. Mit brutalen Experimentieren fand ich diese Hashkollision:

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

Doch es bricht nicht das Wörterbuch:

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

Plausibiltätsprüfung:

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

Möglicherweise gibt es eine andere Lookup Ebene über hash() verhindert Kollisionen zwischen Dictionary Keys. Oder vielleicht verwendet dict() einen anderen Hash.

(By the way, dies in Python 2.7.10. Die gleiche Geschichte in Python 3.4.3 und 3.5.0 mit einer Kollision bei hash(1.1) == hash(214748749.8).)