GATE CSE 2009 | Question: 36

Question

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. $\begin{array}{|l|l|} \hline 0 &   \\\hline 1 &  \\\hline 2 & 2  \\\hline 3 & 23 \\\hline 4 &  \\\hline 5 & 15 \\\hline 6 &   \\\hline 7 &  \\\hline 8 & 18 \\\hline 9 &  \\\hline  \end{array}$ 
• B. $\begin{array}{|l|l|} \hline 0 &   \\\hline 1 &  \\\hline 2 & 12  \\\hline 3 & 13 \\\hline 4 &  \\\hline 5 & 5 \\\hline 6 &   \\\hline 7 &  \\\hline 8 & 18 \\\hline 9 &  \\\hline  \end{array}$
• C. $\begin{array}{|l|l|} \hline 0 &   \\\hline 1 &  \\\hline 2 & 12  \\\hline 3 & 13 \\\hline 4 & 2 \\\hline 5 & 3 \\\hline 6 & 23   \\\hline 7 & 5  \\\hline 8 & 18 \\\hline 9 & 15  \\\hline  \end{array}$
• D. $\begin{array}{|l|l|} \hline 0 &   \\\hline 1 &  \\\hline 2 & 2,12   \\\hline 3 & 13,3,23  \\\hline 4 &  \\\hline 5 & 5,15   \\\hline 6 &   \\\hline 7 &  \\\hline 8 & 18 \\\hline 9 &  \\\hline  \end{array}$

Comments

It's lucky that even after mentioning open addressing also ,they've given clarity by mentioning that it's linear probing.

---

Open addressing (linear probing, quadratic, double hashing) → keys stay in table slots. 

so option c

---

i agree, hashing terms are very confusing

• $\underline{Open \ hasing} = seperate \ chaining \rightarrow$ It's called $\underline{open}$ because the data is allowed to leave the main array and grow out into the open space of your memory using linked lists
   
• also, $\underline{Open \ hashing }= \ \underline{closed \ addressing}$, i.e once you enter a slot you are closed there can't be mapped to any other slot
   
• $\underline{closed \ hasing} \rightarrow$ It's called $\underline{closed}$ because the data is strictly confined (closed in) to the fixed size of the hash table array. If there's a collision, you have to find an open address somewhere else inside the same array.
   
• also, $\underline{closed \ hasing} \rightarrow$ $\underline{Open \  addressing}$

Answer 1

(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

Comments

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)

Answer 2

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.