Algorithms and Data Structures · Junior · Question 12 of 75
What is the main idea of a hash table?
- 1Store key-value pairs in a linked list in insertion order
- 2Keep keys sorted so they can be found with binary search
- ✓Correct answer: Turn a key into an index with a hash function and store the value there
Explanation
The hash function maps a key to a bucket index, so the value can be found without scanning all entries. That gives O(1) average time for insert, lookup and delete.