2

ハッシュテーブルについて学び始めたばかりで、挿入方法は理解していますが、検索方法は理解していません。これらは、この質問の基になるアルゴリズムです。

キーのハッシュ

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

衝突解決のための線形プローブ。

キー 1、11、および 21 を使用して insert を 2 回呼び出すとします。これにより、3 つのキーすべてに対してスロット 1 が返されます。衝突の解決後、テーブルはスロット 1、2、および 3 で値 1、11、および 21 を持ちます。これは、挿入についての私の理解では起こると思います。

これを行った後、キー 11 と 21 を検索すると、どうすればスロット 2 と 3 を取得できますか? 私が読んだことから、ハッシュテーブルの検索は、目的のスロットに到達したときに、何かを挿入する代わりにそのスロットで値を返すことを除いて、挿入と文字通り同じことを行う必要があります。

これを文字通りに解釈して同じアルゴリズムを適用すると、キー 11 を検索すると、スロット 4 に到達します。これは、スロット 1 から開始し、空のスロットが見つかるまで順方向にプローブし続けるためです。スロット 2 は空ではないので、私が望むものであっても、スロット 2 で停止しません。

別のチェーンを使用しても、これに苦労しています。3 つのキーはすべてスロット 1 に格納されますが、同じアルゴリズムを使用して検索すると、リンクされたリスト内のどのノードではなく、スロット 1 が返されます。

4

2 に答える 2

1

私は通常、衝突を処理するリンク リストを作成できるように、テーブルの各エントリを構造体にすることを好みます。これにより、衝突が大幅に減少します。このようなもの。

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

もちろん、ルックアップ関数は、最初のエントリのキー マッチが見つからない場合、リストをトラバースする必要があります。パフォーマンスが重要な場合は、並べ替えやバイナリ検索の使用など、リンクされたリストに他の戦略を使用できます。

于 2012-10-22T23:28:42.993 に答える
1

各スロットには、キーと値のペアが格納されます。各スロットを検索するときに、キーが検索しているキーと等しいかどうかを確認します。等しいキーが見つかったら、検索を停止して値を返します。

個別のチェーンを使用すると、リスト内の各キーに対してキーをチェックして、リスト全体を線形検索できます。

于 2012-10-22T23:30:43.370 に答える