Czy Słownik Pythona jest przykładem tabeli hash?

Jedną z podstawowych struktur danych w Pythonie jest słownik, który pozwala zapisywać "Klucze "do wyszukiwania" wartości " dowolnego typu. Czy jest to zaimplementowane wewnętrznie jako tabela hash? Jeśli nie, to co?

Author: Tommy Herbert, 2008-09-22
Source

4 answers

Tak, jest to mapowanie hash lub tabela hash. Opis implementacji Pythona dict napisany przez Tima Petersa, znajduje się tutaj .

Dlatego nie możesz użyć czegoś 'nie hashowalnego' jako klucza dict, np. listy: 

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

Możesz przeczytać więcej o tablicach hashowych lub sprawdzić jak zostało zaimplementowane w Pythonie i dlaczego jest zaimplementowane w ten sposób .

 262
Author: nosklo,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-06-26 03:13:43

W słowniku Pythona musi być coś więcej niż wyszukiwanie tabeli w hash (). Przez brutalne eksperymenty znalazłem ten hash : 

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

Jednak nie łamie słownika: 

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

Sprawdzenie stanu zdrowia psychicznego: 

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

Być może istnieje inny poziom Wyszukiwania poza hash (), który pozwala uniknąć kolizji między kluczami słownikowymi. A może dict () używa innego hasha.

(przy okazji, to w Pythonie 2.7.10. Ta sama historia w Pythonie 3.4.3 i 3.5.0 z kolizją na hash(1.1) == hash(214748749.8).)

 34
Author: Bob Stein,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-11-01 04:01:49

Tak. Wewnętrznie jest zaimplementowany jako otwarte hashowanie oparte na prymitywnym wielomianie nad Z/2 (source).

 22
Author: Ben Hoffstein,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-06-12 18:56:55

Aby rozwinąć Wyjaśnienie nosklo: 

a = {}
b = ['some', 'list']
a[b] = 'some' # this won't work
a[tuple(b)] = 'some' # this will, same as a['some', 'list']
 7
Author: Jeremy Cantrell,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2008-09-22 15:09:43