Hashing Hash Functions · Open Addressing · Chaining
Hashing in Data Structures
Hash Functions · Open Addressing · Overflow Handling (Chaining)
1. Introduction to Hashing
Hashing is a technique in which we convert a piece of data (key) directly into an
array index (address) so that data can be stored and retrieved very quickly in
constant time O(1).
Hashing is a data structure technique used to store and retrieve data in constant average time O(1).
It is widely used in:
• Databases (fast searching)
• Compilers (symbol tables)
• Caches (CPU memory)
• Dictionaries (key-value mapping)
Example: Imagine you have a library with many books. Each book has a unique ID number.
Now you want to find a book:
� Normal method: You check each shelf one by one (slow ❌)
� Hashing method: You directly get the shelf number using a formula and go straight to it (fast ✔)
1.1 Basic Idea
Hashing converts a key (input data) into an index (address in table) using a function called a hash
function.
Example
If key = 45 and table size = 10
45 % 10 = 5
→ Value stored at index 5
BSCS — Hashing in Data Structures | Lecture Notes
, Hashing Hash Functions · Open Addressing · Chaining
DIAGRAM 1 — Hash Table Structure (Visual Memory)
How a hash function maps keys to array indices
KEY (Input)
+-----------------------------------------------------------------------------+
| HASH FUNCTION |
| h(k) = k mod m Here k = key (45) and m = table size (10) |
| |
+-----------------------------------------------------------------------------+
INDEX = h(k)
+----+----+----+----+----+----+----+----+----+----+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
+----+----+----+----+----+----+----+----+----+----+
| | | | | | 45 | | | | |
+----+----+----+----+----+----+----+----+----+----+
45 % 10 = 5 → stored here
If 25 also inserted: 25 % 10 = 5 → COLLISION!
2. Hash Table Structure
A hash table is an array-based structure where data is stored using indices generated by a hash
function.
2.1 Components
• Key → input value (e.g., student ID)
• Hash Function → converts key into index
• Hash Table → array storing data
• Collision Handling → resolves conflicts
3. Hash Functions
A hash function maps a key to a fixed range of values (table index).
3.1 Characteristics of Good Hash Function
• Fast computation
• Uniform distribution
• Minimum collisions
• Valid index generation
4. Division Method (Most Important Hash Function)
BSCS — Hashing in Data Structures | Lecture Notes
Hashing in Data Structures
Hash Functions · Open Addressing · Overflow Handling (Chaining)
1. Introduction to Hashing
Hashing is a technique in which we convert a piece of data (key) directly into an
array index (address) so that data can be stored and retrieved very quickly in
constant time O(1).
Hashing is a data structure technique used to store and retrieve data in constant average time O(1).
It is widely used in:
• Databases (fast searching)
• Compilers (symbol tables)
• Caches (CPU memory)
• Dictionaries (key-value mapping)
Example: Imagine you have a library with many books. Each book has a unique ID number.
Now you want to find a book:
� Normal method: You check each shelf one by one (slow ❌)
� Hashing method: You directly get the shelf number using a formula and go straight to it (fast ✔)
1.1 Basic Idea
Hashing converts a key (input data) into an index (address in table) using a function called a hash
function.
Example
If key = 45 and table size = 10
45 % 10 = 5
→ Value stored at index 5
BSCS — Hashing in Data Structures | Lecture Notes
, Hashing Hash Functions · Open Addressing · Chaining
DIAGRAM 1 — Hash Table Structure (Visual Memory)
How a hash function maps keys to array indices
KEY (Input)
+-----------------------------------------------------------------------------+
| HASH FUNCTION |
| h(k) = k mod m Here k = key (45) and m = table size (10) |
| |
+-----------------------------------------------------------------------------+
INDEX = h(k)
+----+----+----+----+----+----+----+----+----+----+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
+----+----+----+----+----+----+----+----+----+----+
| | | | | | 45 | | | | |
+----+----+----+----+----+----+----+----+----+----+
45 % 10 = 5 → stored here
If 25 also inserted: 25 % 10 = 5 → COLLISION!
2. Hash Table Structure
A hash table is an array-based structure where data is stored using indices generated by a hash
function.
2.1 Components
• Key → input value (e.g., student ID)
• Hash Function → converts key into index
• Hash Table → array storing data
• Collision Handling → resolves conflicts
3. Hash Functions
A hash function maps a key to a fixed range of values (table index).
3.1 Characteristics of Good Hash Function
• Fast computation
• Uniform distribution
• Minimum collisions
• Valid index generation
4. Division Method (Most Important Hash Function)
BSCS — Hashing in Data Structures | Lecture Notes
