webentwicklung-frage-antwort-db.com.de

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

Eine der grundlegenden Datenstrukturen in Python ist das Dictionary, mit dem man "Schlüssel" zum Nachschlagen von "Werten" eines beliebigen Typs aufzeichnen kann. Ist dies intern als Hash-Tabelle implementiert? Wenn nicht , Was ist es?

161
Tommy Herbert

Ja, es ist ein Hash-Mapping oder eine Hash-Tabelle. Sie können eine Beschreibung der Python-Dikt-Implementierung lesen, wie von Tim Peters geschrieben, hier .

Aus diesem Grund können Sie als Diktierschlüssel nicht "Nicht-Hashbar" 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 lesen Sie mehr über Hash-Tabellen oder überprüfen Sie, wie es in Python implementiert wurde und warum es so implementiert wird .

209
nosklo

Es muss mehr zu einem Python Wörterbuch als eine Tabellensuche auf hash () geben. Durch brachiales Experimentieren fand ich dies Hash-Kollision:

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

Das Wörterbuch wird jedoch nicht beschädigt:

>>> 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 eine andere Suchebene nach hash (), die Kollisionen zwischen Wörterbuchschlüsseln vermeidet. Oder vielleicht verwendet dict () einen anderen Hash.

(Dies ist übrigens in Python 2.7.10. Dieselbe Geschichte in Python 3.4.3 und 3.5.0 mit einer Kollision bei hash(1.1) == hash(214748749.8).)

24
Bob Stein

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

20
Ben Hoffstein

So erweitern Sie die Erklärung von nosklo:

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