user1289 user1289 - 1 year ago 43
C++ Question

Stroustrup's hash_map's implementation is wrong?

I'm looking at Straustrup's implementation of hash_map. This will give an intuition how he's implementing it

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
// ...

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 []

And this is implementation of 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;
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;

So, let's imagine there are 3 elements mapped to hash
, but none of them corresponds to the new key
, then we should add another Entry in the list
, right? Instead the code creates another
in the
vector and replaces
with the address of that entry (whence losing old 3 Entries).

Did I miss something, or really there is an issue?

P.S. I'm looking at "The C++ Programming language" by Bjarne Straustrup, Third edition. The function is on 500th page.

Answer Source

The hash entries form a linked list. When the new entry is inserted, it is given the previous head of the list of entries (possibly null):

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

See the b[i] there?

It then makes a link to that entry in its next field. We then move the head of the list b[i] to point at the new entry;

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