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

197

Wiem, że mapa to struktura danych, która mapuje klucze na wartości. Czy słownik nie jest taki sam? Jaka jest różnica między mapą a słownikiem 1 ?


1. Nie pytam o to, jak są zdefiniowane w języku X lub Y (który wydaje się być tym, o co zwykle pytają ludzie tutaj na SO), chcę wiedzieć, jaka jest ich różnica w teorii.

pochłonęło elysium
źródło
Świetne pytanie!
NoName,

Odpowiedzi:

259

Dwa terminy na to samo:

  • „Mapa” jest używana przez Javę, C ++
  • „Słownik” jest używany przez .Net, Python
  • „Tablica asocjacyjna” jest używana przez PHP

„Mapa” jest poprawnym terminem matematycznym, ale można go uniknąć, ponieważ ma osobne znaczenie w programowaniu funkcjonalnym .

Niektóre języki używają jeszcze innych terminów („Object” w Javascripcie, „Hash” w Ruby, „Table” w Lua) , ale wszystkie te mają również inne znaczenie w programowaniu, więc bym ich unikał.

Zobacz tutaj, aby uzyskać więcej informacji.

BlueRaja - Danny Pflughoeft
źródło
7
Czy JAVA nie ma zarówno mapy, jak i słownika? Jakie są tam różnice?
vivek_jonam
35
@vivek_jonam: Dictionaryw Javie jest przestarzały. Jest to klasa abstrakcyjna, używana przed utworzeniem Mapinterfejsu.
BlueRaja - Danny Pflughoeft
7
Wiem, że pytanie jest niezależne od języka, więc jest to prawidłowa odpowiedź, ale skończyłem tutaj, szukając powodu, dla którego Java ma oba, więc ten komentarz był dla mnie naprawdę idealny.
GrandOpener,
1
„stół” jest używany w lua.
Deduplicator
1
jest również nieco myląco nazywany „Obiektem” w JSON (z przyczyn historycznych związanych z JavaScriptem)
Aprillion
20

Jeden to starszy termin dla drugiego. Zazwyczaj termin „słownik” był używany przed terminem matematycznym „mapa”. Ponadto słowniki mają zazwyczaj kluczowy ciąg, ale nie wszędzie tak jest w 100%.

Edwin Buck
źródło
9

Moje 2 centy.

Słownik to klasa abstrakcyjna w Javie, natomiast Map to interfejs. Ponieważ Java nie obsługuje wielu dziedziczeń, jeśli klasa rozszerza słownik, nie może rozszerzać żadnej innej klasy.

Dlatego wprowadzono interfejs mapy.

Klasa Dictionary jest przestarzała i preferowane jest użycie Map.

Nishit
źródło
9

Odpowiedź na to pytanie jest skomplikowana, ponieważ programiści zauważyli, że terminy mają bardziej szczegółowe znaczenie w określonych językach lub systemach, których używali, ale pytanie wymaga porównania agnostycznego z językiem „teoretycznie”, co mam na myśli w terminologii obliczeniowej .

Wyjaśnienie terminologii

Słownik informatyki Oxford University wymienia:

słowniki dowolną strukturę danych reprezentującą zestaw elementów, które mogą obsługiwać wstawianie i usuwanie elementów, a także testować członkostwo

  • Na przykład mamy zestaw elementów {A, B, C, D ...}, które udało nam się wstawić i możemy rozpocząć usuwanie, i możemy zapytać „czy C jest obecny?” .

Pojęcie mapy w dziedzinie informatyki opiera się na matematycznym mapowaniu terminów lingwistycznych , które Oxford Dictionary definiuje jako:

