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?
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 .
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).)
Ja. Intern wird es als offenes Hashing implementiert, das auf einem primitiven Polynom über Z/2 ( source ) basiert.
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']