874 views

The keys $12, 18, 13, 2, 3, 23, 5$ and $15$ are inserted into an initially empty hash table of length $10$ using open addressing with hash function $h(k) = k \mod 10$ and linear probing. What is the resultant hash table?

A B C D
 $0$ $1$ $2$ $2$ $3$ $23$ $4$ $5$ $15$ $6$ $7$ $8$ $18$ $9$
 $0$ $1$ $2$ $12$ $3$ $13$ $4$ $5$ $5$ $6$ $7$ $8$ $18$ $9$
 $0$ $1$ $2$ $12$ $3$ $13$ $4$ $2$ $5$ $3$ $6$ $23$ $7$ $5$ $8$ $18$ $9$ $15$
 $0$ $1$ $2$ $2, 12$ $3$ $13, 3, 23$ $4$ $5$ $5, 15$ $6$ $7$ $8$ $18$ $9$

edited | 874 views

(C) is the correct option ..directly from the definition of linear probing. In linear probing, when a hashed location is already filled, locations are linearly probed until a free one is found.

http://courses.cs.washington.edu/courses/cse326/00wi/handouts/lecture16/sld015.htm

edited by
Note:

Separate Chaining  = Open Hashing/Closed Addressing (i.e. each key has a linked list, hence no probing)

Closed Hashing/Open Addressing (single array shared, hence probing required)
Here A & B options are incorrect, this is obvious. We are inserting 8 keys but only 4 are present. Hash is data structure for storing data, we don't loose data in Hash.

D is incorrect because it looks like chaining .

Using Linear Probing we get hash table of C. In linear probing, when a hashed location is already filled, locations are linearly probed until a free one is found.