O(1) Lookup with Hash Indexes
What you'll learn: You'll understand why hash indexes deliver constant-time lookups on average and what conditions must hold for this performance guarantee.
The Speed Promise of Hash Indexes
Hash indexes achieve O(1) average-case lookup time, meaning they can find a record in roughly constant time regardless of how many records exist in the table. This is their superpower compared to B-tree indexes, which require O(log n) time.
How Constant-Time Works
When you search for a key, the hash function instantly computes which bucket contains your data—no traversing a tree or scanning multiple locations. It's like having a perfect filing system where you immediately know which drawer holds your document without opening any others.
The calculation: Hash function runs in O(1) → Jump to bucket in O(1) → Retrieve value in O(1) = O(1) total
Critical Conditions Required
This performance isn't free. Hash indexes need:
- Good hash function: Must distribute keys uniformly across buckets to avoid clustering
- Low collision rate: Few keys should hash to the same bucket (handled by techniques from your previous lesson)
- Adequate bucket space: The hash table shouldn't be overcrowded (typically keeping load factor below 0.7-0.8)
- Exact-match queries only: Hash indexes excel at
WHERE id = 42, but fail at range queries likeWHERE id > 42
When Performance Degrades
If too many collisions occur in one bucket, you get O(k) time where k = keys per bucket. In the worst case (all keys hash to one bucket), lookups degrade to O(n) linear search—defeating the purpose entirely.
Key Takeaway: Hash indexes provide O(1) average-case lookups when using a quality hash function with even distribution and low collision rates, but only for exact-match equality queries.