Answer:
a) Linear probing is one of the hashing technique in which we insert values into the hash table indexes based on hash value.
Hash value of key can be calculated as :
H(key) = key % size ;
Here H(key) is the index where the value of key is stored in hash table.
----------
Given,
Keys to be inserted are : 5 , 205, 406,5205, 8205 ,307
and size of the array : 100.
First key to be inserted is : 5
So, H(5) = 5%100 = 5,
So, key 5 is inserted at 5th index of hash table.
-----
Next key to inserted is : 205
So, H(205) = 205%100 = 5 (here collision happens)
Recompute hash value as follows:
H(key) =(key+i) % size here i= 1,2,3...
So, H(205) =( 205+1)%100 = 206%100 = 6
So, key 205 is inserted in the 6th index of the hash table.
----------
Next Key to be inserted : 406
H(406) = 406%100 = 6(collision occurs)
H(406) =(406+1) %100 = 407%100 = 7
So, the value 406 is inserted in 7the index of the hash table.
-----------------
Next key : 5205
H(5205) = 5205%100 = 5(collision)
So, H(5205) = (5205+1)%100 = 6( again collision)
So, H(5205) = 5205+2)%100 = 7(again collision)
So, H(5205) = (5205+3)%100 = 8 ( no collision)
So, value 5205 is inserted at 8th index of the hash table.
-------------
Similarly 8205 is inserted at 9th index of the hash table because , we have collisions from 5th to 8th indexes.
-------------
Next key value is : 307
H(307) = 307%100 = 7(collision)
So, (307+3)%100 = 310%100 = 10(no collision)
So, 307 is inserted at 10th index of the hash table.
So, hash table will look like this:
Key index
5 5
205 6
406 7
5205 8
8205 9
307 10
b) Quadratic probing:
Quadratic probing is also similar to linear probing but the difference is in collision resolution. In linear probing in case of collision we use : H(key) = (key+i)%size but here we use H(key) =( key+i^2)%size.
Applying Quadratic probing on above keys:.
First key to be inserted : 5.
5 will go to index 5 of the hash table.
-------
Next key = 205 .
H(205) = 205%100 = 5(collision)
So. H(key)= (205+1^2)%100 = 6(no collision)
So, 205 is inserted into 6th index of the hash table.
--------
Next key to be inserted 406:
So, 406 %100 = 6 (collision)
(406+1^2)%100 = 7(no collision)
So, 406 is moved to 7th index of the hash table.
----------
Next key is : 5205
So, 5205%100 = 5 (collision)
So, (5205+1^2)%100 = 6 ( again collision)
So, (5205+2^2)%100 = 9 ( no collision)
So, 5205 inserted into 9th index of hash table.
-----------
Next key is 8205:
Here collision happens at 5the , 6the , 9th indexes,
So H(8205) = (8205+4^2)%100 = 8221%100 = 21
So, value 8205 is inserted in 21st index of hash table.
--------
Next value is 307.
Here there is collision at 7the index.
So, H(307) = (307+1^2)%100 = 308%100= 8.
So, 307 is inserted at 8the index of the hash table.
Key Index
5 5
205 6
406 7
5205 9
8205 21
307 8
