map vs. hash_map w C ++

117

Mam pytanie z hash_mapa mapw C ++. Rozumiem, że mapjest w STL, ale hash_mapnie jest to standard. Jaka jest różnica między nimi?

skydoor
źródło

Odpowiedzi:

133

Są realizowane na bardzo różne sposoby.

hash_map( unordered_mapw 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_mapPowinno dać nieco lepszą wydajność dostępu do znanych elementów kolekcji, ale mapbędzie mieć dodatkowe użyteczne cechy (np jest on przechowywany w posortowanych, który umożliwia przechodzenie od początku do końca). unordered_mapbędzie szybszy przy wstawianiu i usuwaniu niż plik map.

Joe
źródło
7
Nie do końca zgadzam się z tobą co do wydajności. Na wydajność ma wpływ szereg parametrów i skarciłbym każdego programistę używającego mapy unordered_map za zaledwie 10 wpisów, ponieważ „jest szybszy”. Najpierw martw się o interfejs / funkcjonalność, później wydajność.
Matthieu M.
24
Cóż, tak, dobrze jest zrozumieć swój problem. Do pewnych rzędów wielkości jest to prawdopodobnie zmywanie pod względem wydajności, ale ważne jest, aby zrozumieć charakterystykę działania obu pojemników, ponieważ różnią się one na różne sposoby w miarę zwiększania się ilości danych.
Joe
7
Co ciekawe, właśnie zamieniłem std :: map na boost :: unordered_map w aplikacji, w której wykonuję wiele losowych wyszukiwań, ale także iteruję po wszystkich klawiszach na mapie. Zaoszczędziłem dużo czasu na wyszukiwaniu, ale odzyskałem go dzięki iteracjom, więc wróciłem do mapy i szukam innych sposobów na poprawę wydajności aplikacji.
Erik Garrison,
4
@ErikGarrison Jeśli korzystasz z dostępu swobodnego i iteracji dużo częściej niż wstawiasz i usuwasz elementy, możesz mieć swoje obiekty zarówno w drzewie, jak i w hash_map (przechowując wskaźnik lub jeszcze lepiej shared_ptr, do tych samych obiektów w obu przypadku, gdy korzystałeś z rzeczywistych instancji). Będziesz wtedy mieć czas dostępu O (1) czas do mapy hash_map i czas iteracji O (n) przez mapę. Oczywiście musisz pamiętać o dodawaniu i usuwaniu wskaźników z obu za każdym razem. Możesz łatwo napisać niestandardową klasę kontenera, która (prawdopodobnie również ją szablon), która będzie hermetyzować to zachowanie dla Ciebie.
sprite
2
@ErikGarrison Oczywiście, jeśli spróbujesz tej metody, zapłacisz niewielką dodatkową przestrzeń. Ponieważ jednak używałbyś wskaźników, nie powinno to być zbyt wiele. Jeśli naprawdę chcesz, możesz przejść za burtę i napisać własną implementację AVL i użyć wskaźnika węzła jako typu danych w mapie hash_map, co da ci dostęp w czasie O (1) do węzła w drzewie, z którego będziesz mógł iterować liniowo, gdziekolwiek potrzebujesz. Oczywiście wymagałoby to sporo kodowania i nie jestem pewien, czy to się opłaci, chyba że będziesz musiał dużo iterować zi do lokalizacji o swobodnym dostępie.
sprite
35

hash_mapbył powszechnym rozszerzeniem dostarczanym przez wiele implementacji bibliotek. Właśnie dlatego zmieniono jego nazwę na, unordered_mapgdy 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_mapi unordered_mapsą generalnie implementowane z tablicami mieszania. W ten sposób porządek nie jest utrzymywany. unordered_mapwstaw / 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ęc unordered_mapjest szybszy, a jeśli nie dbasz o kolejność elementów, powinieneś mieć pierwszeństwo map. Czasami chcesz zachować porządek (uporządkowany według klucza) i do tego mapbyłby wybór.

janglin
źródło
9
Chciałbym zwrócić uwagę, że hashmap ma najgorszy przypadek dostępu O (N), gdy kolizje są prawdopodobne (zły skrót fcn, zbyt wysoki współczynnik ładowania itp.)
KitsuneYMG
Dobry hashmap ma oczekiwany koszt O (1), nie ma gwarancji, że tak będzie. Złe hashmapy mogą mieć oczekiwany koszt, który nie jest równy O (1).
Wyraźniej
14

Niektóre z kluczowych różnic dotyczą wymagań dotyczących złożoności.

  • A mapwymaga O(log(N))czasu na wstawianie i znajdowanie operacji, ponieważ jest zaimplementowany jako struktura danych Czerwono-Czarne Drzewo .

  • An unordered_mapwymaga „średniego” czasu O(1)wstawiania i znajdowania, ale dopuszcza się czas najgorszego przypadku wynoszący O(N). Dzieje się tak, ponieważ jest zaimplementowany przy użyciu struktury danych Hash Table .

Zwykle unordered_mapbędzie więc szybszy, ale w zależności od kluczy i funkcji skrótu, które przechowujesz, może się znacznie pogorszyć.

R Samuel Klatchko
źródło
4

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 mapi 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_mapi to do późniejszych wersji standardu C ++.

Warren Young
źródło
W rzeczywistości został dodany w TR1 (std :: tr1 :: unordered_map), a nie w C ++ 0x
Terry Mahaffey
Pomyślałem, że powodem mapjest generalnie zrównoważone drzewo btree spowodowane użyciem operator<()jako środka określającego lokalizację.
KitsuneYMG
@kts: Czy jakiekolwiek implementacje STL faktycznie używają B-drzewa?
bk1e
Z technicznego punktu widzenia wszystkie drzewa wyszukiwania binarnego to drzewa b (1-2 drzewo). Biorąc to pod uwagę, nie znam żadnego STL, który używa czegoś innego niż czerwony / czarny
KitsuneYMG
@ bk1e „Właściwe” B-drzewa są wyjątkowo przydatne w bazach danych, w których potrzebne są „grube” węzły drzew, które są dobrze dopasowane do stron dysku. OTOH, nie jest to zbyt przydatne w "płaskim" modelu pamięci używanym w "normalnych" programach - wszystkie implementacje STL, które znam, używają czerwono-czarnych drzew.
Branko Dimitrijevic
3

mapjest zaimplementowana z balanced binary search tree(zwykle a rb_tree), ponieważ cały element członkowski balanced binary search treejest posortowany, podobnie jak mapa;

hash_mapjest implementowana z hashtable.S ponieważ wszystkie elementy członkowskie w hashtablesą nieposortowane, więc hash_map(unordered_map)nie są sortowane.

hash_mapnie jest standardową biblioteką c ++, ale teraz została zmieniona na unordered_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łanie balanced binary search treefunkcji.

template <typename Key, typename Value, class Compare = std::less<Key>>
class map{
    // used for rb_tree to sort
    typedef Key    key_type;

    // rb_tree node value
    typedef std::pair<key_type, value_type> value_type;

    typedef Compare key_compare;

    // as to map, Key is used for sort, Value used for store value
    typedef rb_tree<key_type, value_type, key_compare> rep_type;

    // the only member value of map (it's  rb_tree)
    rep_type t;
};

// one construct function
template<typename InputIterator>
map(InputIterator first, InputIterator last):t(Compare()){
        // use rb_tree to insert value(just insert unique value)
        t.insert_unique(first, last);
}

// insert function, just use tb_tree insert_unique function
//and only insert unique value
//rb_tree insertion time is : log(n)+rebalance
// so map's  insertion time is also : log(n)+rebalance 
typedef typename rep_type::const_iterator iterator;
std::pair<iterator, bool> insert(const value_type& v){
    return t.insert_unique(v);
};

hash_map:

hash_mapjest zaimplementowany, z hashtablektórego struktura wygląda mniej więcej tak:

wprowadź opis obrazu tutaj

W poniższym kodzie podam główną część hashtable, a następnie podam hash_map.

// used for node list
template<typename T>
struct __hashtable_node{
    T val;
    __hashtable_node* next;
};

template<typename Key, typename Value, typename HashFun>
class hashtable{
    public:
        typedef size_t   size_type;
        typedef HashFun  hasher;
        typedef Value    value_type;
        typedef Key      key_type;
    public:
        typedef __hashtable_node<value_type> node;

        // member data is buckets array(node* array)
        std::vector<node*> buckets;
        size_type num_elements;

        public:
            // insert only unique value
            std::pair<iterator, bool> insert_unique(const value_type& obj);

};

Tak jak map'stylko członek jest rb_tree, hash_map'sjedynym członkiem jest hashtable. To główny kod, jak poniżej:

template<typename Key, typename Value, class HashFun = std::hash<Key>>
class hash_map{
    private:
        typedef hashtable<Key, Value, HashFun> ht;

        // member data is hash_table
        ht rep;

    public:
        // 100 buckets by default
        // it may not be 100(in this just for simplify)
        hash_map():rep(100){};

        // like the above map's insert function just invoke rb_tree unique function
        // hash_map, insert function just invoke hashtable's unique insert function
        std::pair<iterator, bool> insert(const Value& v){
                return t.insert_unique(v);
        };

};

Poniższy obraz pokazuje, kiedy hash_map ma 53 segmenty i wstawia pewne wartości, jest to struktura wewnętrzna.

wprowadź opis obrazu tutaj

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? :

wprowadź opis obrazu tutaj

Jayhello
źródło
1

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.

#include "StdAfx.h"
#include <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.

BoBoDev
źródło