Hash table -添加rehash to resize方法

Question

我正在做哈希表的链接，我不知道我应该如何重新哈希整个表，同时调整大小。我正在考虑在resize方法中插入具有新散列代码的所有元素，但我不知道如何...你能给我点提示什么的吗？下面是rehash (我的意思是resize，还没有rehash)方法：

void rehash()
{
    if (current_size >= load * size) {
        int newsize = size * cap;
        Node** tmp = new Node * [newsize];
        for (int i = 0; i < size; i++) 
        {
            tmp[i] = hashtable[i];
        }
        for (int i = size; i < newsize; ++i) 
        {
            tmp[i] = NULL;
        }
        delete[] hashtable;
        hashtable = tmp;
        size = newsize;
    }
}

而且，如果有用的话，插入方法：

void addTo(string key, V value)
{
    rehash();
    int index = hashFunction(key);
    if (hashtable[index] == NULL)
    {
        Node* newpair = new Node(key, value);
        hashtable[index] = newpair;
        hashtable[index]->data = newpair;
    }
    else
    {
        Node* tmp = hashtable[index];
        Node* newpair = new Node(key, value);
        Node* newnode = new Node;
        newnode->data = newpair;
        newnode->next = NULL;
        while (tmp->next != NULL)
        {
            tmp = tmp->next;
        }
        tmp->next = newnode;
        
    }
    current_size++;
}

谢谢。

Answer 1

当您增加哈希表的大小时，对于某些键，相关的存储桶可能会发生变化。您的代码只是从前面部分复制列表，这意味着在表中不再能找到一些值。(例如，哈希码为13的键在大小为4的表中的索引为1，但在将大小增加到8后，索引将更改为5。)

分配新数组的基本方法是正确的，但必须将节点放入正确的存储桶中。因为您有一个链表，所以您可以访问旧表的每个存储桶，并在有第一个节点时提取第一个节点，然后将其放入具有正确新索引的存储桶中：

void rehash()
{
    if (current_size >= load * size) {
        size_t newsize = size * cap;
        Node** tmp = new Node * [newsize];

        for (size_t i = 0; i < newsize; ++i) {
            tmp[i] = NULL;
        }

        for (size_t i = 0; i < size; i++) {
            while (hashtable[i]) {
                Node *node = hashtable[i];
                size_t index = hashFunction(node->key);

                // remove node from old table ...
                hashtable[i] = node->next;

                // ... and insert into new one
                node->next = tmp[index];
                tmp[index] = node;                    
            }
        }

        // replace hash table
        delete[] hashtable;
        hashtable = tmp;
        size = newsize;
    }
}

这应该是可行的。(但我还没有测试过它。)