Is een Python-woordenboek een voorbeeld van een hashtabel?

Een van de basisgegevensstructuren in Python is het woordenboek, waarmee men “sleutels” kan opnemen voor het opzoeken van “waarden” van elk type. Is dit intern geïmplementeerd als een hashtabel? Zo niet, wat is het dan?

Antwoord 1, autoriteit 100%

Ja, het is een hash-mapping of hash-tabel. Je kunt een beschrijving lezen van de dict-implementatie van Python, zoals geschreven door Tim Peters, hier.

Daarom kun je iets ‘niet hashable’ niet gebruiken als dicteersleutel, zoals een lijst:

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

Je kunt meer lezen over hashtabellenof controleer hoe het is geïmplementeerd in pythonen waarom het is op die manier geïmplementeerd.

Antwoord 2, autoriteit 15%

Een Python-woordenboek moet meer zijn dan een tabelzoekopdracht op hash(). Door brute experimenten vond ik deze hashbotsing:

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

Toch breekt het het woordenboek niet:

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

Gezondheidscontrole:

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

Mogelijk is er een ander opzoekniveau dan hash() dat botsingen tussen woordenboeksleutels vermijdt. Of misschien gebruikt dict() een andere hash.

(Trouwens, dit in Python 2.7.10. Hetzelfde verhaal in Python 3.4.3 en 3.5.0 met een botsing op hash(1.1) == hash(214748749.8).)

Antwoord 3, autoriteit 8%

Ja. Intern is het geïmplementeerd als open hashing op basis van een primitieve polynoom over Z/2 (bron).

Antwoord 4, autoriteit 2%

Om de uitleg van nosklo uit te breiden:

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