Collision occurs when a hash value of a record being inserted hashes to an address that already contain a different record(i.e) when two key values hash to the same position.
The process of finding another position for the collide record is said to be collision resolution stategy.
Two categories of Hashing: àopen Hashing
a) Separate Chaining. -Linked list àClosed Hashing
i) Linear Probing. - Hi(X) = (HASH(X) +i) % tablesize
ii) Quadratic Probing - Hi(X) = (HASH(X) +i2) % tablesize iii)Double hashing. - Hi(X) = (HASH(X) +i* HASH2(X) % tablesize
HASH2(X)=R-(X % R) R is a prime number that is smaller than the table size
If the table gets too full,then the rehashing method builds new table that is a about twice as big and scan down the entier original hashtable ,computing the new hash value for each element and inserting it in the new table .
Rehashing is very expensive operation, the running time is O(N),since there are N element to rehashing and the table size roughly 2N.
Rehashing can be implemented in several ways with quadratic probing such as:
àRehashing,as soon as the table is half full;
àRehashing only when an insertion fails.
àRehashing when the table reaches a certain load factor
Eg:13,15,24,6 ,23are to be inserted in hash table of size 7.
The table will be 70% full.
A new table is created as the table is so full. The new hash function is then h(X) =X mod 17
Programmer does not worry about the table size.
Simple to implement.
Can be used in other data structures as well.