Wie löst C ++ STL unordered_map Kollisionen?

Wie funktioniert der C++ STL unordered_map beheben Kollisionen?

Blick auf die http://www.cplusplus.com/reference/unordered_map/unordered_map/heißt es "Unique keys
Keine zwei Elemente im container können über entsprechende Tasten".

Das bedeuten sollte, dass der container tatsächlich auflösen von Kollisionen. Jedoch, dass die Seite nicht mir sagen, wie es ist, es zu tun. Ich kenne einige Möglichkeiten, um beheben Sie Kollisionen wie mit verknüpften Listen und/oder antasten. Was ich wissen möchte ist, wie die c++ STL unordered_map ist zu lösen.

InformationsquelleAutor der Frage whiteSkar | 2014-02-03

  1. 48

    Definiert der standard ein wenig mehr über diese, als die meisten Menschen scheinen zu realisieren.

    Insbesondere die Norm erfordert (§23.2.5/9):

    Elemente eine ungeordnete assoziative container unterteilt sind Eimer. Schlüssel mit dem gleichen hash-code angezeigt, in der gleichen Eimer.

    Die Schnittstelle enthält eine bucket_count läuft in konstanter Zeit. (Tabelle 103). Es enthält auch eine bucket_size zu laufen, in der Zeit linear auf die Größe des Eimers.

    Das ist im Grunde die Beschreibung einer Implementierung, die verwendet Kollision Verkettung. Wenn Sie das tun, verwenden Kollision Verkettung, Erfüllung aller Anforderungen ist irgendwo zwischen einfach und trivial. bucket_count() ist die Anzahl der Elemente im array. bucket_size() ist die Anzahl der Elemente in der Kollision Kette. Dass Sie in Konstante und lineare Zeit bzw. ist einfach und unkompliziert.

    Dagegen, wenn Sie so etwas wie lineares Sondieren oder doppeltes hashing-diese Anforderungen werden alle, aber unmöglich zu erfüllen ist. Insbesondere alle Elemente, die gehasht, um einen bestimmten Wert brauchen, um in das land gleichen Eimer, und Sie müssen in der Lage sein zu zählen, die Eimer in konstanter Zeit.

    Aber, wenn Sie so etwas wie lineares Sondieren oder doppeltes hashing finden Sie alle Artikel, die gehasht auf den gleichen Wert bedeutet, dass Sie brauchen, um hash-Wert, dann zu Fuß durch die "Kette" nicht-leerer Elemente in Ihrer Tabelle zu finden, wie viele von diesen Hash auf den gleichen Wert. Das ist nicht linear von der Anzahl der Elemente, die hashed, um den gleichen Wert, obwohl-es ist linear von der Anzahl der Elemente, dass Hash, um die gleiche oder eine Kollision Wert.

    Genug zusätzliche Arbeit und einen fairen Betrag von stretching, die Bedeutung der einige der Anforderungen, die fast an die Belastungsgrenze, es wäre kaum möglich, erstellen Sie eine hash-Tabelle mit etwas anderem als Kollision Verkettung, und noch zumindest etwas erfüllen die Anforderungen-aber ich bin mir nicht wirklich sicher, es ist möglich, und es würde bestimmte mit sehr viel extra Arbeit.

    Zusammenfassung: alle praktischen Umsetzungen der std::unordered_set (oder unordered_map) zweifellos verwenden Kollision Verkettung. Auch wenn es vielleicht (gerade noch) möglich, um den Anforderungen der Verwendung von linearen Sondieren oder doppeltes hashing eine solche Umsetzung scheint sehr viel verlieren und gewinnen fast nichts zurück.

    InformationsquelleAutor der Antwort Jerry Coffin

  2. -1

    wahrscheinlich durch Verkettung. Eine effektive form der hashmap collision resolution zu implementieren, die es mit einer verlinkten Liste. Also wenn ein Eintrag endet in Kollision mit einem anderen hash, es wird einfach nur hängen Sie an das kollidierte Eintrag-Zeiger-Knoten. Ich erkläre mit code.

    typedef struct mapnode {
    const char *strKey;
    void *pData;
    struct mapnode *pNext;
} mapnode_t;

typedef struct hashmap {
    mapnode_t **ppTable;
    unsigned uiLength; //how big is the table?
    unsigned uiCount; //how many entries do we really have?
} hashmap_t;

//excerpt from hashmap_insert
mapnode_t *node = malloc( sizeof(mapnode_t) );
if( !node ) {
    printf("**** Memory Allocation Error **** hashmap_insert::node is NULL\n");
    return false;
}
node->strKey = szKey;
node->pData = pData;

unsigned hash = gethash(szKey) % d->uiLength;
node->pNext = d->ppTable[hash];
d->ppTable[hash] = node;
++d->uiCount;

    Wie Sie sehen können aus dem letzten Teil. Wenn man den hash-Wert, dass der Eintrag platziert werden soll, wir zuerst emplace des Knotens pNext - pointer zu Punkt, an welchem ppTable[hash] schon hat; wenn es null ist, wird der Zeiger null sein wird oder so. Nach der Einstellung der Knoten-Zeiger, setzen wir die Knoten als neuen hash-index-Wert und Schrittweite uiCount wie wir erfolgreich platziert einen neuen Eintrag.

    InformationsquelleAutor der Antwort Nergal

Schreibe einen Kommentar