Question:
The keys \(5, 28, 19, 15, 26, 33, 12, 17, 10\) are inserted into a hash table using the hash function \(h(k) = k \bmod 9\). The collisions are resolved by chaining. After all the keys are inserted, the length of the longest chain is _____. (answer in integer)
The keys \(5, 28, 19, 15, 26, 33, 12, 17, 10\) are inserted into a hash table using the hash function \(h(k) = k \bmod 9\). The collisions are resolved by chaining. After all the keys are inserted, the length of the longest chain is _____. (answer in integer)
Show Hint
Compute k mod 9 for every key and group the keys that land in the same slot; the longest chain is the largest such group.
Updated On: Jul 22, 2026
Show Solution
Verified By Collegedunia
Correct Answer: 3
Solution and Explanation
Step 1: Recall chaining with a hash table.
In chaining, each slot of the hash table points to a linked list, a chain. When two keys hash to the same slot, they both go into that slot's chain, one after another. The chain length for a slot is simply the number of keys that landed in it.
Step 2: Compute the hash value of every key.
The hash function is \(h(k) = k \bmod 9\), so we take each key modulo 9.
\(h(5) = 5 \bmod 9 = 5\)
\(h(28) = 28 \bmod 9 = 1\), since \(28 = 3 \times 9 + 1\)
\(h(19) = 19 \bmod 9 = 1\), since \(19 = 2 \times 9 + 1\)
\(h(15) = 15 \bmod 9 = 6\), since \(15 = 1 \times 9 + 6\)
\(h(26) = 26 \bmod 9 = 8\), since \(26 = 2 \times 9 + 8\)
\(h(33) = 33 \bmod 9 = 6\), since \(33 = 3 \times 9 + 6\)
\(h(12) = 12 \bmod 9 = 3\), since \(12 = 1 \times 9 + 3\)
\(h(17) = 17 \bmod 9 = 8\), since \(17 = 1 \times 9 + 8\)
\(h(10) = 10 \bmod 9 = 1\), since \(10 = 1 \times 9 + 1\)
Step 3: Group keys by their slot.
Slot 1: keys \(28, 19, 10\), a chain of length 3.
Slot 3: key \(12\), a chain of length 1.
Slot 5: key \(5\), a chain of length 1.
Slot 6: keys \(15, 33\), a chain of length 2.
Slot 8: keys \(26, 17\), a chain of length 2.
Step 4: Find the longest chain.
Comparing the chain lengths 3, 1, 1, 2, 2 across all occupied slots, the largest value is 3, coming from slot 1 which holds \(28, 19, 10\).
Final Answer:
The longest chain has length 3.
\[ \boxed{3} \]
In chaining, each slot of the hash table points to a linked list, a chain. When two keys hash to the same slot, they both go into that slot's chain, one after another. The chain length for a slot is simply the number of keys that landed in it.
Step 2: Compute the hash value of every key.
The hash function is \(h(k) = k \bmod 9\), so we take each key modulo 9.
\(h(5) = 5 \bmod 9 = 5\)
\(h(28) = 28 \bmod 9 = 1\), since \(28 = 3 \times 9 + 1\)
\(h(19) = 19 \bmod 9 = 1\), since \(19 = 2 \times 9 + 1\)
\(h(15) = 15 \bmod 9 = 6\), since \(15 = 1 \times 9 + 6\)
\(h(26) = 26 \bmod 9 = 8\), since \(26 = 2 \times 9 + 8\)
\(h(33) = 33 \bmod 9 = 6\), since \(33 = 3 \times 9 + 6\)
\(h(12) = 12 \bmod 9 = 3\), since \(12 = 1 \times 9 + 3\)
\(h(17) = 17 \bmod 9 = 8\), since \(17 = 1 \times 9 + 8\)
\(h(10) = 10 \bmod 9 = 1\), since \(10 = 1 \times 9 + 1\)
Step 3: Group keys by their slot.
Slot 1: keys \(28, 19, 10\), a chain of length 3.
Slot 3: key \(12\), a chain of length 1.
Slot 5: key \(5\), a chain of length 1.
Slot 6: keys \(15, 33\), a chain of length 2.
Slot 8: keys \(26, 17\), a chain of length 2.
Step 4: Find the longest chain.
Comparing the chain lengths 3, 1, 1, 2, 2 across all occupied slots, the largest value is 3, coming from slot 1 which holds \(28, 19, 10\).
Final Answer:
The longest chain has length 3.
\[ \boxed{3} \]
Was this answer helpful?
0
0
Top GATE CS Programming and Data Structures Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- Given N distinct elements in an array, determine the number of comparisons required to find the element which is not the largest:
Consider the following code:
main() { int x = 126, y = 105; { if (x > y) x = x - y; else y = y - x; } while (x != y) printf("%d", x); }- In a binary search tree with the following elements: \( 10, -4, 15, 13, 20, 5, 16, 19 \), the number of edges from node 19 to the root is?
Consider the following code:
int a; int arr[] = {30, 50, 10}; int *ptr = arr[10] + 1; a = *ptr; (*ptr)++; ptr = ptr + 1; printf("%d", a + arr[1] + *ptr);
View More Questions
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?
View More Questions