MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Solved

Posted on 2003-12-06

To C++ Experts,

I am still struggling to understand the logic of a hashtable. This is a continued question of :

http://www.experts-exchange.com/Programming/Programming_Languages/Cplusplus/Q_20817844.html

The implementation of the insert() function looks like :

---------------------------------------------------------------------

template <class K, class T, class H>

bool HashTable<K,T,H>::insert(K key, T val)

{ const K ZERO_K = K() ;

int k0 = hash(key), k = k0 ; // line01 .... Q1

while ( _[k].first != key && _[k].first != ZERO_K)

k=(k+1)%_.size() ;

if (_[k].first == key) return false ;

if (size()+1 < LOAD*_.size()) _[k] = Pair(key,val) ;

else

{ rebuild() ;

insert(key,val) ;

}

return true ;

}

------------------------------------------------------

So here is my question :

Q1. in line01: k0 and k could be values larger than 1, and "_" is a vector of pair in the HashTable. Then it seems to me that : the vector "_" does not start from 0 ? (I mean _[0], v[1] ... could be empty). It starts at certain k dependes on the pair we inserted and the first several elements of "_" could be empty ???

Q2. if the above statement is true, it troubles me a lot ! If the first several elements of "_" is empty, what does _.size() mean ? Then how do we know the later implementation such as "size()+1 < LOAD*_.size()" is correct ?

Thanks very much !!!

meow.

I am still struggling to understand the logic of a hashtable. This is a continued question of :

http://www.experts-exchange.com/Programming/Programming_Languages/Cplusplus/Q_20817844.html

The implementation of the insert() function looks like :

--------------------------

template <class K, class T, class H>

bool HashTable<K,T,H>::insert(K

{ const K ZERO_K = K() ;

int k0 = hash(key), k = k0 ; // line01 .... Q1

while ( _[k].first != key && _[k].first != ZERO_K)

k=(k+1)%_.size() ;

if (_[k].first == key) return false ;

if (size()+1 < LOAD*_.size()) _[k] = Pair(key,val) ;

else

{ rebuild() ;

insert(key,val) ;

}

return true ;

}

--------------------------

So here is my question :

Q1. in line01: k0 and k could be values larger than 1, and "_" is a vector of pair in the HashTable. Then it seems to me that : the vector "_" does not start from 0 ? (I mean _[0], v[1] ... could be empty). It starts at certain k dependes on the pair we inserted and the first several elements of "_" could be empty ???

Q2. if the above statement is true, it troubles me a lot ! If the first several elements of "_" is empty, what does _.size() mean ? Then how do we know the later implementation such as "size()+1 < LOAD*_.size()" is correct ?

Thanks very much !!!

meow.

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

- Help others & share knowledge
- Earn cash & points
- Learn & ask questions

1 Comment

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

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Title | # Comments | Views | Activity |
---|---|---|---|

Would like to move button in a function | 3 | 85 | |

FMX StringGrid1->Canvas->FillR |
3 | 197 | |

Add values of each row in an array | 3 | 70 | |

Compile error - linkage specification contradicts earlier specification for 'DllGetClassObject' | 6 | 79 |

Join the community of 500,000 technology professionals and ask your questions.