Collision Resolution Techniques in Data Structure

Collision Resolution Techniques:

If two keys k1 and k2 produce same bucket index L for some hash function, then it is called Collision. Some collision resolution techniques are given below:

Types of Collision Resolution Techniques:

The collision resolution techniques can be classified into two broad categories:
1. Open Addressing
2. Chaining

Open Addressing:

The general procedure for open addressing can be stated as:
i. All keys are stored in the hash table only.

ii. When collisions occur, use a systematic procedure to store elements in free slots of the hash table.

Open Addressing can be classified into four types:
a. Linear probing: Suppose two keys k1 and k2 yield same memory location (bucket index) L.
H(k1)=L and H(k2)=L

Now, to resolve this collision, search the memory for an available place like:
L, L+1, L+2,….,L+i….
Store the key in the first available place.

b. Quadratic probing: Suppose two keys k1 and k2 yield same memory location (bucket index) L.
H(k1)=L and H(k2)=L

Now, to resolve this collision, search the memory for an available place like:
L, L+1², L+2²,…..,L+i²….
Store the key in the first available place.

c. Double hashing: Here, a double hash function is used to resolve the collisions. If two keys k1 and k2 yield the same memory location, then search the memory linearly for an available place like:
L, L+H’, L+2H’,….,L+iH’….
Store the key at the first available memory location.

d. Rehashing: If at any stage the hash table becomes full or overflows then it will be very difficult to find the free slot for a new key. In such a situation create a new hash table that is double in length as the previous one. Then scan the previous hash table and for each key calculate the new bucket index and store them into a newly created hash table.

Chaining:

The general procedure for chaining is:
i. Store all elements that have the same slot in a linked list.
ii. Store a pointer to the head of the linked list in the hash table slot.

Load Factor:

Suppose there are n items in the bucket and the bucket size is m. Then the load factor can be defined as –
Load factor = occupied space/total space
λ=n/m

Where λ=0 indicates an empty bucket λ=0.5 signifies that the bucket is half. Similarly, λ=1 means full bucket. For open addressing, λ can never exceed 1, but for chaining, there is no bar on the value of λ.