Collision Resolution Techniques
Collision in Hashing
The hash function may return the same hash value for two or more keys. When two
or more keys have the same hash value, a collision happens. To handle this collision, we use
collision resolution techniques.
Collision Resolution Techniques
There are two types of collision resolution techniques.
Separate chaining (open hashing)
Open addressing (closed hashing)
Separate chaining:
This method involves making a linked list out of the slot where the collision
happened, then adding the new key to the list. Separate chaining is the term used to
describe how this connected list of slots resembles a chain. It is more frequently utilized
when we are unsure of the number of keys to add or remove.
Time complexity
Its worst-case complexity for searching is o(n).
Its worst-case complexity for deletion is o(n).
Advantages of separate chaining
It is easy to implement.
The hash table never fills full, so we can add more elements to the chain.
It is less sensitive to the function of the hashing.
Disadvantages of separate chaining
In this, the cache performance of chaining is not good.
Memory wastage is too much in this method.
It requires more space for element links.
Open addressing:
To prevent collisions in the hashing table, open addressing is employed as a
collision-resolution technique. No key is kept anywhere else besides the hash table. As a
result, the hash table’s size is never equal to or less than the number of keys. Additionally
known as closed hashing.
The following techniques are used in open addressing:
Linear probing
Quadratic probing
Double hashing
1
Mrs. B.PANDISELVI, M.E, AP/CSE AD3251 DSD
Linear probing:
This involves doing a linear probe for the following slot when a collision occurs
and continuing to do so until an empty slot is discovered.
The worst time to search for an element in linear probing is O. The cache performs best
with linear probing, but clustering is a concern. This method’s key benefit is that it is
simple to calculate.
Disadvantages of linear probing:
The main problem is clustering.
It takes too much time to find an empty slot.
Quadratic probing:
When a collision happens in this, we probe for the i2-nd slot in the ith iteration,
continuing to do so until an empty slot is discovered. In comparison to linear probing,
quadratic probing has a worse cache performance. Additionally, clustering is less of a
concern with quadratic probing.
Double hashing:
In this, you employ a different hashing algorithm, and in the ith iteration, you look
for (i * hash 2(x)). The determination of two hash functions requires more time. Although
there is no clustering issue, the performance of the cache is relatively poor when using
double probing.
Example: Given input {4371,1323,6173,4199,4344,9679,1989} and a hash function
h(x)=x(mod 10), show the resulting.
(i) open hash table (ii) closed hash table using linear probing (iii) closed hash table using
quadratic probing (iv) closed hashing.
solution: table size : 10
(i) open hash table (separate chaining)
{4371,1323,6173,4199,4344,9679,1989}
0
4371 h(x)=x mod 10
1
1. 4371%10= 1
2
1323 6173 2. 1323 %10= 3
3
3. 6173%10= 3
4
4344 4. 4199%10= 9
5 5. 4344%10= 4
6 6. 9679%10 = 9
7 7. 1989%10= 9
8
9 4199 9679 1989
2
Mrs. B.PANDISELVI, M.E, AP/CSE AD3251 DSD
(ii) closed hash table using linear probing.
{4371,1323,6173,4199,4344,9679,1989}
0 9679 h(x)=x mod 10
1 4371 1. 4371%10= 1
2 1989 2. 1323 %10= 3
3 1323 3. 6173%10= 3, 3 reserved
4 6173 so store in 4
5 4344 4. 4199%10= 9
6 5. 4344%10= 4, 4 reserved
7 so store in 5
8 6. 9679%10 = 9, 9 reserved
9 4199 so store in 0
7. 1989%10= 9, 9 reserved
so store in 0, 0 also
reserved store in 1, 1 also
reserved store in 2
(iii) closed hash table using quadratic probing
{4371,1323,6173,4199,4344,9679,1989}
choose the index value like +1,+4,+9,+16.....(12, 22, 32.......)
0 9679 h(x)=x mod 10
1 4371 1. 4371%10= 1
2 2. 1323 %10= 3
3 1323 3. 6173%10= 3, 3 reserved so store in
4 6173 +1 position. ie, 4.
5 4344 4. 4199%10= 9
6 5. 4344%10= 4, 3 reserved so store in
7 +1 position away. ie, 5.
8 1989 6. 9679%10 = 9, 3 reserved so store in
9 4199 +1 position away. ie, 0
7. 1989%10= 9, 3 reserved so store in
+1 position. ie, 0, 0 reserved so store
in +4 (0,1,2,3,) position. ie, 3 , 3
reserved so store in +9(ie, already 4
positions checked(from 0,1,2,3 and
remaining 5 position is (4,5,6,7,8)
position. ie, 8
3
Mrs. B.PANDISELVI, M.E, AP/CSE AD3251 DSD
(iv) closed hashing
{4371,1323,6173,4199,4344,9679,1989}
0 h(x)=x mod 10
1 4371 1. 4371%10= 1
2 2. 1323 %10= 3
3 1323 3. 6173%10= 3 already
4 4344 reserved so not store .
5 4. 4199%10= 9
6 5. 4344%10= 4
7 6. 9679%10 = 9 already
reserved so not store .
8
7. 1989%10= 9 already
9 4199
reserved so not store .
(v) Double Hashing:
{4371,1323,6173,4199,4344,9679,1989}
calculate the double hash function :
1. h1(x)=x mod 10
2. h2(x)=7-(x mod 7), how to find h2 (prime no below table size ie, here table size is 10, prime
no below 10 is (1,3,5,7) from these we select max prime ie, 7).
0 1. h1(x)=x mod 10 6. 9679%10 = 9 = h1(x)
1 4371 2. h2(x)=7-(x mod 7) already reserved so ,
2 1. 4371%10= 1 h2(x)=7-(9679 mod 7)=7-5=2
3 1323 2. 1323 %10= 3 h(x,i)=(h1(x)+i*h2(x))%table
4 6173 3. 6173%10= 3=h1(x), already size(10)
5 9679 reserved so calculate i=1,2,3,4.... upto found
6 h2(x)=7-(6173 mod 7)=7-6=1 empty space
7 4344 h(x,i)=(h1(x)+i*h2(x))%table size(10) h(x,1)= (9+1*2)%10
i=1,2,3,4.... upto found empty space =11%10=1, 1 also reserved,
8
h(x,1)= (3+1*1)%10 =4%10=4 is h(x,2)= (9+2*2)%10
9 4199
empty store here. =13%10=3 is also reserved,
4. 4199%10= 9 h(x,3)= (9+3*2)%10=
5. 4344%10= 4 =h1(x), already 15%10 =5 is empty store
reserved so calculate here.
h2(x)=7-(4344 mod 7)=7-4=3
h(x,i)=(h1(x)+i*h2(x))%table size(10) 7.1989%10= 9 already
i=1,2,3,4.... upto found empty space reserved so try upto
h(x,1)=(4+1*3)%10 =7%10=7 is i=1,2,3,...9 cannot get empty
empty store here. space so this value cannot be
inserted .
4
Mrs. B.PANDISELVI, M.E, AP/CSE AD3251 DSD
