Rehashing

• If the table gets too full, the running time for the operations will start taking too long and insertions might fail for open addressing hashing with quadratic resolution. This can happen if there are too many removals intermixed with insertions.
• Rehashing is to build another table that is about twice as big (with an associated new hash function) and scan down the entire original hash table, computing the new hash value for each (nondeleted) element and inserting it in the new table.
• Rehashing is obviously a very expensive operation; the running time is O(N), since there are N elements to rehash and the table size is roughly 2N, but it is actually not all that bad, because it happens very infrequently.
• If this data structure is part of the program, the effect of rehashing is not noticeable. On the other hand, if the hashing is performed as part of an interactive system, then the unfortunate user whose insertion caused a rehash could see a slowdown.
• Rehashing can be implemented in several ways with quadratic probing.
• One alternative is to rehash as soon as the table is half full.
• The other extreme is to rehash only when an insertion fails.
• A third, middle-of-the-road strategy is to rehash when the table reaches a certain load factor. Since performance does degrade as the load factor increases, the third strategy, implemented with a good cutoff, could be best.