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

46

Jaka jest różnica między Hashi Dictionary?

Pochodząc ze scenariusza, czuję, że są do siebie podobne, ale chciałem znaleźć dokładne różnice. Googling niewiele mi pomógł.

— Sairam
źródło

92

Hashjest wyjątkowo źle nazwaną strukturą danych, w której programista pomylił interfejs z implementacją ( i był zbyt leniwy, aby napisać pełną nazwę, tzn. HashTablezamiast tego używał skrótu Hash).

Dictionaryto „poprawna” nazwa interfejsu (= ADT ), tj. kontener asocjacyjny odwzorowujący (zwykle unikatowy) klucze na (niekoniecznie unikatowe) wartości.

Tabela skrótów jest jedną z możliwych implementacji takiego słownika, która zapewnia dość dobrą charakterystykę dostępu (pod względem czasu działania) i dlatego często jest domyślną implementacją.

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

klucze muszą być haszowalne i równe .
wpisy nie pojawiają się w słowniku w określonej kolejności.

(Aby klucz mógł być haszowalny, oznacza to, ż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łownikowych, które narzucają porządek na klawiszach - często nazywane są słownikiem posortowanym (i zwykle są implementowane w kategoriach drzewa wyszukiwania, chociaż istnieją inne wydajne implementacje).

Podsumowując: słownik to narzędzie ADT, które mapuje klucze na wartości. Istnieje kilka możliwych implementacji tego narzędzia ADT, z których jedna to tablica skrótów . Hashjest mylące, ale w kontekście jest równoważne słownikowi, który jest implementowany w postaci tabeli skrótów.

— Konrad Rudolph
źródło

4

Aby podać przykład w C ++, standardowych asocjacyjnych szablonów kontenerów nie można zaimplementować jako skrótów, chociaż następny standard będzie zawierał tabele skrótów. Są powołani, unordered_mapaby pokazać, co robią, a nie czym są.

— David Thornley,

6

„Poprawne” według jakiego organu? W niektórych językach, takich jak Ruby i Perl, oficjalna nazwa „poprawna” - dla tych struktur to „hash”.

— nohat

11

@ nohat: Zwróć uwagę na moje stosowanie cytatów. Co więcej, nie wyjaśnił, dlaczego nazwa jest źle wybrany, nie ma ja? Więc jeśli potrzebujesz autorytetu, powiem, że to autorytet teoretycznej policji informatycznej.

— Konrad Rudolph

9

Co ciekawe, w Ruby 1.9 nie jest możliwe zaimplementowanie Hashklasy z tabelą skrótów, ponieważ Ruby 1.9 Hashzachowuje kolejność wstawiania, podczas gdy tabela skrótów nie. Tak więc w Ruby 1.9 nazwa Hashnie odzwierciedla już nawet implementacji.

— Jörg W Mittag

7

@hippietrail Mylisz się - po pierwsze, są to obiektywne opisy. W końcu kwalifikuję się, dlaczego nazywanie jest złe i niewłaściwe (patrz poniżej). „Zbyt leniwy” jest z mojej strony licencją artystyczną, ale chodzi o to, że powód skrócenia nazwy jest nieodłączny, tzn. Nie ma powodu, aby używać tutaj krótkiej nazwy poza skracaniem nazwy. I mylisz się co do „słownika”: to po prostu oficjalna nazwa struktury danych. Twoja definicja „słownika” jest błędna w kontekście informatyki, a nazwa poprzedza Python o dekady.

— Konrad Rudolph

8

„Słownik” to nazwa tego pojęcia. Możliwe jest wdrożenie hashtable.

— dan_waterworth
źródło

1

Hash jest również ADT. HashTable jest implementacją skrótu

— Sairam

3

@Sairam Myślę, że o wiele bardziej powszechne jest, że „hash” oznacza raczej funkcję skrótu niż tablicę skrótów.

— jk.

@ jk W rzeczywistości „skrót” jest wynikiem zastosowania „funkcji / algorytmu skrótu” do niektórych danych wejściowych. Oomehoe „tablicy skrótów” lub „mapy skrótów” odnosi się do obiektu, który można haszować, do jakiegoś obiektu (obiekt w formie ogólnej, nie ograniczonej do OOP)

— John

Istnieją języki, które używają „Hash” w odniesieniu do struktury typu słownikowego, a nie tylko do operacji funkcji skrótu. Na przykład Ruby .

— Sean Burton

7

Słownik to zbiorowy termin określający dowolną implementację struktury danych używaną do szybkiego wyszukiwania / wstawiania. Można to osiągnąć / wdrożyć za pomocą różnych struktur danych, takich jak tablica skrótów, listy pominięć, drzewo rb itp. Tablica skrótów to specjalna struktura danych przydatna do wielu celów, w tym do implementacji słownika.

— aufather
źródło

Hash jest również ADT. Czy jest jakaś konkretna różnica między Hash a Dictionary ADT?

— Sairam

2

@Sairam: Nie, skrót jest wynikiem działania pewnego rodzaju algorytmu (funkcji skrótu).

5

Słownika wykorzystuje klucz do referencyjnych wartości bezpośrednio wewnątrz z tablicy asocjacyjnej .

to znaczy (KEY => VALUE)

Mieszania jest często opisywany jako tabeli mieszania , który wykorzystuje funkcję mieszania do obliczania położenia w pamięci (lub więcej łatwo macierzy), w której wartość będzie. Hash pobierze KEY jako dane wejściowe i da wartość jako wynik. Następnie podłącz tę wartość do indeksu pamięci lub tablicy.

to znaczy KEY => HASH FUNCTION => VALUE

Myślę, że jedno jest bezpośrednie, a drugie nie. Funkcje skrótu również mogą nie być idealne i mogą czasami zapewniać indeks odwołujący się do niewłaściwej wartości. Ale można to poprawić.

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

— Ross
źródło