webentwicklung-frage-antwort-db.com.de

map vs. hash_map in C ++

Ich habe eine Frage mit hash_map und map in C++. Ich verstehe, dass map in AWL ist, aber hash_map ist kein Standard. Was ist der Unterschied zwischen den beiden?

110
skydoor

Sie werden auf sehr unterschiedliche Weise implementiert.

hash_map (unordered_map in TR1 und Boost; Verwenden Sie stattdessen diese.) Verwenden Sie eine Hash-Tabelle, bei der der Schlüssel mit einem Slot in der Tabelle gehasht und der Wert in einer mit diesem Schlüssel verknüpften Liste gespeichert wird.

map wird als ausgeglichener binärer Suchbaum (normalerweise ein rot/schwarzer Baum) implementiert.

Ein unordered_map sollte eine etwas bessere Leistung für den Zugriff auf bekannte Elemente der Sammlung liefern, aber ein map weist zusätzliche nützliche Merkmale auf (z. B. wird es in sortierter Reihenfolge gespeichert, wodurch ein Durchlaufen von Anfang bis Ende möglich ist). unordered_map ist beim Einfügen und Löschen schneller als ein map.

129
Joe

hash_map War eine verbreitete Erweiterung, die von vielen Bibliotheksimplementierungen bereitgestellt wurde. Genau aus diesem Grund wurde es in unordered_map Umbenannt, als es als Teil von TR1 zum C++ - Standard hinzugefügt wurde. map wird im Allgemeinen mit einem ausgeglichenen binären Baum wie einem rot-schwarzen Baum implementiert (Implementierungen variieren natürlich). hash_map Und unordered_map Werden im Allgemeinen mit Hash-Tabellen implementiert. Somit bleibt die Reihenfolge nicht erhalten. unordered_map Einfügen/Löschen/Abfragen ist O(1) (konstante Zeit), wobei die Zuordnung O (log n) ist, wobei n die Anzahl der Elemente in der Datenstruktur ist unordered_map Ist also schneller, und wenn Sie sich nicht um die Reihenfolge der Artikel kümmern, sollten Sie es vorziehen, map. Manchmal möchten Sie die Reihenfolge (sortiert nach dem Schlüssel) beibehalten und das auch map wäre die Wahl.

34
janglin

Einige der Hauptunterschiede liegen in den Komplexitätsanforderungen.

  • Ein map benötigt O(log(N)) Zeit für Einfügungen und Suchvorgänge, da es als Rot-Schwarz-Baum Datenstruktur implementiert ist.

  • Ein unordered_map Benötigt eine 'durchschnittliche' Zeit von O(1) für Einfügungen und Suchen, darf aber im ungünstigsten Fall eine Zeit von O(N) haben. Dies liegt daran, dass die Implementierung mit der Datenstruktur Hash-Tabelle erfolgt.

Normalerweise ist unordered_map Also schneller, aber abhängig von den Tasten und der Hash-Funktion, die Sie speichern, kann dies viel schlimmer werden.

14

Die C++ - Spezifikation gibt nicht genau an, welchen Algorithmus Sie für die STL-Container verwenden müssen. Es stellt jedoch bestimmte Einschränkungen für ihre Leistung dar, die die Verwendung von Hash-Tabellen für map und andere assoziative Container ausschließen. (Sie werden am häufigsten mit rot/schwarzen Bäumen implementiert.) Diese Einschränkungen erfordern eine bessere Worst-Case-Leistung für diese Container, als Hash-Tabellen liefern können.

Viele Leute wollen jedoch wirklich Hash-Tabellen, so dass Hash-basierte STL-assoziative Container seit Jahren eine übliche Erweiterung sind. Folglich fügten sie unordered_map und so weiter zu späteren Versionen des C++ - Standards.

4
Warren Young

map wird aus balanced binary search tree (normalerweise ein rb_tree) implementiert, da alle Elemente in balanced binary search tree sortiert sind, auch map;

hash_map Wird aus hashtable implementiert, da alle Elemente in hashtable unsortiert sind und die Elemente in hash_map(unordered_map) nicht sortiert sind.

hash_map Ist keine C++ - Standardbibliothek, aber jetzt wird sie in unordered_map Umbenannt (Sie können sich vorstellen, dass sie umbenannt wird) und wird zur C++ - Standardbibliothek, da C++ 11 diese Frage sieht nterschied) zwischen hash_map und unordered_map? für weitere Details.

Im Folgenden werde ich eine Kernschnittstelle aus dem Quellcode geben, wie die Map mit zwei Typen implementiert wird.

karte:

Der folgende Code soll nur zeigen, dass map nur ein Wrapper eines balanced binary search tree Ist. Fast alles, was dazu gehört, ist, die Funktion balanced binary search tree Aufzurufen.

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_map Wird aus hashtable implementiert, dessen Struktur ungefähr so ​​aussieht:

enter image description here

Im folgenden Code gebe ich den Hauptteil von hashtable und dann hash_map An.

// 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);

};

So wie das einzige Mitglied von map'srb_tree Ist, ist das einzige Mitglied von hash_map'shashtable. Es ist Hauptcode wie folgt:

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);
        };

};

Das folgende Bild zeigt, wenn eine hash_map 53 Buckets hat und einige Werte einfügt, die interne Struktur.

enter image description here

Das folgende Bild zeigt einen Unterschied zwischen map und hash_map (unordered_map), das Bild stammt von Wie wählt man zwischen map und unordered_map? :

enter image description here

2
Jayhello

Ich weiß nicht, was gibt, aber hash_map braucht mehr als 20 Sekunden, um () 150K vorzeichenlose Ganzzahlschlüssel und Gleitkommawerte zu löschen. Ich laufe gerade und lese den Code eines anderen.

Dies ist, wie es hash_map enthält.

#include "StdAfx.h"
#include <hash_map>

Ich habe dies hier gelesen https://bytes.com/topic/c/answers/570079-perfomance-clear-vs-swap

zu sagen, dass clear () die Ordnung von O (N) ist. Das ist für mich sehr seltsam, aber so ist es.

0
BoBoDev