Given the hash table, hash functions, and second hash function insert D E F G into the given hash table using double hashing.

QUESTION

h(A)=7 h(A)=4

h(B)=5 h(B)=1

h(C)=10 h(C)=2

h(D)=7 h(D)=2

h(E)=6 h(E)=3

h(F)=5 h(F)=2

h(G)=7 h(G)=3

SUMMARY

For the alphabets from A to G, two hash functions are given. For each alphabet, double hashing is performed to place it in the table.

Double hashing function:

[h(key) + (i*h2(key))] % table_size

When a collision occurs, i value will be incremented from 0 by 1.

ANSWER

table_size =11

1) D

h(D) = 7 (collision)

[h(D) + (1*h2(D))] % 11

= 9

table[9] = D

2) E

h(E) = 6 (no collision)

table[6] = E

3) F

h(F) = 7 (collision) (i=0)

(h2=2)

[h(F) + (1*h2(F))] % 11 = 7

[h(F) + (2*h2(F))] % 11 = 9

[h(F) + (1*h2(F))] % 11 = 0

table[0] = F

4) G

h(G) = 7 (collision)

(h2=3)

[h(G) + (1*h2(G))] % 11 = 10

[h(G) + (2*h2(G))] % 11 = 10

table[2] = G

Share this post