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

187

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?

Tommy Herbert
źródło
2
Jeśli interesują Cię szczegóły techniczne, jeden artykuł w Beautiful Code dotyczy wewnętrznych dictimplementacji Pythona .
Torsten Marek,
To był jeden z moich ulubionych rozdziałów w Beautiful Code.
DGentry
4
Oto wykład Brandona Craiga Rhodesa na temat działania słownika python, youtube.com/watch?v=C4Kc8xzcA68 .
chandola
Od jakiegoś czasu szukałem diagramu przedstawiającego dykt, który deklamuje implementację w pamięci i CPython. Dziękujemy za odwołanie się do książki!
Chen A.

Odpowiedzi:

239

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 .

nosklo
źródło
1
Szwy łączące Tima Petersa, które mają zostać zerwane, czy jest tam czyste połączenie?
Matt Alcock,
1
@MattAlcock: Zaktualizowałem link. Czasami (zwykle ze względu na to, że ktoś chce gdzieś usunąć swój adres e-mail) archiwa listy pythonów są odbudowywane, a identyfikatory wiadomości e-mail zmieniają się, w ten sposób psując te linki. Administratorzy pydotorg zazwyczaj starają się tego uniknąć.
Martijn Pieters
Ale za pomocą .keys()można pobrać listę kluczy. Prawdziwy stół mieszający nie przechowuje kluczy, a jedynie skróty, aby zaoszczędzić miejsce.
noɥʇʎԀʎzɐɹƆ
Pełniejszy opis implementacji słownika
Daniel Goldfarb
32

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

Bob Stein
źródło
14
Tak więc kolizje są nieuniknione. Zestaw S może zawierać nieskończenie dużą liczbę elementów, a chcesz, aby miał skrót do liczby, którą komputer może przechowywać. Każda użyteczna implementacja tabeli skrótów rozwiązuje kolizje, przy czym dwie z najczęstszych metod to: a) otwarte adresowanie i b) tworzenie łańcuchów. To, że nie wykorzystuje idealnego skrótu, nie oznacza, że ​​nie jest to skrót.
TurnipEntropy
1
Zderzenia zdarzają się na ogół, ponieważ istnieją nieskończone możliwe wartości skrótu i ​​skończone kody skrótu. Nawet tablica skrótów musiałaby jakoś poradzić sobie z kolizją.
Yanfeng Liu
3
@YanfengLiu Uważam, że są to dokładnie te same punkty, które przedstawiła TurnipEntropy.
Bob Stein
1
W Pythonie 3.7 wygląda na to, że istnieją 2E20 minus 1 możliwe wartości skrótu. Od -1E20 minus 1 do (+) 1E20 minus 1. Spróbuj hash('I wandered lonely as a cloud, that drifts on high o\'er vales and hills, when all at once, I saw a crowd, a host of golden daffodils.')To daje 19 cyfr po przecinku - -4037225020714749784jeśli jesteś wystarczająco maniakiem, aby się tym przejmować. Kontynuujcie własnymi słowami, dzieci, a hasz wciąż jest 19-cyfrową liczbą. Zakładam, że w Pythonie istnieje ograniczenie długości łańcucha znaków, ale można powiedzieć o wiele więcej możliwych łańcuchów niż możliwych wartości. A tak przy okazji hash(False)= 0.
Will Croxford,
22

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

Ben Hoffstein
źródło
7

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']
Jeremy Cantrell
źródło