Question

Which of the following variant of a hash table has the best cache performance?

(a) hash table using a linked list for separate chaining

(b) hash table using binary search tree for separate chaining

(c) hash table using open addressing

(d) hash table using a doubly linked list for separate chaining

Enquiry is from Hash Tables in section Hash Tables of Data Structures & Algorithms I

The question was posed to me in quiz.

Answer 1

The correct choice is (c) hash table using open addressing

Easy explanation - Implementation of the hash table using open addressing has a better cache performance as compared to separate chaining. It is because open addressing stores data in the same table without using any extra space.