GATE 2007 Example on Hashing

Consider a hash table of size seven, with starting index zero, and a hash function \((3x + 4) \ mod \ 7\). Assuming the hash
table is initially empty, which of the following is the contents of the table when the sequence 1, 3, 8, 10  is inserted into the
table using closed hashing? Note that _  denotes an empty location in the table.

 

A) 8, _, _, _, _, _, 10

B) 1, 8, 10, _, _, _, 3

C) 1, _, _, _, _, _, 3

D) 1, 10, 8, _, _, _, 3

Answer

Keys : 1 , 3, 8, 10

Hash Function : \((3x + 7) \ \% \ 7\)

position of 1: \((3*1 + 4 ) \ \% \ 7 = (7) \ \% \ 7 = 0\)             (1, _ , _ , _ , _ , _ , _ )

position of 3 : \((3*3 + 4 ) \ \% \ 7 = (13) \ \% \ 7 = 6\)          (1, _ , _ , _ , _ , _ , 3 )

position of 8 : \((3*8 + 4 ) \ \% \ 7 = (28) \ \% \ 7 = 0\)           (1, 8 , _ , _ , _ , _ , 3 )       ∵ position-0 is occupied ∴ go to the next empty cell    

position of 10: \((3*10 + 4 ) \ \% \ 7 = (34) \ \% \ 7 = 6\)        (1, 8 , 10 , _ , _ , _ , 3 )      ∵ position-6 is occupied ∴ go to the next empty cell 

Hence, Ans (B)

0Comment