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" aufzeichnen, um "Werte" eines beliebigen Typs zu suchen. Wird dies intern als Hash -Tabelle implementiert? Wenn nicht, was ist das?

Answer 1

Ja, es ist eine Hash -Mapping oder eine Hash -Tabelle. Sie können eine Beschreibung von Pythons Diktatimplementierung lesen, wie von Tim Peters geschrieben. hier.

Deshalb können Sie wie eine Liste etwas "nicht hashabel" als Diktatschlüssel verwenden:

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

Du kannst Lesen Sie mehr über Hash -Tabellen oder Überprüfen Sie, wie es in Python implementiert wurde und Warum es so implementiert wird.

Answer 2

Ein Python -Wörterbuch muss mehr als eine Tabelle auf Hash () enthalten. Durch brutales Experimentieren fand ich das Hash -Kollision:

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

Dennoch bricht es nicht das Wörterbuch:

>>> 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 ein weiteres Lookup -Level über Hash () hinaus, der Kollisionen zwischen Wörterbuchschlüssel vermeidet. Oder vielleicht dikt () verwendet einen anderen Hash.

(Übrigens, dies 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).)

Answer 3

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

Answer 4

Um Nosklos Erklärung zu erweitern:

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