Czy słownik Pythona jest przykładem tabeli skrótów?

Jedną z podstawowych struktur danych w Pythonie jest słownik, który pozwala rejestrować „klucze” do wyszukiwania „wartości” dowolnego typu. Czy jest to implementowane wewnętrznie jako tablica skrótów? Jeśli nie, co to jest?

Tak, jest to mapowanie skrótów lub tabela skrótów. Opis implementacji dykta Pythona, napisany przez Tima Petersa, znajduje się tutaj .

Dlatego nie możesz użyć czegoś „nieukrywalnego” jako klucza do dyktowania, takiego jak lista:

>>> 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 tabelach skrótów lub sprawdzić, jak zostało ono zaimplementowane w Pythonie i dlaczego jest zaimplementowane w ten sposób .

W haśle Pythona musi być coś więcej niż wyszukiwanie tabel w hash (). Podczas brutalnych eksperymentów znalazłem to zderzenie mieszające :

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

Ale to nie łamie słownika:

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

Kontrola poczytalności:

>>> 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łownika. A może dict () używa innego skrótu.

(Nawiasem mówiąc, to w Python 2.7.10. Ta sama historia w Python 3.4.3 i 3.5.0 z kolizją w hash(1.1) == hash(214748749.8).)

Tak. Wewnętrznie jest implementowany jako otwarty skrót w oparciu o prymitywny wielomian nad Z / 2 ( źródło ).

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