How to implement a hash function for a dynamic hashtable?

Question

I am trying to implement a generic HashTable. (This question is in continuation to the question asked here)

I have implemented the generic hash function for the case when the size of the table is fixed. But, in real time situations, it's a pretty bad idea to use a HashTable whose size is initially fixed to about the 2^32 bits since it might lead to a lot of memory wastage.

So, what I am now trying to do is to dynamically increase the size of the hast table, from some initial value, whenever it's full.

But, when I do this the hash function will now return new values to the the previously hashed keys.

Is there any way to overcome this problem other than re-hashing the values previously hashed values with the new ones.

Answer 1

You cannot avoid rehashing: the position of the bucket where an element ends up inside your hash table depends on two or three things, depending on your collision resolution strategy:

• The hash code of the element,
• The size of the table, and
• When you use linear probing, it's also the presence or absence of prior elements with hash codes that put them in the same bucket

If you change any of these three factors, you need a full rehash: unless you do something really bad, such as picking a non-prime table size, the value of the hashCode % tableSize exression that determines the position is going to be different when you change the tableSize. The presence or absence of elements that hash to the same bucket in linear probing is going to change as well. That is why you need a full rehash.