A chained hash table has an array of 100 buckets. Assuming each bucket uses a…
2010
A chained hash table has an array of 100 buckets. Assuming each bucket uses a chain with no fixed capacity, what is the theoretical maximum number of entries the table can store?
Answer: D. There is no fixed upper limit — ConceptSeparate chaining resolves collisions by storing, at each hash-table bucket, a chain of all entries mapped to that bucket. The bucket array fixes the…
- A.
100
- B.
200
- C.
10000
- D.
There is no fixed upper limit
Attempted by 71 students.
Show answer & explanation
Correct answer: D
Concept
Separate chaining resolves collisions by storing, at each hash-table bucket, a chain of all entries mapped to that bucket. The bucket array fixes the number of hash indices, but it does not impose a fixed maximum length on each chain.
For m buckets and n entries, the load factor is α = n/m. With separate chaining, α may be greater than 1 because several entries can occupy the chain of the same bucket.
Application
Here m = 100 buckets.
For n stored entries, α = n/100.
Separate chaining does not require α ≤ 1; additional entries can be appended to bucket chains while nodes can be allocated.
Therefore the bucket-array size does not set a fixed maximum number of entries.
Cross-check and contrast
In open addressing, entries stay inside the 100 array slots, so the table would reach 100 occupied slots before resizing. Separate chaining stores collision chains outside that fixed slot count, confirming that the theoretical answer is: there is no fixed upper limit (practical memory is finite).