Old elements in a hashtable aren't found after a resize?

Question

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;

    for(int i=0;i<key.length();i++)
    {
        hash+=(int)key.charAt(i) * Math.pow(constant,i);
    }
    return hash;
}
private int hash(String key)
{
    return hashCode(key) % capacity
}

Using linear probing the inserts into the table work fine,however if I ever choose to expand the table the hash(key) function will not work adequately for the get(key) operation of a hash table as the capacity has changed(it will map to the incorrect location when before the table extension it mapped correctly). Is there any easy way I could edit this which takes into account a extension of a hash table by lets say a factor of two. Ie: if loadfactor > 0.5 increase table by 2* the capacity.

Rehashing all the keys after resizing the array is a common practice. You may want to look in your textbook for a more in-depth explanation of how its done. — 4castle

templatetypedef templatetypedef · Accepted Answer · 2016-11-29T02:10:43

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.

Old elements in a hashtable aren't found after a resize?

1 Answers