Jaka jest prawdziwa różnica między słownikiem a tabelą skrótu?

Question

Zawsze używałem słowników. Piszę w Pythonie.

Answer 1

Słownik to ogólna koncepcja mapująca klucze do wartości. Istnieje wiele sposobów na wdrożenie takiego mapowania.

Obiekt hashtable to specyficzny sposób implementacji słownika.

Poza hashtables, innym powszechnym sposobem na wdrożenie słowników jest red-black trees.

Każda metoda ma swoje wady i zalety. Czerwono-czarne drzewo zawsze może wykonać wyszukiwanie w O (log N). Obiekt hashtable może wykonać wyszukiwanie w czasie O (1), chociaż może się ono pogorszyć do O (N) w zależności od danych wejściowych.

Answer 2

Słownik w języku Python jest wewnętrznie implementowany z hashtable.

Answer 3

Słownik jest strukturą danych, która mapuje klucze do wartości.

Tablica haszowania jest strukturą danych, która mapuje klucze do wartości, pobierając wartość skrótu klucza (przez zastosowanie do niej pewnej funkcji mieszania) i mapując ją do zasobnika, w którym przechowywana jest jedna lub więcej wartości.

IMO jest to analogiczne do pytania o różnicę między listą a połączoną listą.

Dla przejrzystości może być ważne, aby pamiętać, że MOŻE to być przypadek, w którym Python obecnie implementuje swoje słowniki za pomocą tablic haszujących, i MOGĄ mieć miejsce w przyszłości, że Python zmieni ten fakt bez powodowania, że ​​ich słowniki przestaną być słownikami .

Answer 4

"Słownik" ma kilka różnych znaczeń w programowaniu, ponieważ wikipedia powie Ci - "tablica asocjacyjna", że sens, w jakim Python używa tego terminu (nazywanego także "mapowaniem"), jest jednym z tych znaczenia (ale "słownik danych" i "ataki słownikowe" w próbie odgadnięcia hasła są również ważne).

Tabele skrótów są ważnymi strukturami danych; Python używa ich do implementacji dwóch ważnych wbudowanych typów danych: dict i set.

Tak więc, nawet w Pythonie, nie można rozważać „tabeli mieszania”, aby być synonimem „słowniku” ... od podobnej strukturze danych służy również do wdrożenia „paczkach” -!)

Answer 5

Słownik jest zaimplementowany przy użyciu tabel mieszających. Moim zdaniem różnicę między 2 można uważać za różnicę między stosami a tablicami, w których używamy tablic do implementacji stosów.

Answer 6

Tablica haszująca zawsze używa pewnej funkcji działającej na wartości, aby określić, gdzie zostanie zapisana wartość. Słownik (jak sądzę, że masz na myśli) jest bardziej ogólnym terminem i po prostu wskazuje mechanizm wyszukiwania, który może być tablicą asocjacyjną lub może być zaimplementowany przez prostszą strukturę, która nie bierze pod uwagę samej wartości przy określaniu swojej lokalizacji przechowywania.