map vs. hash_map in C ++

117

Ich habe eine Frage mit hash_mapund mapin C ++. Ich verstehe, dass dies mapin STL ist, aber hash_mapkein Standard ist. Was ist der Unterschied zwischen den beiden?

skydoor
quelle

Antworten:

133

Sie werden auf sehr unterschiedliche Weise implementiert.

hash_map (unordered_map in TR1 und Boost; verwenden Sie diese stattdessen) Verwenden Sie eine Hash-Tabelle, in der der Schlüssel in einen 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 implementiert (normalerweise ein rot / schwarzer Baum).

A unordered_mapsollte eine etwas bessere Leistung für den Zugriff auf bekannte Elemente der Sammlung bieten, hat jedoch mapzusätzliche nützliche Eigenschaften (z. B. wird es in sortierter Reihenfolge gespeichert, die das Durchlaufen von Anfang bis Ende ermöglicht). unordered_mapwird beim Einfügen und Löschen schneller sein als a map.

Joe
quelle
7
Ich stimme Ihnen in Bezug auf die Leistung nicht ganz zu. Die Leistung wird durch eine Reihe von Parametern beeinflusst und ich würde jeden Programmierer mit einer unordered_map für nur 10 Einträge schelten, weil "Es ist schneller". Sorgen Sie sich zuerst um die Schnittstelle / Funktionalität, später um die Leistung.
Matthieu M.
24
Ja, es hilft, wenn Sie Ihr Problem verstehen. Bis zu bestimmten Größenordnungen ist es wahrscheinlich eine Waschleistung, aber es ist wichtig, die Leistungsmerkmale beider Behälter zu verstehen, da sie mit zunehmendem Datenvolumen unterschiedlich voneinander abweichen.
Joe
7
Interessanterweise habe ich gerade eine std :: map mit einer boost :: unordered_map in einer Anwendung ausgetauscht, in der ich viele zufällige Suchvorgänge durchführe, aber auch alle Schlüssel in der Map durchlaufe. Ich habe viel Zeit bei der Suche gespart, diese aber über die Iterationen wiedererlangt. Daher bin ich wieder zur Karte gewechselt und suche nach anderen Möglichkeiten, um die Anwendungsleistung zu verbessern.
Erik Garrison
4
@ErikGarrison Wenn Sie viel häufiger Direktzugriff und Iteration verwenden als Elemente einfügen und löschen, können Sie Ihre Objekte sowohl in einem Baum als auch in einer hash_map haben (indem Sie einen Zeiger oder besser noch einen shared_ptr auf dieselben Objekte in beiden in speichern Fall, dass Sie tatsächliche Instanzen verwendet haben). Sie haben dann O (1) Zeitzugriffszeit durch die hash_map und O (n) Iterationszeit durch die Karte. Natürlich müssen Sie daran denken, jedes Mal die Zeiger von beiden hinzuzufügen und zu entfernen. Sie könnten leicht eine benutzerdefinierte Containerklasse schreiben, die (wahrscheinlich auch eine Vorlage) dieses Verhalten für Sie kapselt.
Sprite
2
@ErikGarrison Wenn Sie diese Methode ausprobieren, zahlen Sie natürlich mit einem kleinen zusätzlichen Speicherplatz. Da Sie jedoch Zeiger verwenden würden, sollte dies nicht zu viel sein. Wenn Sie wirklich möchten, können Sie über Bord gehen und Ihre eigene Implementierung einer AVL schreiben und den Knotenzeiger als Datentyp in der hash_map verwenden. Dadurch erhalten Sie O (1) Zeitzugriff auf einen Knoten im Baum, von dem aus Sie können linear dorthin iterieren, wo Sie es benötigen. Dies würde natürlich einiges an Codierung erfordern, und ich bin mir nicht sicher, ob es sich auszahlen würde, wenn Sie nicht viel von und zu Orten mit wahlfreiem Zugriff iterieren müssen.
Sprite
35

hash_mapwar eine häufige Erweiterung, die von vielen Bibliotheksimplementierungen bereitgestellt wurde. Genau aus diesem Grund wurde es umbenannt, unordered_mapals es als Teil von TR1 zum C ++ - Standard hinzugefügt wurde. map wird im Allgemeinen mit einem ausgeglichenen Binärbaum wie einem rot-schwarzen Baum implementiert (Implementierungen variieren natürlich). hash_mapund unordered_mapwerden im Allgemeinen mit Hash-Tabellen implementiert. Somit wird die Reihenfolge nicht eingehalten. unordered_mapEinfügen / Löschen / Abfragen ist O (1) (konstante Zeit), wobei Map O (log n) ist, wobei n die Anzahl der Elemente in der Datenstruktur ist. So unordered_mapgeht es schneller, und wenn Sie sich nicht um die Reihenfolge der Artikel kümmern, sollten Sie es vorziehen map. Manchmal möchten Sie die Reihenfolge aufrechterhalten (sortiert nach dem Schlüssel) und dafür mapwäre die Wahl.

