Mam pytanie z hash_map
a map
w C ++. Rozumiem, że map
jest w STL, ale hash_map
nie jest to standard. Jaka jest różnica między nimi?
117
Są realizowane na bardzo różne sposoby.
hash_map
( unordered_map
w TR1 i Boost; użyj ich zamiast tego) użyj tablicy hash, w której klucz jest zaszyfrowany do gniazda w tabeli, a wartość jest przechowywana na liście powiązanej z tym kluczem.
map
jest zaimplementowany jako zbalansowane drzewo wyszukiwania binarnego (zwykle drzewo czerwono-czarne).
unordered_map
Powinno dać nieco lepszą wydajność dostępu do znanych elementów kolekcji, ale map
będzie mieć dodatkowe użyteczne cechy (np jest on przechowywany w posortowanych, który umożliwia przechodzenie od początku do końca). unordered_map
będzie szybszy przy wstawianiu i usuwaniu niż plik map
.
hash_map
był powszechnym rozszerzeniem dostarczanym przez wiele implementacji bibliotek. Właśnie dlatego zmieniono jego nazwę na,unordered_map
gdy został dodany do standardu C ++ jako część TR1. mapa jest generalnie implementowana ze zrównoważonym drzewem binarnym, takim jak czerwono-czarne drzewo (implementacje są oczywiście różne).hash_map
iunordered_map
są generalnie implementowane z tablicami mieszania. W ten sposób porządek nie jest utrzymywany.unordered_map
wstaw / usuń / zapytanie będzie równe O (1) (stały czas), gdzie mapa będzie równa O (log n), gdzie n to liczba elementów w strukturze danych. Więcunordered_map
jest szybszy, a jeśli nie dbasz o kolejność elementów, powinieneś mieć pierwszeństwomap
. Czasami chcesz zachować porządek (uporządkowany według klucza) i do tegomap
byłby wybór.źródło
Niektóre z kluczowych różnic dotyczą wymagań dotyczących złożoności.
A
map
wymagaO(log(N))
czasu na wstawianie i znajdowanie operacji, ponieważ jest zaimplementowany jako struktura danych Czerwono-Czarne Drzewo .An
unordered_map
wymaga „średniego” czasuO(1)
wstawiania i znajdowania, ale dopuszcza się czas najgorszego przypadku wynoszącyO(N)
. Dzieje się tak, ponieważ jest zaimplementowany przy użyciu struktury danych Hash Table .Zwykle
unordered_map
będzie więc szybszy, ale w zależności od kluczy i funkcji skrótu, które przechowujesz, może się znacznie pogorszyć.źródło
Specyfikacja C ++ nie mówi dokładnie, jakiego algorytmu należy użyć dla kontenerów STL. Jednak nakłada pewne ograniczenia na ich wydajność, co wyklucza użycie tabel skrótów dla
map
i innych kontenerów asocjacyjnych. (Najczęściej są implementowane z czerwonymi / czarnymi drzewami). Te ograniczenia wymagają lepszej wydajności w najgorszym przypadku dla tych kontenerów, niż mogą zapewnić tabele skrótów.Jednak wiele osób naprawdę chce tabel skrótów, więc asocjacyjne kontenery STL oparte na skrótach są od lat powszechnym rozszerzeniem. W konsekwencji dodali
unordered_map
i to do późniejszych wersji standardu C ++.źródło
map
jest generalnie zrównoważone drzewo btree spowodowane użyciemoperator<()
jako środka określającego lokalizację.map
jest zaimplementowana zbalanced binary search tree
(zwykle arb_tree
), ponieważ cały element członkowskibalanced binary search tree
jest posortowany, podobnie jak mapa;hash_map
jest implementowana zhashtable
.S ponieważ wszystkie elementy członkowskie whashtable
są nieposortowane, więchash_map(unordered_map)
nie są sortowane.hash_map
nie jest standardową biblioteką c ++, ale teraz została zmieniona naunordered_map
(możesz pomyśleć o zmianie nazwy) i staje się standardową biblioteką c ++ od c ++ 11 zobacz to pytanie Różnica między hash_map i unordered_map? aby uzyskać więcej szczegółów.Poniżej podam podstawowy interfejs z kodu źródłowego, w jaki sposób implementowana jest mapa dwóch typów.
mapa:
Poniższy kod ma na celu pokazanie, że mapa jest tylko opakowaniem jakiegoś elementu
balanced binary search tree
, prawie cała jego funkcja to po prostu wywołaniebalanced binary search tree
funkcji.hash_map
:hash_map
jest zaimplementowany, zhashtable
którego struktura wygląda mniej więcej tak:W poniższym kodzie podam główną część
hashtable
, a następnie podamhash_map
.Tak jak
map's
tylko członek jestrb_tree
,hash_map's
jedynym członkiem jesthashtable
. To główny kod, jak poniżej:Poniższy obraz pokazuje, kiedy hash_map ma 53 segmenty i wstawia pewne wartości, jest to struktura wewnętrzna.
Poniższy obrazek pokazuje pewną różnicę między mapą a hash_map (unordered_map), obraz pochodzi z Jak wybrać między mapą a unordered_map? :
źródło
Nie wiem, co daje, ale funkcja hash_map zajmuje więcej niż 20 sekund, aby wyczyścić () 150 000 kluczy całkowitych bez znaku i wartości zmiennoprzecinkowych. Po prostu uruchamiam i czytam kod kogoś innego.
W ten sposób zawiera hash_map.
Przeczytałem to tutaj https://bytes.com/topic/c/answers/570079-perfomance-clear-vs-swap
mówiąc, że clear () jest rzędem O (N). To dla mnie bardzo dziwne, ale tak właśnie jest.
źródło