Page 200 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 9: Hashing

Notes

Task “Open hashing is most appropriate when the hash table is kept in main memory,
with the lists implemented by a standard in-memory linked list.” Explain.

9.5 Rehashing

This is another method of collision handling. In this method you find an alternative empty
location by modifying the hash function, and applying the modified hash function to the colliding

symbol. For example, if x is symbol and h(x) = i, and if the ith location is already occupied, then
I modify the hash function h to h1, and find out h1(x), if h1(x) =j, and jth location is empty, then

I accommodate x in the jth location. Otherwise you once again modify h1 to some h2 and repeat
the process till the collision gets handled. Once the collision gets handled we revert back to the
original hash function before considering the next symbol.
Denote h(x, 0) by simply h(x).

Linear Probing

h(x, i) = (h(x) + i) mod m

Quadratic Probing

h(x, i) = (h(x) + C i + C i ) mod m
2
1 2
where C and C are constants.
2
1
Double Hashing

h(x, i) = (h(x) + i mod m
}
another hash function
A Comparison of Rehashing Methods
Linear Probing m distinct probe sequences Primary clustering
Quadratic Probing m distinct probe sequences No primary clustering; but secondary clustering
2
Double Probing m distinct probe sequences No primary clustering
No secondary clustering
9.6 Summary

Hash functions are mostly used in hash tables, to quickly locate a data record (for example,

a dictionary definition) given its search key (the headword).

Specifically, the hash function is used to map the search key to the index of a slot in the
table where the corresponding record is supposedly stored.
Rehashing schemes use a second hashing operation when there is a collision.

LOVELY PROFESSIONAL UNIVERSITY 195