Wie Suche ich in einer hash-Tabelle?

Ich habe gerade angefangen zu lernen, über hash-Tabellen, und ich verstehe, wie legen aber nicht, wie suchen. Diese sind die algorithmen werde ich stützend auf diese Frage aus:

Hashing-Schlüssel

int Hash (int key) {
    return key % 10;  //table has a max size of 10
}

Linear probing for collision resolution.

Angenommen, ich nenne legen Sie sich zweimal mit den Tasten 1, 11 und 21. Dies würde die Rückkehr slot 1 für alle 3 keys. Nach der Kollision Auflösung würde die Tabelle haben die Werte 1, 11 und 21 an den slots 1, 2 und 3. Dies ist, was ich annehmen würde passieren mit meinem Verständnis einfügen.

Nachdem Sie dies tun, wie würde ich die slots 2 und 3, wenn ich bei der Suche nach den Schlüsseln 11 und 21? Von dem, was ich gelesen habe, suchen Sie eine hash-Tabelle sollte buchstäblich die gleiche Sache, wie das einfügen, außer, wenn Sie ankommen an den gewünschten Steckplatz, kehren Sie den Wert an, der Steckplatz anstelle von einsetzen etwas in Sie hinein.

Wenn ich das wörtlich nehmen und anwenden des gleichen Algorithmus, wenn ich nach dem Schlüssel 11 ich ankommen würde in slot 4, da es beginnen würde, bei slot 1 und halten Sie Sondieren nach vorne, bis es findet einen leeren slot. Es würde nicht aufhören, auf Steckplatz 2, obwohl es das ist, was ich will, weil es nicht leer ist.

Ich bin mit diesen zu kämpfen, selbst wenn ich getrennte Verkettung. Alle 3 Tasten gespeichert werden würde auf slot 1, aber mit dem gleichen Algorithmus zur Suche zurückkehren würde, slot 1, nicht die Knoten in der verketteten Liste.

InformationsquelleAutor TreeTree | 2012-10-22

  1. 1

    Jedem Steckplatz wird ein Schlüssel/Wert-paar. Als Sie bist suchen durch jedes Ablagefach, überprüfen Sie, ob der Schlüssel gleich dem Schlüssel, den du suchst. Aufhören zu suchen, und geben den Wert zurück, wenn Sie finden, der einen gleichen Schlüssel.

    Mit separater Verkettung, die Sie tun können, eine lineare Suche durch die Liste durch, die überprüfung der Schlüssel vor jedem Schlüssel in der Liste.

    Ich habe keine Ahnung, warum ich nicht glaube, ich könnte den key selbst.
    Huh? Ich so über-dachte deine Frage.

    InformationsquelleAutor fgb

  2. 0

    Ich in der Regel bevorzugen, um jeden Eintrag in der Tabelle eine Struktur, so kann ich eine Link-Liste zu handhaben Kollisionen. Dies reduziert die Kollisionen deutlich. So etwas wie dieses.

    struct hashtable
{
    int key;
    struct hashtable *pList;
};

struct hashtable ht[10];

void Insert(int key);
{
    index = Hash(key);
    if (!ht[index].key)
    {
        ht[index].key = key;
        ht[idnex].pList = 0;
    } 
    else
    {
        struct hashtable *pht;
        pht = ht[index].pList; 
        while (pht->pList)
            pht = pht->pList;
        pht->pList = new struct hashtable;
        pht->pList->key = key;
        pht->pList->pList = 0;
    }
    return;
}

    Die lookup-Funktion würde natürlich zum Durchlaufen der Liste, wenn es nicht der erste Eintrag, der Schlüssel passt. Wenn Leistung wichtig ist, könnten Sie andere Strategien für die verlinkten Listen wie diese zu Sortieren und mit binärer Suche.

    InformationsquelleAutor Carey Gregory

Schreibe einen Kommentar