重新散列由列表向量组成的散列 table C++

Question

所以我实现了一个散列 table 存储指针。我将其实现为 lists 的 vector。沿着 std::vector<std::list<Sequence*> > hashTable; 的路线。我已经实施了一切并且工作正常。当我尝试重新散列哈希 table 时，出现了我唯一的问题。哈希 table 使用单独的链接来解决冲突，因此我的列表向量。

使用调试器，我发现要重新散列的循环挂在 while 循环上并导致无限循环。它不断地从我的旧向量的第一个索引中读取。我是新手，我不确定重新散列这个 table 的正确方法。我试图研究并发现没有太多参考这个哈希实现 table，更不用说重新哈希了。这是我的实现。

void HashTable::rehash(int oldSize){
    int tempSize = 2 * oldSize;
    int newSize = HashTable::findPrime(tempSize);
    std::vector<std::list< Sequence*> > newHashTable;
    newHashTable.resize(newSize);
    tableSize = newSize;
    for(int i = 0; i < oldSize; i++){
        auto iter = hashTable[i].begin();
        while(iter != hashTable[i].end()){
            if((*iter) != nullptr){
                std::string tempString = (*iter)->getKey();
                int hashIndex = hashFunction(tempString);
                newHashTable[hashIndex].push_front(*iter);
            }
        }
    }
    hashTable = newHashTable;
}

我觉得这是一个简单的错误，我只是没有看到它。还是我完全以错误的方式解决了这个问题？

Answer 1

您似乎没有更新 iter，这就是为什么 iter 永远不会变成 hashtable[i].end()，除非它以该值开头。

Answer 2

您在 while 循环结束前缺少一个 ++iter ，因此它会移至列表中的下一个。

我自己通常会使用 for 循环，因为它使我不太可能忘记递增迭代器。类似于：

for(auto iter = hashTable[i].begin(); iter != hashTable[i].end(): ++iter)
{
     // ... code using iterator ...
}

重新散列由列表向量组成的散列 table C++

Rehashing a hash table comprised of a vector of lists C++

c++

c++11

vector

stl

hashtable