search
Log In
22 votes
2.8k 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$
in DS
edited by
2.8k views
0
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.

3 Answers

35 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.


edited by
11
@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.
3
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 ?
7

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)

1 vote
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
0 votes
Answer:

Related questions

28 votes
3 answers
1
7.1k views
Consider a hash table with $100$ slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first $3$ slots are unfilled after the first $3$ insertions? $(97 \times 97 \times 97) / 100^3$ $(99 \times 98 \times 97) / 100^3$ $(97 \times 96 \times 95) / 100^3$ $(97 \times 96 \times 95 / (3! \times 100^3)$
asked Sep 28, 2014 in DS jothee 7.1k views
55 votes
9 answers
2
8.4k views
Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly $4$ nodes is $O(n^a\log^bn)$. Then the value of $a+10b$ is __________.
asked Sep 26, 2014 in DS jothee 8.4k views
38 votes
4 answers
3
5.9k views
Let $G=(V,E)$ be a directed graph where $V$ is the set of vertices and $E$ the set of edges. Then which one of the following graphs has the same strongly connected components as $G$ ? $G_1$ = $(V,E_1)$ where $E_1 = \left\{(u,v) \mid (u,v) \notin E\right\}$ $G_2$ ... of length $\leq2$ from $u$ to $v$ in $E\}$ $G_4$ = $(V_4,E)$ where $V_4$ is the set of vertices in $G$ which are not isolated
asked Sep 26, 2014 in DS jothee 5.9k views
18 votes
3 answers
4
3.1k views
Consider a hash table of size seven, with starting index zero, and a hash function $(3x + 4)\mod 7$. Assuming the hash table is initially empty, which of the following is the contents of the table when the sequence $1, 3, 8, 10$ is inserted into the table using closed hashing? Note that − denotes an empty location in the ... $3$ $1$, −, −, −, −, −, $3$ $1, 10, 8$, −, −, −,$ 3$
asked Sep 22, 2014 in DS Kathleen 3.1k views
...