DBMS Notes
Hashing is a data access technique that uses a mathematical function (called a hash function) to compute the storage address of a record directly from its...
What is Hashing?
Hashing is a data access technique that uses a mathematical function (called a hash function) to compute the storage address of a record directly from its search key value. Unlike index-based methods that traverse tree structures to locate data, hashing computes the exact bucket (disk block) where a record resides — offering the potential for single-step access with O(1) time complexity.
Think of it like a mail sorting system. Instead of searching through every mailbox to find where a letter belongs, the postal code directly tells you which area, route, and box to deliver to. The postal code acts as a hash function — given an address, it immediately produces the delivery location without searching.
Hash Function Properties
A good hash function must satisfy several properties:
| Property | Description | Why Important |
|---|---|---|
| Uniform Distribution | Maps keys evenly across all buckets | Prevents some buckets from overflowing while others stay empty |
| Deterministic | Same key always produces same address | Must find the record at the same location every time |
| Fast Computation | Minimal CPU time to evaluate | Function is called for every access; must be efficient |
| Minimizes Collisions | Different keys map to different buckets | Collisions require overflow handling, adding disk accesses |
Common Hash Functions
| Example | M = 13 buckets |
| K = 1234 | K² = 1522756 → middle digits = 227 → bucket 227 mod M |
| K = 123456 | 12 + 34 + 56 = 102 → 102 mod M |
| K = 987654 | extract positions 2,4,6 → 876 → 876 mod M |
The Collision Problem
A collision occurs when two different search key values hash to the same bucket address. Since buckets have fixed capacity, collisions can cause a bucket to overflow.
| Insert(10): h(10) = 0 | Bucket 0: [10] |
| Insert(25): h(25) = 0 | Bucket 0: [10, 25] ← bucket full |
| Insert(30): h(30) = 0 | Bucket 0 OVERFLOW! ← collision, no space |
Collisions are inevitable (by the Pigeonhole Principle — if you have more keys than buckets, at least one bucket must hold multiple keys). The question is how to handle them efficiently.
Collision Resolution Strategies
Open Addressing
When a collision occurs, probe other buckets in a systematic pattern to find an empty slot.
Linear Probing
If bucket h(K) is full, try h(K)+1, h(K)+2, h(K)+3, ...
Problem: Clustering — consecutive full buckets form clusters, degrading performance
Quadratic Probing
If bucket h(K) is full, try h(K)+1², h(K)+2², h(K)+3², ...
Problem: Secondary clustering — less severe but still occurs
Double Hashing
Use second hash function for step size: h₁(K) + i × h₂(K)
Best distribution but most complex to implement
Chaining (Overflow Buckets)
Each primary bucket has a pointer to a linked list of overflow buckets. When the primary bucket is full, new records are added to the overflow chain.
| Bucket 0: [10, 25] | Overflow Bucket 0a: [30, 45] → Overflow Bucket 0b: [60] |
| Bucket 1: [11, 36] | NULL (no overflow) |
| Bucket 2: [17, 22] | Overflow Bucket 2a: [42] |
| Access cost | 1 (primary bucket) + number of overflow buckets to traverse |
Static vs. Dynamic Hashing
| Aspect | Static Hashing | Dynamic Hashing |
|---|---|---|
| Number of Buckets | Fixed at creation time | Grows/shrinks with data |
| Overflow Handling | Overflow chains (degrade performance) | Split buckets to redistribute |
| Reorganization | Requires complete rehashing | Incremental restructuring |
| Space Utilization | May waste space or overflow heavily | Adapts to actual data volume |
| Examples | Traditional hash files | Extendible hashing, linear hashing |
When to Use Hashing vs. Indexing
| Criterion | Hashing | B+ Tree Indexing |
|---|---|---|
| Equality queries (WHERE id = 5) | Excellent — O(1) | Good — O(log n) |
| Range queries (WHERE age BETWEEN 20 AND 30) | Poor — must scan all buckets | Excellent — leaf-level traversal |
| Ordered access (ORDER BY) | Not supported | Natural with leaf linked list |
| Dynamic data (frequent inserts/deletes) | Static: problematic; Dynamic: good | Always handles well |
| Worst case | O(n) with many collisions | O(log n) guaranteed |
The key insight: use hashing when your workload is dominated by equality searches on the hash key. Use B+ trees when you need range queries, ordering, or guaranteed worst-case performance.
Real-World Applications
- Hash indexes in databases: MySQL MEMORY engine, PostgreSQL hash indexes
- Hash tables in programming: Python dictionaries, Java HashMaps use the same principles
- Distributed systems: Consistent hashing in load balancers and distributed caches (Redis, Memcached)
- Database joins: Hash join algorithm uses in-memory hash tables to match tuples efficiently
Continue the lesson path