The keys 5, 28, 19, 15, 26, 33, 12, 17, 10 are inserted into a hash table using the
hash function β(π) = π πππ 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 β(π) = π πππ 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
Correct Answer: 3
Solution and Explanation
Instead of listing hash values one by one, it helps to notice a pattern: since the table size is 9, keys that differ by a multiple of 9 always land in the same bucket.
Step 1: The keys 28, 19 and 10 are each exactly 9 apart from one another (\(28-19=9\), \(19-10=9\)), so all three automatically map to the same bucket, namely \(10 \bmod 9 = 1\).
Step 2: Check the remaining keys: \(5 \bmod 9 = 5\) (alone); \(15 \bmod 9 = 6\) and \(33 \bmod 9 = 6\) (\(33-15=18\), a multiple of 9, so they collide) giving bucket 6 with 2 keys; \(26 \bmod 9 = 8\) and \(17 \bmod 9 = 8\) (\(26-17=9\), so they collide) giving bucket 8 with 2 keys; and \(12 \bmod 9 = 3\), alone in its bucket.
Step 3: Tally the chain sizes: one bucket with 3 keys (bucket 1: 28, 19, 10), two buckets with 2 keys each (bucket 6: 15, 33 and bucket 8: 26, 17), and two buckets with a single key each (bucket 3: 12 and bucket 5: 5). No bucket exceeds 3 keys.
Conclusion: The longest chain, formed at bucket index 1, contains 3 keys, so the answer is 3.
Top Questions on Hashing
- Match the following:
List I List II 1 FIFO a Stack 2 Look up op. b Queue 3 Last-In first out c Hash table - Match the items in Column 1 with the items in Column 2 in the following table :
Column 1 Column 2 (p) First In First Out (i) Stacks (q) Lookup Operation (ii) Queues (r) Last In First Out (iii) Hash Tables - Consider performing uniform hashing on an open address hash table with load factor \(Ξ± = \frac{n}{m}< 1\), where n elements are stored in the table with m slots. The n m expected number of probes in an unsuccessful search is at most \(\frac{1}{1-\alpha}\)
Inserting an element in this hash table requires at most ______ probes, on average. - Want to practice more? Try solving extra ecology questions todayView All Questions
Questions Asked in GATE CS exam
A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the blockβs anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of \(b\) blocks needs \(\lceil \log_2 b \rceil\) block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.
- GATE CS - 2023
- Database Management Systems