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?
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
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.
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 ).
dict
implementacji Pythona .Odpowiedzi:
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:
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 .
źródło
.keys()
można pobrać listę kluczy. Prawdziwy stół mieszający nie przechowuje kluczy, a jedynie skróty, aby zaoszczędzić miejsce.W haśle Pythona musi być coś więcej niż wyszukiwanie tabel w hash (). Podczas brutalnych eksperymentów znalazłem to zderzenie mieszające :
Ale to nie łamie słownika:
Kontrola poczytalności:
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)
.)źródło
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 --4037225020714749784
jeś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 okazjihash(False)
= 0.Tak. Wewnętrznie jest implementowany jako otwarty skrót w oparciu o prymitywny wielomian nad Z / 2 ( źródło ).
źródło
Aby rozwinąć wyjaśnienie nosklo:
źródło