Wie löst C++ STL unordered_map Kollisionen?

Wie löst C++ STL unordered_map Kollisionen?

Mit Blick auf die http://www.cplusplus.com/reference/unordered_map/unordered_map/heißt es “Eindeutige Schlüssel Zwei Elemente im Container können keine gleichwertigen Schlüssel haben.”

Das sollte bedeuten, dass der Container tatsächlich Kollisionen auflöst. Diese Seite sagt mir jedoch nicht, wie es das macht. Ich kenne einige Methoden, um Kollisionen zu lösen, wie z. B. die Verwendung von verknüpften Listen und/oder das Sondieren. Was ich wissen möchte, ist, wie die c++ STL unordered_map es auflöst.

Der Standard definiert etwas mehr darüber, als die meisten Menschen zu erkennen scheinen.

Insbesondere fordert der Standard (§23.2.5/9):

Die Elemente eines ungeordneten assoziativen Containers sind in Buckets organisiert. Schlüssel mit demselben Hashcode erscheinen im selben Bucket.

Die Schnittstelle umfasst a bucket_count das läuft in konstanter Zeit. (Tabelle 103). Dazu gehört auch ein bucket_size das muss zeitlich linear zur Größe des Eimers laufen.

Das beschreibt im Grunde eine Implementierung, die Kollisionsverkettung verwendet. Wenn Sie Kollisionsverkettung verwenden, ist das Erfüllen aller Anforderungen irgendwo zwischen einfach und trivial. bucket_count() ist die Anzahl der Elemente in Ihrem Array. bucket_size() ist die Anzahl der Elemente in der Kollisionskette. Sie in konstanter bzw. linearer Zeit zu erhalten, ist einfach und unkompliziert.

Wenn Sie dagegen so etwas wie lineares Sondieren oder doppeltes Hashing verwenden, werden diese Anforderungen so gut wie unmöglich zu erfüllen. Insbesondere müssen alle Elemente, die auf einen bestimmten Wert gehasht wurden, im selben Bucket landen, und Sie müssen in der Lage sein, diese Buckets in konstanter Zeit zu zählen.

Wenn Sie jedoch so etwas wie lineares Sondieren oder doppeltes Hashing verwenden, bedeutet das Finden aller Elemente, die auf denselben Wert gehasht wurden, dass Sie den Wert hashen und dann durch die “Kette” nicht leerer Elemente in Ihrer Tabelle gehen müssen, um herauszufinden, wie viele von denen auf den gleichen Wert gehasht. Das ist jedoch nicht linear in Bezug auf die Anzahl der Elemente, die auf denselben Wert gehasht wurden – es ist linear in Bezug auf die Anzahl der Elemente, die auf denselben Wert gehasht wurden oder ein kollidierender Wert.

Mit genügend zusätzlicher Arbeit und einer ziemlichen Menge an dehnender Bedeutung einiger der Anforderungen fast bis zum Zerreißen, ist es möglicherweise kaum möglich, eine Hash-Tabelle mit etwas anderem als Kollisionsverkettung zu erstellen und dennoch die Anforderungen zumindest irgendwie zu erfüllen. -aber ich bin mir nicht sicher, ob es möglich ist, und es würde sicherlich eine Menge zusätzlicher Arbeit erfordern.

Zusammenfassung: alle praktischen Umsetzungen von std::unordered_set (oder unordered_map) verwenden zweifellos Kollisionsverkettung. Während es vielleicht (gerade noch) möglich ist, die Anforderungen mit linearem Sondieren oder doppeltem Hashing zu erfüllen, scheint eine solche Implementierung viel zu verlieren und im Gegenzug fast nichts zu gewinnen.

Ich habe diese Antwort gefunden, als ich suchte, wie ich erkennen kann, wann meine Typen kollidieren, also werde ich dies posten, falls dies die Absicht der Frage ist.:

Ich glaube, es gibt ein Missverständnis über “Eindeutige Schlüssel. Keine zwei Elemente im Container können gleichwertige Schlüssel haben.”

schau dir den Code unten an

//pseudocode
std::unordered_map<int, char> hashmap;
hashmap[5] = 'a';
hashmap[5] = 'b'; //replace 'a' with 'b', there is no collision being handled.

Ich denke, die Antwort von Jerry bezieht sich auf das interne System, das es verwendet, um Schlüssel auf geeignete Array-Indizes zu verkleinern.

Wenn Sie möchten, dass Kollisionen für Ihre Typen (mit Buckets) behandelt werden, müssen Sie std::unordered_multimap und müssen iterieren

Hoffentlich kann dieser Code ohne den Kontext gelesen werden, mit dem ich ihn generiert habe. Es prüft im Grunde, ob ein Element im Bucket, das dem Hash zugeordnet ist, das Element ist, nach dem ich suche.

//sp is std::shared_ptr
//memo is std::unordered_multimap< int, sp<AStarNode> >

//there's probably multiple issues with this code in terms of good design (like using int keys rather than unsigned)

bool AStar_Incremental::hasNodeBeenVisited(sp<AStarNode> node)
{
    using UMIter = std::unordered_multimap<int, sp<AStarNode> >::iterator;

    bool bAlreadyVisited = false;

    //get all values for key in O(1*)
    int hash = WorldGrid::hashGrid(node->location);
    std::pair<UMIter, UMIter> start_end = memo.equal_range(hash); //bucket range
    UMIter start = start_end.first;
    UMIter end = start_end.second;

    //hopefully this is implemented to be O(m) where m is the bucket size.
    for(UMIter bucketIter = start; bucketIter != end; ++bucketIter)
    {
        sp<AStarNode> previousNode = bucketIter->second;
        sf::Vector2i& previousVisit = previousNode->location;
        if (previousVisit == node->location)
        {
            bAlreadyVisited = true;
            break;
        }
    }

    return bAlreadyVisited;
}