##### 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

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)