user1289 - 1 year ago 43

C++ Question

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

// ...

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

};

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;

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;

}

So, let's imagine there are 3 elements mapped to hash

`i`

`k`

`b[i]`

`Entry`

`v`

`b[i]`

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
```