edited by
2,806 views
1 votes
1 votes

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

edited by

3 Answers

0 votes
0 votes
answer is c
0 votes
0 votes

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.

 

edited by
0 votes
0 votes

Answer is D.

option C : 1st 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.

Related questions

1 votes
1 votes
2 answers
2