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 回答