Question

A hash function f defined as f (key) = key mod 13, with linear probing is used to insert keys 55, 58, 68, 91, 27, 145. what will be the location of 79 ?

Answer 1

(A) 1

(B) 2

(C) 3

(D) 5

Answer(d).

Explanation. 55 mod13 is 3. 3 rd slot is given to 55.Occupied slot is(3)

58 mod 13 is 6 . 6th slot is given to 58.Ocuppied slots are (3,6)

68 mod 13 is 3 . which is preoccupied hence next free slot 4 is allotted. Occupied slots are (3,4,6).

91 mod 13 is 0. 0th slot is given to 91. Occupied slots are (0,3,4,6)

27 mod 13 is 1. 1st slot is given to 27. Occupied slots are (0,1,3,4,6)

145 mod 13 is 2. 2nd slot is given to 145. Occupied slots are (0,1,2,3,4,6)

79 mod 13 is 1. 1st slot is already occupied and searches for the next free slot, that is 5. 5 th slot is allotted to 79

Answer 2

the location of 79 is at index 5

Explanation:

Linear Probing:

In linear probing, we linearly probe for next slot.

For example, the typical gap between two probes is 1 .

Let hash(x) be the slot index computed using a hash function and S be the table size

If slot hash(x)  % S is full, then we try (hash(x) + 1) % S

If (hash(x) + 1) % S is also full, then we try (hash(x) + 2) % S

If (hash(x) + 2) % S is also full, then we try (hash(x) + 3) % S

so on,

Now in a given question

A hash function f defined as f (key) = key mod 13,

with linear probing is used to insert keys 55, 58, 68, 91, 27, 145.

we have to find the location of 79.

0    1    2    3   4   5   6   7   8   9   10    11    12    13

91   27  145   55  68  79  58

1. 55 is inserted, so 55%13 = 3.

• thus at index 3, 55 is stored

2. 58 is inserted, so 58%13 = 6.

• Thus, at index 6, 55 is stored

3. 68 is inserted, so 68%13 = 3. At 3 55 is already stored

•  thus, now (68+1)%13 = 4. Hence, at index 4, 68 is stored  

4. 91 is inserted, so 91%13 = 0.

• Thus, at index 0, 91 is stored

5. 27 is inserted, so 27%13 = 1.

• Thus, at index 1, 27 is stored

6. 145 is inserted, so 145%13 = 2.

• Thus, at index 2, 145 is stored

Now, 79 is inserted. Since 79%13 = 1. So 27 already occupied index 1.

So now (79+1)%13 = 2. Since, 145 also already occupied index 2.

Hence, (79+2)%13 = 3.  Since, 55 also already occupied index 3.

Hence, (79+3)%13 = 4.  Since, 68 also already occupied index 4.

Hence, (79+4)%13 = 5.  Now index 5 is empty so 79 will be stored at index 5.

hence, the location of 79 is at index 5