I am creating my own hashtable adt for my data structures class and have run across a problem. I used the following functions to hash (key,value) entries in my hash table(the key is a string and the value can be any data type,it is generic):
private int hashCode(String key)
final int constant = 37;
int hash = 0;
hash+=(int)key.charAt(i) * Math.pow(constant,i);
private int hash(String key)
return hashCode(key) % capacity
Generally speaking, when you rehash a hash table, you need to iterate over all the elements in the hash table and redistribute them based on their hash codes so that they end up in the proper location. This takes a little bit more time than just resizing things normally, but otherwise the table doesn't work correctly.
The alternative would be to use a different collision resolution scheme like extendible hashing that is specifically built to avoid moving things after placing them, but given just how blindly fast linear probing hashing is in practice I imagine the slowdown from this setup would likely not be worth it.