Double Hashing or Rehashing

These are methods of dealing with hash collisions. Double hashing or rehashing involves using a secondary hash function on the hashed key of the item. The rehash function is applied successively until an empty position is found. If the hash position is found occupied during a search, the rehash function is again used to locate the item. In general, a rehash function, RH, accepts an array address and produces another. If array address H (K) is already occupied, a rehash function, RH, is applied to the value of H (K) i.e.

RH (H (K))

to find another location. If position RH (H (K) ) is also occupied, it too is rehashed to see if RH (RH (H (K))) is available. This process continues until an empty location is found. RH is not necessarily the same as the original hash function.

The following two methods are collectively known as double hashing or rehashing methods. In each method, rather than using an arithmetic probe function, the address is rehashed. Both methods prevent primary clustering.