Hash table 的调整大小使程序崩溃

Question

我正在尝试使用 STL 对列表在 C++ 中实现哈希 Table。初始 maxSize 我设置为 1，我想在其 currentSize 大于最大容量的 75% 时将哈希 table 的大小增加两倍。我收到错误“无法取消引用结束列表运算符”。这是我的实现：

template<class V>
class HashTable {
public:
    int currentSize;
    int maxSize;
    std::list<std::pair<std::string, V> > *arr;

    HashTable() {
        this->currentSize = 0; 
        this->maxSize = 1; 
        this->arr = new std::list<std::pair<std::string, V> >[maxSize];
        arr->assign(maxSize, std::pair<std::string, V>());
    }
    ~HashTable() {
        delete[] arr;
    }

    void add(std::string key, V value) {
        if (currentSize >= 0.75 * maxSize) {
            rehash();
        }
        currentSize++;
        int idx = hashFunction(key);
        std::list<std::pair<std::string, int> >::iterator it = arr->begin();
        std::advance(it, idx);
        it = arr->erase(it);
        arr->insert(it, std::pair<std::string, V> (key, value));
    }

    int hashFunction(std::string key) {
        int total = 0;
        for (int i = 0; i < key.length(); i++) {
            total += int(key[i]) * pow(31, key.length() - i - 1);
        }
        return total % maxSize;
    }

    void rehash() {
        maxSize *= 2;
        std::list<std::pair<std::string, V> > *newArr = new std::list<std::pair<std::string, V> >[maxSize];
        newArr->assign(maxSize, std::pair<std::string, V>());
        for (auto it = arr->begin(); it != arr->end(); it++) {
                int idx = hashFunction(it->first);
                it = arr->begin();
                std::advance(it, idx);
                it = arr->erase(it);
                newArr->insert(it, std::pair<std::string, V>(it->first, it->second));
        }
        delete[] arr;
        arr = newArr;
    }

有趣的事实是，当我对 maxSize 进行硬编码时，例如通过将其设置为 20 然后添加 2 个元素，它可以工作并输出例如“1：abc -> 123，5：bca -> 42”。

Answer 1

显示的代码中存在多个错误。

在你的 rehash:

it = arr->erase(it);

erase() 总是 returns 指向刚被擦除的那个值之后的值的迭代器。这就是它的工作原理。因此，如果 it 已经碰巧引用了 arr 中的最后一个值，erase() 将其删除并有效地 returns end()。之后：

for (  ... ; it++)

一如既往地增加 it。但在这种情况下 it 已经是 end()。增加 end() 迭代器值是未定义的行为。

另外：

newArr->insert(it, ...

it 不是 newArr 的迭代器，它是另一个容器的迭代器。迭代器只能作为参数传递给它自己的容器insert()。更多未定义的行为。

Hash table 的调整大小使程序崩溃

Hash table's resizing crashes program

c++

algorithm

hashtable