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

data-structures hashing dictionary difference hashtable Sairam
źródło

Odpowiedzi:

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:

  1. klucze muszą być haszowalne i równe .
  2. 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