c++ - Stroustrup 的 hash_map 的实现是错误的？

Question

我正在查看 Straustrup 的 hash_map 实现。这将给出他如何实现的直觉

template<class Key, class T, class H = Hash<Key>, class EQ = equal_to<Key>, class A = allocator<T> >
class hash_map
{
private: // representation
    struct Entry {
        key_type key;
        mapped_type val;
        Entry* next; // hash overflow link
        bool erased;
        Entry(key_type k, mapped_type v, Entry* n)
        : key(k), val(v), next(n), erased(false) { }
    };

    vector<Entry> v; // the actual entries
    vector<Entry*> b; // the hash table: pointers into v
    // ...

private:
    float max_load; // keep v.size()<=b.size()*max_load
    float grow; // when necessary, resize(bucket_count()*grow)
    size_type no_of_erased; // number of entries in v occupied by erased elements
    Hasher hash; // hash function
    key_equal eq; // equality
    const T default_value; // default value used by []
};

这是 operator[] 的实现

template<class Key, class T, class H = Hash<Key>, class EQ = equal_to<Key>, class A = allocator<T> >
mapped_type& hash_map::operator[](const key_type& k)
{
    size_type i = hash(k)%b.size(); // hash
    for(Entry* p = b[i]; p; p = p->next) // search among entries hashed to i
        if (eq(k,p->key)) { // found
            if (p->erased) { // re-insert
                p->erased = false;
                no_of_erased--;
                return p->val = default_value;
            }
            return p->val;
        }

    // not found:
    if (b.size()*max_load < v.size()) { // if ‘‘too full’’
        resize(b.size()*grow); // grow
        return operator[](k); // rehash
    }

    v.push_back(Entry(k,default_value,b[i])); // add Entry
    b[i] = &v.back(); // point to new element
    return b[i]->val;
}

所以，假设有 3 个元素映射到哈希 i，但没有一个对应于新键 k，那么我们应该在列表中添加另一个条目b[i]，对吧？相反，代码在 v vector 中创建了另一个 Entry 并将 b[i] 替换为该条目的地址(因此丢失了旧的 3 个条目) .

是我遗漏了什么，还是真的有问题？

附言我正在看 Bjarne Straustrup 的“The C++ Programming language”，第三版。该函数在第 500 页。

Answer 1

哈希条目形成一个链表。当插入新条目时，它被赋予条目列表的前一个头部(可能为空):

v.push_back(Entry(k,default_value,b[i])); // add Entry

看到那里的b[i]了吗？

然后它在其 next 字段中创建指向该条目的链接。然后我们移动列表的头部 b[i] 以指向新条目；

b[i] = &v.back(); // point to new element