Algorithm :- Hashing

Question

Consider a hash table consisting of M=11 slots, and suppose integer key value are hashed into the table using hash function h1:

int h1(int key)
{
    x = (key + 5)*(key + 5);
    x = x/6;
    x = x + key;
    x = x%11;
    return x;
}

Suppose that collisions are resolved using linear probing. The probe in sequence is given therefore by

h1(k) + i(mod)11

The integer key values listed below are to be inserted, in the order given below. What are the final contents of the hash table after the following key values have been inserted in the given order:
43, 23, 1, 0, 15, 31, 4, 7, 11, 3

Source:- http://www.techtud.com/example/hashing

Answer 1

Answer is D.

option C : 1^st 4 elements are going to right place but just don’t blindly conclude, you will have to try all elements.

15 is not hashed to 1st place. :) . So Option C is wrong.

Answer 2

answer is c

Comments

how you solved this can u please elaborate?

---

apply hash function for the input 0(take any value), we will get the index at which it should be stored in the hash table.

h1(0) = 4, hence 0 will be stored at index 4 of the hash table.

---

what is i here?

are u saying h(43)+43mod 11?

---

i is used when collision is detected, suppose if we are filling a table and at index 5 already value there then increase the value i and calculate for the index again.

i ranges from {0,1,2,.......,(M-1)}.

Answer 3

Ans - C)

Take small value first. Lets take 0, Pass Key =  0 in program.

1. X = garbage
2. X = ( 0 + 5 )*(0 + 5) = 25
3. X = 25/16 = 1(only integer part because x is integer)
4. X = 1 + 0 = 1
5. X = 1 % 11 = 1
6. Return 1
7. So put h1(k) = 1.
8. ( 1 + 0 ) mod11 = 1 so update the index position 1 = 0

Repeat same for all, you'll get (c) as answer.

Note : i ranges from {0,1,2,.......,(M-1)}. So if any collision detected increase the i value.