Question

1) Suppose that you have table size M=101 and you are using double hashing. The first hash function h1, is used to determine the home position, and the second hash , h2, is used to determine the increment for linear probing. Suppose you have two records with keys k1, and k2, such that: h1(k1) = 5, h2(k1)= 3, h1(k2) = 5, h2(k2) = 11. Note: h2 is returning an offset, not an index.

Fill in the Blank :

The First Probe index location for k1 is ___. The first probe index location for k2 is __.

2) For the following indicate if it is important feature for the probe function, hash function, or both.

a) Probe function should spread out data.

b) Hash Function should be fully determine by the data being hashed

c) Hash function should use all the input data.

Answer 1

1) Double Hashing: It uses two hash functions:

1. h1 computes the home position

2. h2 computes the increment for linear probing

So, probe sequence: h1, h1 + h2, h1 + 2*h2, h1+3*h2 …..

Given two records with keys k1 and k2,

For key k1, h1(k1)=5 h2(k1)=3

For key k2, h1(k2)=5 h2(k2)=11

First Probe index location for k1 is h1(k1)+h2(k1)=5+3=8

First Probe index location for k2 is h1(k2)+h2(k2)=5+11=16

Hence, the First Probe index location for k1 is 8 . The first probe index location for k2 is 16  .

When the collision occurs at place at location 5, we have to place key at first probe.

For k1, first probe is 8

For k2, first probe is 16.

If collision occurs at first probe, key should be placed in the second probe i.e h1+2*h2 and so on.......