🧥 Introduction: The Coat Check
Imagine you go to a fancy museum and hand your coat to the attendant.
The attendant gives you a tiny plastic ticket with the number #42 on it.
- When you leave, you hand the attendant ticket #42.
- The attendant doesn't browse alphabetically through a list of names, nor do they walk aisle-by-aisle. They walk directly to hanger hook #42 and grab your coat instantly!
In databases, a Hash Index is this exact ticket system! It takes a column value, runs it through a math function to get a unique bucket address (like hanger #42), and jumps straight to the data row in one single step ($O(1)$ time complexity).
⚙️ How Hash Indexes Work
A Hash Index uses a mathematical function called a Hash Function to map keys directly to bucket pointers:
Search Key (e.g. "Alice")
|
v
+-----------------+
| HASH FUNCTION | <--- Mathematical converter (e.g., md5 or modulo)
+-----------------+
|
Calculates 42
|
v
HASH BUCKET LIST DATA TABLE
+------------+----------+ +----+----------+-------------+
| Bucket ID | Pointer | | ID | Username | Country |
+------------+----------+ +----+----------+-------------+
| 41 | Null | | 1 | Bob | USA |
| 42 | Row #2 | -----------> | 2 | Alice | Canada |
| 43 | Row #3 | | 3 | Charlie | UK |
+------------+----------+ +----+----------+-------------+
The Trade-off: Equality vs. Range
Hash indexes are the fastest possible indexes for exact match queries, but they have major limitations:
- Perfect for Equality (
=): FindingWHERE username = 'Alice'takes exactly 1 step. - Useless for Ranges (
>,<,BETWEEN): Because hash values are scattered randomly, a hash index cannot help you find users withage > 21. The database has to fall back to a full Table Scan! - Useless for Sorting: The keys in a hash index are not sorted. You cannot use them to speed up
ORDER BYqueries.
💻 Code Examples
Let's simulate a hash index lookup structure in different languages.
SQL Setup (PostgreSQL example)
-- Create a Hash Index for exact equality checks
CREATE INDEX idx_user_hash_email ON users USING HASH (email);Multi-Language Execution
⚠️ Common Mistakes
1. Using Hash Indexes for Range Queries
Trying to speed up queries like WHERE age BETWEEN 18 AND 30 using a Hash Index. The index cannot help, forcing the database to perform a slow Table Scan. Use a B-Tree index for range queries.
2. Hash Collisions
When two different keys generate the exact same hash value. The database has to store both keys in a linked list inside the bucket, slowing down matches if there are many collisions.
🔍 Interview Corner
Q1: Why can't we use a Hash Index for range queries like BETWEEN 10 and 20?
A Hash function maps keys to buckets randomly to distribute them evenly (e.g. hash(10) might be bucket 42, while hash(11) is bucket 1). Because the values are not sorted, the index cannot locate sequential intermediate values without checking every bucket.
Q2: What is the time complexity of a Hash Index lookup compared to a B-Tree Index?
- Hash Index: Average time complexity is $O(1)$ (constant time) because it computes the address math directly.
- B-Tree Index: Time complexity is $O(log N)$ (logarithmic time) because it must traverse the tree levels.
📝 Summary
- Hash Indexes provide $O(1)$ search speeds by using hash mathematical formulas.
- They are excellent for equality comparisons (
=orIN). - They do not support range queries (
>,<,BETWEEN) or sorting.