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

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

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.

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

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.

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

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.

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.

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

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

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

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

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

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.