map vs. hash_map w C ++

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?

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.

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.

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

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

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:

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.

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

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.