Data Structures and Algorithms
For a hash table with many elements kept at a load factor of about 0.5, which is the most appropriate reason that open addressing with linear probing tends to be faster than chaining (linking elements with linked lists)?
- AAfter a collision, the next position checked is the neighboring element, which is often in the same cache line or the next one, so fewer memory accesses are needed
- BOpen addressing has no collisions at all
- CChaining must compute the hash function two or more times
Show answer and explanation
Answer: A. After a collision, the next position checked is the neighboring element, which is often in the same cache line or the next one, so fewer memory accesses are needed
On modern CPUs, reading main memory after a cache miss takes far longer than computations such as comparisons. Linear probing checks the neighboring position after a collision, so most probes stay within the same cache line, and prefetching also helps. With chaining, the next element of a list is often somewhere else in memory, so each pointer followed is likely to cause a cache miss. Even with the same big-O complexity, the real speed can differ greatly depending on how memory is accessed. However, linear probing slows down sharply at high load factors as occupied positions cluster, so the load factor is kept fairly low.
- A. Correct. It only checks neighboring positions, so the data needed is likely to be in the cache already.
- B. Collisions also occur in open addressing; it handles them by checking the neighboring positions.
- C. Both compute the hash function once; the difference is in how memory is accessed.