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.
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.