A hash function h defined h(key)=key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18?

Concept:

Hashing is used to uniformly distribute key values into the table using a hash function. In linear probing, when allocating location to the key values, if there occurs a collision, then we linearly probe for the next vacant location and allocate that to the key.

Explanation:

Hash function: h(key) = key mod 7

Keys are 44, 45, 79, 55, 91, 18, 63

Table size = 7( 0 to 6)

Step 1: key is 44 , h(44) = 44 mod 7 = 2,

Key 44 will move into index 2.

Step 2: Next 45, h(45)= 45 mod 7 = 3

45 will move to index 3.

Step 3: key 79, h(79) = 79 mod 7 = 2 (collision as, there is already a key value at index 2).

So, 79 will go for the next empty location, i.e. 4

Step 4: next key is 55, h(55) = 55 mod 7 = 6,

Key 55 will go into index 6.

Step 5: key 91, h(91) = 91 mod 7 = 0

Step 6: key 18, h(18) = 18 mod 7 = 4 (collision , move to next empty location i.e. 5)

Step 7: key 63, h(63) = 63 mod 7 = 0 (due to collision, it will move into index 1)

Therefore, the location of 18 elements is 5