0

これがgdbでどのように機能するかを理解するのにしばらく苦労していましたが、理解するのに苦労しています。基本的に、elements_物事がハッシュされる配列（）があります。これらは、連鎖に使用される特定のフックを含む構造体へのポインターです。サンプル構造体は次のとおりです。

struct foo
{
    Data  data;
    foo*  next;
    foo** prevNext;
};

次に、ハッシュテーブルはでインスタンス化されます

HashTable<foo> hash;

挿入機能は次のようになります（簡単にするために、サイズ変更などはすべて省略しています）

template <class T>
void HashTable<T>::insert(T* x)
{
    int bucket  = hashFunc(x->data);
    T** xPtr    = &elements_[bucket];
    x->next     = *xPtr;
    x->prevNext = xPtr;

    if (x->next)
        x->next->prevNext = &x->next;

    *xPtr = x;
}

削除は次のとおりです

template<class T>
void HashTable<T>::remove(T* x)
{
    if (x->next)
        x->next->prevNext = x->prevNext;

    *x->prevNext = x->next;
}

参考までに、検索方法は次のようになります。

template<class T>
T* HashTable<T>::find(Data& data)
{
    int bucket = hashFunc(data);

    T* ptr = elements_[bucket];
    while (ptr != 0)
    {
        if(ptr->data == data)
            return ptr;
        ptr = ptr->next;
    }
    return 0;
}

私は2〜3個の衝突する要素の挿入（最初はテーブルサイズを小さく設定することによって）と削除を追跡してロジックが何であるかを確認しようとしていますが、理解していません。これは、削除操作（ノード2の削除）が行っていると思うことの図ですが、私の頭の中ではまだ少しあいまいです。

ここに画像の説明を入力してください

4

1 に答える 1

1

同じバケットに分類される要素は、二重リンクリスト（一種）として保存されます。

ルックアップは、値が一致する要素が見つかるまでそのリストをトラバースしdataます。

于 2012-09-27T23:43:20.910 に答える