Register

GO Classes DPP | GATE CS, DA | Data Structure | Linear Probing

180 views
4 4 votes

A hash table of length $11$ is initially empty. The hash function is:

$H(key) = key \bmod 7$

Collisions are resolved using linear probing.

The following keys are inserted in order:

$87, ~40, ~30, ~6, ~11, ~22, ~98, ~20$

What is the average search length for an unsuccessful search?

  1. $4$
     
  2. $5.25$
     
  3. $6$
     
  4. $6.29$

2 Answers

3 3 votes

After insertion, the hash table becomes:

Index $0$: $98$

Index $1$: $22$

Index $2$: $30$

Index $3$: $87$

Index $4$: $11$

Index $5$: $40$

Index $6$: $6$

Index $7$: $20$

Index $8, 9, 10$: empty


Hash Table :

$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\text{Index} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline
\text{Key} & 98 & 22 & 30 & 87 & 11 & 40 & 6 & 20 & \text{-} & \text{-} & \text{-}\\
\hline
\end{array}$


Since the hash function is $key \bmod 7$, an unsuccessful search can start only from initial addresses $0$ to $6$.

Count probes until the first empty slot is reached:

For start $0$: check $0,1,2,3,4,5,6,7,8$, so $9$ probes

For start $1$: $8$ probes

For start $2$: $7$ probes

For start $3$: $6$ probes

For start $4$: $5$ probes

For start $5$: $4$ probes

For start $6$: $3$ probes


Probe count table : 

$\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
\text{Start Index} & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
\hline
\text{Probes till empty} & 9 & 8 & 7 & 6 & 5 & 4 & 3 \\
\hline
\end{array}$


So the average unsuccessful search length is:

$(9+8+7+6+5+4+3)/7 = 42/7 = 6$


Answer: C 

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

5 5 votes
3 3 answers
207
207 views
GO Classes asked Jul 18
207 views
GO Classes DPP | GATE CS, DA | Data Structure | Quadratic Probing
A hash table of length $11$ is initially empty. The hash function is:$H(key) = (key \times 3) \bmod 11$Collisions are resolved using quadratic probing:$H_k = (H_0 + k^2) ...
5 5 votes
2 2 answers
256
256 views
GO Classes asked Jul 18
256 views
GO Classes DPP | GATE CS, DA | Data Structure | Hash Collision
A key consists of three uppercase English letters. The hash value $h$ of a key is calculated as:$h = (\text{sum of alphabetical positions of the three letters}) \bmod 27$...
6 6 votes
3 3 answers
195
195 views
GO Classes asked Jul 18
195 views
GO Classes DPP | GATE CS, DA | Data Structure | Hash Collision
A hash table has size $10$. Each key is a lowercase English alphabet character from $a$ to $z$.The hash value of a key is defined as the last digit of its decimal ASCII c...
4 4 votes
3 3 answers
204
204 views
GO Classes asked Jul 18
204 views
GO Classes DPP | GATE CS, DA | Data Structure | Search Length in Hashing
Which of the following factors affect the average search length in hashing?Load factor Hash function Collision resolution method Only I and II Only I and III Only II and ...