The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
1.4k views

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

  1. $3, 0,$ and $1$
  2. $3, 3,$ and $3$
  3. $4, 0,$ and $1$
  4. $3, 0,$ and $2$
asked in DS by Veteran (99.8k points)
edited by | 1.4k views

2 Answers

+26 votes
Best answer

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.

answered by Active (1.1k points)
edited by
+7
@Arjun sir, although the answer is correct, but I think that in Chaining, insertions in the list are performed in the beginning of the list to achieve constant time operation. If we insert into the end of the list, in worst case, insertion will take O(length of chain) as we will need to traverse the entire chain then. In the diagram above, the OP has inserted in the end of the chain.
+1
yes, but still searching will be O(length of chain) rt? Hashing takes care of this using proper hash function and load factor.
+3
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 ?
0 votes
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
answered by Loyal (8.3k points)


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

37,941 questions
45,453 answers
131,195 comments
48,210 users