Computer Science
Explainer
Why hash tables find things in O(1)
How can a table of a million items find one key in a single step?
Quick check · tap an answer to continue
Lesson notes
Key points
- A hash table stores key-value pairs in an array, so any slot can be reached directly by its index.
- A hash function converts the key, like a student ID, into a number, then takes it modulo the array size.
- Because computing the index takes constant time, average lookup, insert and delete are all O(1).
- Compare this with an unsorted list, where finding a key means scanning items one by one in O(n) time.
Definitions
- Hash table
- A data structure mapping keys to values by computing an array index from each key.
Takeaway: Hashing turns a key into an array index, giving O(1) average access.
Quick check: What gives a hash table its O(1) average lookup?
- Keeping keys sorted
- Computing the index directly
- Using a linked list
Hash tableHash functionO(1) averageO(1) vs O(n)
Lessons like this, for your syllabus.
Short narrated study videos written for your course, level and exam. Free to start.
Get lessons for your own syllabus