Course contentsShow
← Computer Science
Lesson 1692 of 2,87238. Database Transactions and IndexingFree lesson

O(1) Lookup with Hash Indexes

Understand why hash indexes provide constant-time average-case lookups and the conditions required for this performance.

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:

  1. Good hash function: Must distribute keys uniformly across buckets to avoid clustering
  2. Low collision rate: Few keys should hash to the same bucket (handled by techniques from your previous lesson)
  3. Adequate bucket space: The hash table shouldn't be overcrowded (typically keeping load factor below 0.7-0.8)
  4. Exact-match queries only: Hash indexes excel at WHERE id = 42, but fail at range queries like WHERE 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.