GATE CSE 2014 | Set 1 | Question: 40

Question

Consider a hash table with $9$ slots. The hash function is $h(k)= k \mod 9$. The collisions are resolved by chaining. The following $9$ keys are inserted in the order: $5, 28, 19, 15, 20, 33, 12, 17, 10$. The maximum, minimum, and average chain lengths in the hash table, respectively, are

• A. $3, 0,$ and $1$
• B. $3, 3,$ and $3$
• C. $4, 0,$ and $1$
• D. $3, 0,$ and $2$

Comments

Actually In chaing we store address of chain in hash table . initially all the node will contain NULL.  when hash value is computed It will search where to link that node then address of this node is stored in corresponding node.As such node will  be created for every new insertion.So it shows all the property of Single linked list like insertion deletion updation etc..Its Structure is somewhat similar to adjacency list.For a chaining i max length is not fixed so it is prefered hasing technique.

Answer 1

So, Maximum & minimum chain lengths are $3  \ \&  \ 0$ respectively.

Average chain length $= (0+3+1+1+0+1+2+0+1)/9 = 1$ .

So, Answer is A.

Comments

Yes, but in exam suppose order of elements in a chain is asked, then we should insert into the beginning of the list and proceed right ?

---

REMEMBER here Average chain length = (0+3+1+1+0+1+2+0+1)/9 , this nine (9) is total number of slot in the hash table (NOT THE NUMBER OF KEY)

---

Searching for this doubt. Thank You @register_user_19

Answer 2

Following are values of hash function for all keys

 5 --> 5
28 --> 1
19 --> 1  [Chained with 28]
15 --> 6
20 --> 2
33 --> 6  [Chained with 15]
12 --> 3
17 --> 8
10 --> 1 [Chained with 28 and 19]

The maximum chain length is 3. The keys 28, 19 and 10 go to same slot 1, and form a chain of length 3. The minimum chain length 0, there are empty slots (0, 4 and 7). Average chain length is (0 + 3 + 1 + 1 + 0 + 1 + 2 + 0 + 1)/9 = 1

Comments

Refer : https://www.geeksforgeeks.org/gate-gate-cs-2014-set-1-question-52/

---

Good one

Thanks

---

I am not able to understand how average length came can anyone clarify me pls

Answer 3

https://www.youtube.com/watch?v=eyX_Jrq14Lc

Answer 4

Here's another way to look at it,
The expected length of the linked list in chaining is $\alpha=\frac{n}{m}$ where $n$ is the number of keys and $m$ is the size of hash table. So here $n=9$ and $m=9$ which makes the average size as $1$. As for the maximum size it's apparent that $28,19,10$ all the three have $1$ modulo 10 as the highest length of linked list. So option $(A)$ is the answer

Answer 5

avg is  sum of all 0+3+1+1+0+1+2+0+1=9

9/9=1 avg

max = 3

min 0