The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+17 votes
1.2k 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$  
asked in DS by Veteran (59.7k points)
edited by | 1.2k views

2 Answers

+26 votes
Best answer

(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

answered by Boss (14.4k points)
edited by
+6
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)
+8 votes
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.
answered by Boss (43.2k points)
Answer:

Related questions

+5 votes
1 answer
7
asked Nov 2, 2014 in DS by Arjun Veteran (367k points) | 617 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

44,062 questions
49,583 answers
162,856 comments
65,776 users