Hashing Techniques

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

What is Hashing?

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

Hashing Techniques

What is Hashing?

Hash Function Properties

Common Hash Functions

The Collision Problem

Collision Resolution Strategies

Open Addressing

Linear Probing

Quadratic Probing

Double Hashing

Chaining (Overflow Buckets)

Static vs. Dynamic Hashing

When to Use Hashing vs. Indexing

Real-World Applications

Continue learning this concept

Hashing Techniques

What is Hashing?

Hash Function Properties

Common Hash Functions

The Collision Problem

Collision Resolution Strategies

Open Addressing

Linear Probing

Quadratic Probing

Double Hashing

Chaining (Overflow Buckets)

Static vs. Dynamic Hashing

When to Use Hashing vs. Indexing

Real-World Applications

Continue learning this concept