Jaka jest różnica między hashem a słownikiem?

Hash to wyjątkowo słabo nazwana struktura danych, w której programista pomylił interfejs z implementacją ( i był zbyt leniwy, aby wpisać pełną nazwę, tj. HashTable zamiast uciekać się do skrótu Hash).

Dictionary to „poprawna” nazwa interfejsu (= ADT ), tj. kontener asocjacyjny, który odwzorowuje (zwykle unikalne) klucze na (niekoniecznie unikalne) wartości.

Tablica skrótów jest jedna możliwa implementacja takiego słownika, która zapewnia całkiem dobre parametry dostępu (pod względem czasu wykonywania) i dlatego często jest implementacją domyślną.

Taka implementacja ma dwie ważne właściwości:

1. klucze muszą być ha shable i równość porównywalna .
2. wpisy w słowniku nie pojawiają się w określonej kolejności.

(Aby uzyskać klucz do być hashable oznacza, że możemy obliczyć wartość liczbową z klucza, który jest następnie używany jako indeks w tablicy.)

Istnieją alternatywne implementacje struktury danych słownika, które narzucają uporządkowanie na klawiszach – jest to często nazywane słownikiem posortowanym (i zwykle jest implementowane w kategoriach drzewa wyszukiwania, chociaż istnieją inne wydajne implementacje).

Aby podsumowanie: słownik to narzędzie ADT, które odwzorowuje klucze na wartości. Istnieje kilka możliwych implementacji tego narzędzia ADT, z których jedną jest tablica skrótów . Hash to myląca nazwa, ale w kontekście jest odpowiednikiem słownika zaimplementowanego w postaci tabeli skrótów.

Komentarze

• Aby podać przykład w C ++, standardowe asocjacyjne szablony kontenerów nie mogą być ' implementowane jako skróty, chociaż następny standard będzie zawierał faktycznie tablice skrótów. ' nazywane są unordered_map, aby pokazać, co robią, a nie czym są.
• „poprawne” zgodnie z jaki autorytet? W niektórych językach, takich jak Ruby i Perl, oficjalna – czytaj „poprawna” – nazwa tych struktur to „hash”.
• @nohat: Zwróć uwagę, że używam cudzysłowów. Ponadto wyjaśniłem , dlaczego nazwa jest źle dobrana, prawda? Więc jeśli potrzebujesz autorytetu, powiem, że jest to autorytet teoretycznej policji informatycznej.
• Co ciekawe, w Rubim 1.9 faktycznie niemożliwe jest zaimplementowanie Hash z tablicą mieszającą, ponieważ Ruby 1.9 Hash es zachowuje kolejność wstawiania, podczas gdy tablica skrótów nie. Tak więc w Rubim 1.9 nazwa Hash nie ' nie odzwierciedla już nawet implementacji.
• @hippietrail Mylisz się – po pierwsze, te to opisy obiektywne. W końcu wyjaśniam, dlaczego nazewnictwo jest słabe i błędne (patrz poniżej). „Zbyt leniwy” to z mojej strony licencja artystyczna, ale pozostaje kwestia, że powód skracania nazwy jest nieodłączny, tj. Nie ma powodu, aby używać tutaj krótkiej nazwy poza jej skracaniem. I mylisz się co do „słownika”: jest to po prostu oficjalna nazwa struktury danych. Twoja definicja „słownika” jest błędna w kontekście informatyki, a nazwa wyprzedza Pythona o dziesięciolecia.

„Słownik” to nazwa pojęcia. Możliwa implementacja to tablica haszująca.

Komentarze

• Hash to także ADT. HashTable to implementacja Hash
• @Sairam. Myślę, że jest on dużo bardziej powszechny w przypadku ' hash ' funkcja skrótu zamiast tabeli skrótów.
• @jk Właściwie " hash " jest wynikiem zastosowania " funkcja skrótu / algorytm " do niektórych danych wejściowych. " tabela skrótów " lub " mapa skrótów " omehoe odnosi się i haszuje obiekt do jakiegoś obiektu (obiekt w formie ogólnej, nie ograniczonej do OOP)
• Istnieją języki, które używają ' Hash ' w celu odniesienia się do struktury typu słownikowego, a nie tylko do operacji funkcji skrótu. Na przykład Ruby .

Słownik to zbiorcze określenie każdej implementacji struktury danych używanej do szybkiego wyszukiwania / wstawiania. Można to osiągnąć / zaimplementować za pomocą różnych struktur danych, takich jak tablica skrótów, listy pomijane, drzewo rb itp. Tablica skrótów to specyficzna struktura danych przydatna do wielu celów, w tym do implementacji słownika.

Komentarze

• Hash to także ADT. Czy jest jakaś szczególna różnica między Hash a Dictionary ADT?
• @Sairam: Nie, hash jest wynikiem pewnego rodzaju algorytmu (funkcja skrótu).

słownik używa klucza do odwołaj się do wartości bezpośrednio w tablicy asocjacyjnej .

ie (KEY => VALUE)

hash jest częściej opisywany jako tabela skrótów , która używa funkcji skrótu do obliczenia pozycja w pamięci (lub łatwiej tablicy), w której będzie znajdować się wartość. Hash pobierze KEY jako dane wejściowe i poda wartość jako dane wyjściowe. Następnie podłącz tę wartość do pamięci lub indeksu tablicy.

tj. KEY => HASH FUNCTION => VALUE

Myślę, że jedna jest bezpośrednia, a druga isn „t. Funkcje skrótu mogą też nie być doskonałe i czasami mogą zawierać indeks odwołujący się do niewłaściwej wartości. Ale można to poprawić.

Najlepsze miejsce do wyszukania: Wikipedia ( tablica asocjacyjna i tablica skrótów )