0% completed
1️⃣ Understanding Hashing in Hashtables
A Hashtable stores key-value pairs using a hash function that converts a key into a numeric index in an array. This enables quick lookups, insertions, and deletions.
🔹 How Hashing Works:
- A key (e.g.,
Book ID: 1008) is passed through a hash function. - The hash function computes an index based on the key (e.g.,
1008 % 10 → 8). - The value (e.g.,
"A1 Shelf") is stored at that index in the Hashtable. - When retrieving a value, the Hashtable recomputes the index and directly accesses the stored value.
Advantages of Hashing
- Allows constant-time lookups (
O(1)) when there are no collisions. - Efficient for large datasets where fast access is needed.
🚨 Issue: What If Two Keys Map to the Same Index?
This is called a collision, which we’ll discuss next.
2️⃣ Collision in Hashtables
A collision happens when two different keys produce the same index after hashing. Since a Hashtable uses an array-based structure, only one value can be stored at an index—so the system must handle this situation.
Collision Example: Library Book Storage
Imagine a library where books are stored on numbered shelves, determined by their ISBN (Book ID) % 10. The Book ID acts as the key, while the Shelf Location represents the value in a Hashtable.
-
The library assigns each book a shelf number using a hash function:
-
If two books hash to the same shelf, a collision occurs.
-
The library must efficiently organize multiple books on the same shelf to avoid data loss.
We insert the following books:
| Key (Book ID) | Title | Shelf |
|---|---|---|
| 1008 | Introduction to Algorithms | A1 |
| 1009 | Data Structures: A Pseudocode Approach | B2 |
| 1010 | System Design Interview Roadmap | C3 |
| 1011 | Grokking the Coding Interview | D4 |
| 1021 | Grokking the Art of Recursion for Coding Interviews | E5 |
Hash Function Calculation
Each book's shelf index is determined by:
\text{Hash Index} = \text{Book ID} \mod 10
| Key (Book ID) | Hash Function Output (Index) |
|---|---|
| 1008 | 1008 % 10 = 8 |
| 1009 | 1009 % 10 = 9 |
| 1010 | 1010 % 10 = 0 |
| 1011 | 1011 % 10 = 1 |
Collision Scenario:
Now, inserting Key 1021:
Since Book 1011 is already placed at Shelf 1, we encounter a collision.
Without a collision-handling mechanism, Book 1021 would overwrite Book 1011, losing data!
How Time Complexity Increases to O(n) Due to Collisions
- If multiple elements exist at the same index (due to collisions), a linear search (O(n)) is needed to find the correct key.
- If all books in the library hash to Shelf 1, searching for a book requires scanning the entire shelf, making it O(n) instead of O(1).
🚨 Worst-Case Scenario:
If too many keys collide, the Hashtable behaves like a linked list, leading to O(n) worst-case performance**.
3️⃣ Overflow and Resizing
Even with collision resolution, Hashtables eventually run out of space when too many elements are inserted.
To handle this, Hashtables dynamically resize based on the load factor.
What is Load Factor?
The load factor determines when a Hashtable should grow.
\text{Load Factor} = \frac{\text{Number of Stored Elements}}{\text{Hashtable Size}}
- A load factor of 0.7 (70%) is a common threshold for resizing.
- When the load factor exceeds the threshold, the Hashtable doubles its size to reduce collisions.
🔹 How Resizing Works?
- Create a new, larger Hashtable (typically 2× the original size).
- Recompute hash values for all existing keys and reinsert them into the new table.
- Insert the new key at its correct position.
In the next lesson, we will learn how to use hashtable in different programming langauges.
Table of Contents
1️⃣ Understanding Hashing in Hashtables
Advantages of Hashing
2️⃣ Collision in Hashtables
Collision Example: Library Book Storage
How Time Complexity Increases to O(n) Due to Collisions
3️⃣ Overflow and Resizing
What is Load Factor?
🔹 How Resizing Works?