Hashing: Concept & Explanation
Hashing is a technique used in computer science to store and retrieve data efficiently. It involves mapping data (keys) to a fixed-size value (hash code) using a hash function. This hash code determines where the data will be stored in a data structure called a hash table.
Key Concepts of Hashing
1️⃣ Hash Function
- A mathematical function that takes an input (key) and returns a fixed-size value (hash code).
- Example:
h(key) = key % table_size(for numeric keys).
2️⃣ Hash Table
- A data structure that stores key-value pairs.
- Uses an array where the index is determined by the hash function.
3️⃣ Collisions & Handling Techniques
- When two keys generate the same hash code, it’s called a collision.
- Common ways to handle collisions:
- Chaining: Store multiple values at the same index using linked lists.
- Open Addressing: Find an empty slot using techniques like linear probing or quadratic probing.
4️⃣ Load Factor
- Determines the efficiency of a hash table.
- Formula:
Load Factor = (Number of elements) / (Table size). - A higher load factor increases collisions, so resizing may be required.
Example of Hashing
Let’s say we have a list of student IDs: {101, 203, 309, 412, 512}
Using a hash function h(key) = key % 10, we map them to a hash table:
The table size is usually defined at the start when a hash table is initialized. However, whether it remains fixed or can grow depends on the type of hash table being used.
The table size is typically chosen based on the number of expected elements and efficiency considerations.
If table size = 10, it means the hash table has 10 slots (buckets) for storing values
table size = 10
| Key | Hash Code (key % 10) | Stored At Index |
|---|---|---|
| 101 | 101 % 10 = 1 | 1 |
| 203 | 203 % 10 = 3 | 3 |
| 309 | 309 % 10 = 9 | 9 |
| 412 | 412 % 10 = 2 | 2 |
| 512 | 512 % 10 = 2 | 2 (Collision occurs!) |
So, if table size = 10, the hash function ensures values are stored within the range 0-9
The operation 101 % 10 is a modulus operation, which finds the remainder when 101 is divided by 10.
Step-by-Step Calculation:
- 101 ÷ 10 = 10 (Quotient)
- 10 × 10 = 100
- 101 – 100 = 1 (Remainder)
That’s why 101 % 10 = 1.
To handle the collision at index 2, we use chaining or open addressing.
🔹 Load Factor Calculation
The formula for Load Factor (LF) is:
From your table:
- Total Table Size =
10(since the hash function uses% 10) - Number of Stored Elements =
5(101,203,309,412,512)
🔹 Interpretation:
- A 50% load factor means the table is half full.
- If the load factor exceeds 0.7, rehashing (resizing the table) is recommended to reduce collisions.
Applications of Hashing
✅ Database Indexing – Fast lookup of records.
✅ Password Storage – Hashing algorithms (e.g., SHA-256) secure passwords.
✅ Caching – Fast data retrieval in web applications.
✅ Cryptography – Ensures data integrity and security.
✅ Symbol Tables in Compilers – Stores variable/function names efficiently.
What is a Key-Value Pair?
A key-value pair is a fundamental concept in data structures where each key is associated with a specific value. It allows quick access to values based on their unique keys.
Explanation:
- The key is a unique identifier (like a name or an ID).
- The value is the associated data (like a phone number or an address).
Example:
Imagine a dictionary where:
- The word (key) is unique.
- The definition (value) is associated with that word.
Real-World Example:
| Key (Name) | Value (Phone Number) |
|---|---|
| Alice | 123-456-7890 |
| Bob | 987-654-3210 |
| Charlie | 555-666-7777 |
Here:
- “Alice” is the key and “123-456-7890” is the value.
- You can quickly retrieve Alice’s phone number using her name.