(1) You don't show the hash() function but it returns a number modulo the table size (_.size()). Modular arithmetic works with values on the range 0 - (_.size()-1), exactly the range of indices in a C++ array (or vector).

The point of a hash function is to "randomize" the key values to avoid clustering. So, if there is one item in your hash there is no guarantee that it is in _[0]. Your hash table is using open address hashing where if two keys do hash to the same location (which is bound to happen by the pigeon hole principle), the collision is resolved by walking the table the the +1 direction (modular arithmetic again) until an opening is found. Notice that the load factor makes sure that there is at least one free slot so the loop must terminate

(2) A hash table's size is the number of SLOTs in the hash table. So _.size() is initialized (remembering from another of your posts) to 109? That means there is room for 109 pairs and when there are too many in the table rebuild is called to expand _ (and _.size()). You would keep track of the size() of the hash table (the number of entries inserted into it) and _.size() separately (as your implementation seems to do).

Hope this helps, -bcl

The point of a hash function is to "randomize" the key values to avoid clustering. So, if there is one item in your hash there is no guarantee that it is in _[0]. Your hash table is using open address hashing where if two keys do hash to the same location (which is bound to happen by the pigeon hole principle), the collision is resolved by walking the table the the +1 direction (modular arithmetic again) until an opening is found. Notice that the load factor makes sure that there is at least one free slot so the loop must terminate

(2) A hash table's size is the number of SLOTs in the hash table. So _.size() is initialized (remembering from another of your posts) to 109? That means there is room for 109 pairs and when there are too many in the table rebuild is called to expand _ (and _.size()). You would keep track of the size() of the hash table (the number of entries inserted into it) and _.size() separately (as your implementation seems to do).

Hope this helps, -bcl