Janglin
quelle
9
Ich möchte darauf hinweisen, dass Hashmap einen Worst-Case-Zugriff von O (N) hat, wenn Kollisionen wahrscheinlich sind (schlechter Hash-FCN, zu hoher
Ladefaktor
Eine gute Hashmap hat erwartete Kosten von O (1), dies ist jedoch nicht garantiert. Schlechte Hashmaps haben möglicherweise erwartete Kosten, die nicht O (1) sind.
Klarer
14

Einige der Hauptunterschiede liegen in den Komplexitätsanforderungen.

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

  • A unordered_mapbenötigt eine 'durchschnittliche' Zeit O(1)für Einfügungen und Fundstücke, darf jedoch eine Worst-Case-Zeit von haben O(N). Dies liegt daran, dass es mithilfe der Hash Table- Datenstruktur implementiert wird.

Normalerweise ist unordered_mapes also schneller, aber abhängig von den Tasten und der von Ihnen gespeicherten Hash-Funktion kann es viel schlimmer werden.

R Samuel Klatchko
quelle
4

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

Viele Leute wollen jedoch wirklich Hash-Tabellen, daher sind Hash-basierte STL-assoziative Container seit Jahren eine häufige Erweiterung. Folglich fügten sie unordered_mapund so zu späteren Versionen des C ++ - Standards hinzu.

Warren Young
quelle
Es wurde tatsächlich in TR1 (std :: tr1 :: unordered_map) hinzugefügt, nicht in C ++ 0x
Terry Mahaffey
Ich dachte, dass der Grund dafür mapim Allgemeinen ein ausgewogener Baum ist, der operator<()als Mittel zur Standortbestimmung verwendet wird.
KitsuneYMG
@kts: Verwenden STL-Implementierungen tatsächlich einen B-Baum?
bk1e
Technisch gesehen sind alle binären Suchbäume B-Bäume (ein 1-2-Baum).
Davon abgesehen
@ bk1e "Richtige" B-Bäume sind besonders nützlich in Datenbanken, in denen Sie "fette" Baumknoten wünschen, die gut mit den Festplattenseiten übereinstimmen. OTOH, dies ist im "flachen" Speichermodell, das in "normalen" Programmen verwendet wird, nicht so nützlich - alle mir bekannten STL-Implementierungen verwenden rot-schwarze Bäume.
Branko Dimitrijevic
3

mapwird implementiert von balanced binary search tree(normalerweise a rb_tree), da alle Mitglieder in balanced binary search treesortiert sind, so ist map;

hash_mapwird von. implementiert, hashtableda alle Mitglieder in hashtableunsortiert sind, sodass die Mitglieder in hash_map(unordered_map)nicht sortiert sind.

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

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

Karte:

Der folgende Code soll nur zeigen, dass Map nur ein Wrapper von balanced binary search treeist. Fast alles, was seine Funktion ist, ist nur das Aufrufen der balanced binary search treeFunktion.

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_mapwird implementiert, hashtabledessen Struktur ungefähr so ​​ist:

Geben Sie hier die Bildbeschreibung ein

Im folgenden Code werde ich den Hauptteil von geben hashtableund dann geben 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);

};

Wie map'snur ein Mitglied ist rb_tree, ist das hash_map'seinzige Mitglied hashtable. Es ist der 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, ihre interne Struktur.

Geben Sie hier die Bildbeschreibung ein

Das folgende Bild zeigt einen Unterschied zwischen map und hash_map (unordered_map). Das Bild stammt von Wie wähle ich zwischen map und unordered_map ? ::

Geben Sie hier die Bildbeschreibung ein

Jayhello
quelle
1

Ich weiß nicht, was es gibt, aber hash_map benötigt mehr als 20 Sekunden, um () 150K vorzeichenlose Ganzzahlschlüssel und Float-Werte zu löschen. Ich laufe nur und lese den Code eines anderen.

So enthält es hash_map.

#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 nun mal.

BoBoDev
quelle