mapowanie Operacja, która wiąże każdy element danego zestawu (domeny) z jednym lub większą liczbą elementów drugiego zestawu (zakresu).

  • Jako taka, struktura danych mapy zapewnia sposób przejścia od elementów danego zestawu - znane są „ klucze ” na mapie, do jednego lub większej liczby elementów w drugim zestawie - znanych jako powiązane „ wartości ”.
  • W „... lub więcej elementów w drugim secie” aspekt może być obsługiwany za pomocą wdrożenia jest dwa odrębne sposób:
    • Wiele implementacji map wymusza unikalność kluczy i zezwala na powiązanie każdego klucza z jedną wartością, ale ta wartość może być samą strukturą danych zawierającą wiele wartości prostszego typu danych, np. {{1, {"one" , „ichi”}, {2, {„two”, „ni”}}} ilustrują wartości składające się z par ciągów.
    • Inne implementacje map pozwalają na duplikowanie kluczy przy każdym mapowaniu na te same lub różne wartości - co funkcjonalnie spełnia warunek „kojarzy… każdy element [klucz] ... z ... więcej [więcej niż jednym] elementem [wartość]”. Na przykład: {{1, „one”}, {1, „ichi”}, {2, „two”}, {2, „ni”}}.

Słownik i mapa skontrastowane

Tak więc, używając powyższej ścisłej terminologii Comp Sci, słownik jest mapą tylko wtedy, gdy interfejs obsługuje dodatkowe operacje, które nie są wymagane dla każdego słownika:

  • możliwość przechowywania elementów z odrębnymi kluczowymi i wartościowymi komponentami

  • możliwość odzyskania wartości podanych tylko kluczem

Trywialny zwrot akcji:

  • interfejs mapy może nie obsługiwać bezpośrednio testu tego, czy para {klucz, wartość} znajduje się w kontenerze, co jest pedantycznie wymogiem słownika, w którym elementami są pary {klucz, wartość}; mapa może nawet nie mieć funkcji do testowania klucza, ale w najgorszym przypadku można sprawdzić, czy próba odzyskania wartości według klucza się powiedzie, czy nie, a jeśli to ważne, możesz sprawdzić, czy klucz odzyskał oczekiwaną wartość.

Komunikuj się jednoznacznie ze swoimi odbiorcami

⚠ Mimo wszystko powyższego, jeśli używasz słownika w ścisłym znaczeniu informatyki wyjaśnionym powyżej, nie spodziewaj się, że publiczność początkowo pójdzie za tobą lub nie zrobi na tobie wrażenia, gdy podzielisz się i bronisz terminologii. Inne odpowiedzi na to pytanie (i ich opinie) pokazują, jak prawdopodobne jest, że „słownik” będzie równoznaczny z „mapą” w odczuciu większości programistów. Spróbuj wybrać terminologię, która będzie szerzej i jednoznacznie zrozumiana: np

  • kontener asocjacyjny : dowolny kontener przechowujący pary klucz / wartość z wyszukiwaniem wartości i usuwaniem według klucza
  • mapa hash : implementacja tabeli hash powiązanego kontenera
  • zestaw skrótów wymuszający unikalne klucze : implementacja tablicy hashowej przechowującej element / wartości słownika bez traktowania ich jako zawierających odrębne składniki klucza / wartości, w których nie można wstawić duplikatów elementów
  • Bilansowa mapa drzewa binarnego obsługująca duplikat klucza : ...

Terminologia Crossreferencing Comp Sci z konkretnymi implementacjami

Biblioteka standardowa C ++

  • mapy: map, multimap, unordered_map,unordered_multimap
  • inne słowniki: set, multiset, unordered_set,unordered_multiset
  • Uwaga: z iteratorów lub std::findmożna skasować element i wykonaj test dla członkostwa w array, vector, list, dequeetc, ale interfejsy kontenerów nie bezpośrednio wspierać że ponieważ znalezienie element jest spektakularnie nieskuteczne w O (n), w niektórych przypadkach wkładka / skasowaniem jest nieefektywne, a wspieranie tych operacji podważa celowo ograniczony interfejs API, jaki sugeruje kontener - np. deques powinny obsługiwać tylko usuwanie / pop z przodu iz tyłu, a nie pod względem niektórych kluczy. Konieczność wykonania większej pracy w kodzie w celu uporządkowania wyszukiwania delikatnie zachęca programistę do przejścia do struktury danych kontenera z bardziej wydajnym wyszukiwaniem.

... może dodać inne języki później / możesz edytować w ...

Tony Delroy
źródło
3

Zazwyczaj zakładam, że mapa jest wspierana przez tablicę skrótów; oznacza nieuporządkowany sklep. Słowniki oznaczają zamówiony sklep.

Istnieje słownik oparty na drzewie o nazwie Trie .

W Lisp może to wyglądać tak:

(a (n (d t)) n d )

Który zawiera słowa:

  • za
  • i
  • Mrówka
  • na
  • ogłoszenie

Przechodzenie od góry do liścia daje słowo.

Paul Nathan
źródło
4
Dictionaryw .Net jest nieuporządkowany.
BlueRaja - Danny Pflughoeft
2
Słowniki kakaowe są również nieuporządkowane.
Ken
C ++ std::mapjest uporządkowane, jego implementacja nie jest określona w standardzie, std::unordered_mapzostała wprowadzona w c ++ 11, jest zaimplementowana za pomocą skrótu
Harald Scheirich
3
@HaraldScheirich - Podczas gdy standard C ++ nie mówi konkretnie „powinieneś użyć czerwono-czarnego drzewa do implementacji std::map”, spróbuj użyć czegokolwiek innego. Drzewo AVL nie będzie działać; koszty wstawienia nie spełniają standardu. Hash nie zadziała; skrót jest nieuporządkowany i dlatego nie spełnia standardu. Standard w zasadzie mówi „powinieneś użyć czerwono-czarnego drzewa do implementacji std::map”, nie mówiąc wprost.
David Hammen,
+1. Chociaż słowniki są nieuporządkowane na wielu platformach, słowo to oznacza porządek. Termin mapa bardziej mi się podoba.
nawfal
2

Niezupełnie to samo. Mapy są podzbiorem słownika. Słownik jest tutaj definiowany jako mający funkcje wstawiania, usuwania i wyszukiwania. Mapa używana przez Javę (zgodnie z tym ) jest słownikiem z wymaganiem, aby klucze mapowane na wartości były ściśle mapowane jako funkcja jeden do jednego. Słownik może mieć więcej niż jedną mapę klucza do jednej wartości lub jedną mapę klucza do kilku wartości (np. Tworzenie łańcucha w hasthtable), np. Wyszukiwania hashtagów na Twitterze.

Jako bardziej „rzeczywisty” przykład, wyszukiwanie słowa w słowniku może dać nam wiele definicji tego samego słowa, a gdy znajdziemy pozycję wskazującą na inny wpis (patrz inne słowo), kilka słów dla tej samej listy definicji. W prawdziwym świecie mapy są znacznie szersze, co pozwala nam mieć lokalizacje dla nazw lub nazw dla współrzędnych, ale także możemy znaleźć najbliższego sąsiada lub inne atrybuty (populacje itp.), Więc IMHO może być argumentem za większym rozszerzeniem typ mapy może mieć implementacje oparte na grafie, ale najlepiej byłoby zawsze zakładać tylko parę klucz-wartość, zwłaszcza że najbliższy sąsiad i inne atrybuty wartości mogą być tylko elementami danych wartości.

Mapy Java, pomimo wymogu jeden do jednego, mogą implementować coś bardziej jak słownik uogólniony, jeśli wartość jest uogólniona jako sama kolekcja lub jeśli wartości są jedynie odniesieniami do kolekcji przechowywanych gdzie indziej.

Pamiętaj, że opiekunowie Java nie są opiekunami definicji ADT i że decyzje dotyczące Javy dotyczą konkretnie Javy.

użytkownik6585083
źródło
1

Inne terminy dla tej koncepcji, które są dość powszechne: tablica asocjacyjna i skrót.

Hank Gay
źródło
1
Hash nie ma z tym nic wspólnego. Jest to metoda szybkiego wykrywania, czy obiekty są różne. Zastanawiasz się nad skrótem, który używa skrótu do wykonania zadania Mapa / Słownik.
DJClayworth
5
@DJClayworth Nie, wiele języków programowania nazywa te rzeczy haszowaniem. Zobacz Ruby . Nie zaprojektowałem go i nie nazwałbym tego tak, ale nie strzelaj do posłańca.
Hank Gay
1

Tak, są takie same, możesz dodać do miksu „Associative Array”.

użycie Hashtable lub Hashczęsto odnosi się do implementacji.

OscarRyz
źródło
1

na czysto teoretycznym poziomie.

Słownik to wartość, której można użyć do zlokalizowania połączonej wartości. Mapa to wartość, która zawiera instrukcje dotyczące lokalizowania innych wartości

wszystkie kolekcje, które pozwalają na dostęp nieliniowy (tj. tylko pierwsze lub ostatnie) są Mapą, ponieważ nawet prosta Tablica ma indeks, który mapuje na prawidłową wartość. Więc chociaż słownik jest rodzajem mapy, mapy mają znacznie szerszy zakres możliwych funkcji.

W praktyce jest to zwykle funkcja mapowania, która definiuje nazwę, więc HashMap to zmapowana struktura danych, która wykorzystuje algorytm mieszający do łączenia klucza z wartością, gdzie jako Słownik nie określa, w jaki sposób klucze są powiązane z wartością więc może być przechowywany za pośrednictwem połączonej listy, drzewa lub dowolnego innego algorytmu. od końca użytkowania zwykle nie przejmujesz się tym, jaki algorytm działa, więc używasz ogólnego słownika i przechodzisz do jednej z pozostałych struktur tylko wtedy, gdy potrzebujesz wymyślić typ algorytmu

MikeT
źródło
-2

Są to dwa różne terminy dla tej samej koncepcji.
Hashtablea HashMaptakże odnoszą się do tej samej koncepcji.

SLaks
źródło
3
W rzeczywistości Hashtable / Hashmap implikują konkretną implementację w ich nazwie (w porównaniu z drzewem zrównoważonym, które jest używane na przykład w std :: map C ++).
Joe
Ogólnie rzecz biorąc, nie powinieneś przejmować się implementacją. (Z wyjątkiem powodów związanych z wydajnością) Nie zawsze jest to prawdą; patrz na przykład .Net.
SLaks
-2

Główną różnicą jest to, że mapa wymaga, aby wszystkie wpisy (para wartość i klucz) miały unikalny klucz. Jeśli wystąpią kolizje, tj. Gdy nowy wpis ma taki sam klucz jak wpis już w kolekcji, wymagana jest obsługa kolizji.

Zwykle radzimy sobie z kolizjami za pomocą oddzielnego łączenia . Lub sondowanie liniowe .

Słownik pozwala na wielokrotne wpisy mają być powiązane z tym samym kluczem.

Kiedy mapa wdrożyła oddzielne tworzenie łańcuchów, zwykle przypomina słownik.

Bondo Kalombo
źródło