Data Structures and Algorithms
Which correctly compares chaining (linking the elements at the same position into a linked list) and open addressing (finding another free position within the table) as ways to resolve hash table collisions? The load factor is the number of stored elements divided by the table size.
- AChaining can store elements even when the load factor exceeds 1, but open addressing cannot store more elements than the table size, and its number of probes rises sharply as the load factor approaches 1
- BOpen addressing has no collisions, so a search always takes one probe regardless of the load factor
- CWith chaining, the search cost stays the same however high the load factor becomes
Show answer and explanation
Answer: A. Chaining can store elements even when the load factor exceeds 1, but open addressing cannot store more elements than the table size, and its number of probes rises sharply as the load factor approaches 1
Chaining links elements at the same position into lists, so it can store more elements than the table size, but the average list length grows in proportion to the load factor and so does the search cost. Open addressing stores everything inside the table, so it can hold at most as many elements as the table size, and the number of probes to find a free slot rises sharply as the load factor approaches 1. With either method, it is usual to enlarge the table and reinsert all elements (rehash) once the load factor exceeds a chosen limit, such as about 0.5 to 0.75. Collisions also occur in open addressing; it handles them by looking for a free position.
- A. Correct. It accurately describes the difference in capacity and in how searches slow down at high load factors.
- B. Collisions also occur in open addressing; it handles them by looking for another free position.
- C. The average list length is proportional to the load factor, so a high load factor makes searches slower.