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

Eine der grundlegenden Datenstrukturen in Python ist das Wörterbuch, mit dem "Schlüssel" zum Nachschlagen von "Werten" eines beliebigen Typs aufgezeichnet werden können. Wird dies intern als Hash-Tabelle implementiert? Wenn nicht, was ist das?

Ja, es handelt sich um eine Hash-Zuordnung oder eine Hash-Tabelle. Eine Beschreibung der Diktatimplementierung von Python, wie sie von Tim Peters geschrieben wurde, finden Sie hier .

Aus diesem Grund können Sie etwas, das nicht hashbar ist, nicht als Diktatschlüssel verwenden, z. B. eine 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

Sie können mehr über Hash-Tabellen lesen oder überprüfen, wie sie in Python implementiert wurden und warum sie auf diese Weise implementiert wurden .

Ein Python-Wörterbuch muss mehr enthalten als eine Tabellensuche in hash (). Durch brutale Experimente fand ich diese Hash-Kollision :

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

Dennoch bricht es das Wörterbuch nicht:

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

Gesundheitsüberprüfung:

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

Möglicherweise gibt es neben hash () eine weitere Nachschlageebene, die Kollisionen zwischen Wörterbuchschlüsseln vermeidet. Oder vielleicht verwendet dict () einen anderen Hash.

(Übrigens in Python 2.7.10. Gleiche Geschichte in Python 3.4.3 und 3.5.0 mit einer Kollision bei hash(1.1) == hash(214748749.8).)

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

Um die Erklärung von nosklo zu erweitern:

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