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.
dictionary
data-structures
language-agnostic
key-value
pochłonęło elysium
źródło
źródło
Odpowiedzi:
Dwa terminy na to samo:
„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.
źródło
Dictionary
w Javie jest przestarzały. Jest to klasa abstrakcyjna, używana przed utworzeniemMap
interfejsu.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%.
źródło
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.
źródło
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:
Pojęcie mapy w dziedzinie informatyki opiera się na matematycznym mapowaniu terminów lingwistycznych , które Oxford Dictionary definiuje jako:
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:
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
Terminologia Crossreferencing Comp Sci z konkretnymi implementacjami
Biblioteka standardowa C ++
map
,multimap
,unordered_map
,unordered_multimap
set
,multiset
,unordered_set
,unordered_multiset
std::find
można skasować element i wykonaj test dla członkostwa warray
,vector
,list
,deque
etc, 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.deque
s 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 ...
źródło
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:
Który zawiera słowa:
Przechodzenie od góry do liścia daje słowo.
źródło
Dictionary
w .Net jest nieuporządkowany.std::map
jest uporządkowane, jego implementacja nie jest określona w standardzie,std::unordered_map
została wprowadzona w c ++ 11, jest zaimplementowana za pomocą skrótustd::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 implementacjistd::map
”, nie mówiąc wprost.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.
źródło
Inne terminy dla tej koncepcji, które są dość powszechne: tablica asocjacyjna i skrót.
źródło
Tak, są takie same, możesz dodać do miksu „Associative Array”.
użycie
Hashtable
lubHash
często odnosi się do implementacji.źródło
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
źródło
Są to dwa różne terminy dla tej samej koncepcji.
Hashtable
aHashMap
także odnoszą się do tej samej koncepcji.źródło
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.
źródło