UPPCL AE 2018:53

Question

Consider a hash table of size $7$ implemented using an array $A[0 \dots 6].$ A modulo hash function $\text{(MOD 7)}$ is used to map the keys, and open addressing is used to handle collisions. If $53, 32, 43, 51, 99$ are inserted into the hash table, the contents of array $A$ is 

• A. $\text{EMPTY}, 43, 51, 99, 32, 53, \text{EMPTY}$
• B. $\text{EMPTY}, 99, 43, 51, 32, 53, \text{EMPTY}$
• C. $\text{EMPTY}, 43, 51, 99, 53, 32, \text{EMPTY}$
• D. $\text{EMPTY}, 43, 99, 51, 32, 53, \text{EMPTY}$

Answer 1

Inserted Numbers:  53,32,43,51,99          Collision Resolution : Open Addressing by default Linear Probing

Hash Function: Mod 7

Index for 53:    53%7 = 4 

Index for 32:    32%7 = 4 but already 53 is there hence Probe next i.e 5 Yes available So,5

Index for 43:     43%7 = 1

Index for 51:     51%7 = 2

Index for 99:     99%7 = 1 but 43 is there hence Probe next i.e 2 but that also not available So next i.e 3 Yes available.

 

6
5	32
4	53
3	99
2	51
1	43
0

Content of Array[0...6] = EMPTY,43,51,99,53,32,EMPTY