Data Structure and AlgorithmsUnit 1010 min read

Hashing & Collision Resolution: Hash Tables, Probing, and Real-World Hashing

Unit 10 of Data Structure and Algorithms introduces hashing—a technique to map keys to array indices for O(1) average-time lookups—while covering collision types, probing methods (linear, quadratic, double), and collision resolution (chaining vs. open addressing). It includes worked examples, comparisons, and real-worl

Padhai · Based on the official syllabus and past papers
Updated 29 Sept 2026

TAKEAWAYS

Hashing converts keys into array indices using a hash function to achieve constant-time access.
Collisions occur when two keys hash to the same index; probing (linear, quadratic, double) and chaining resolve them.
Open addressing (probing) vs. chaining (linked lists) trade off memory for speed.
Load factor (α = n/m) determines performance: higher α → more collisions.
Double hashing uses two hash functions to reduce clustering in quadratic probing.
Real-world systems (e.g., Khalti’s payment routing, Daraz’s inventory lookup) rely on hashing for efficiency.

1. Introduction to Hashing

Hashing is a mapping technique that converts a key into an index in a fixed-size array (hash table) for fast retrieval. The hash function $h (k)$ maps keys $k$ to indices $0 \leq h (k) < m$ , where $m$ is the table size.

Why Hashing?

O(1) average-time for search/insert/delete (vs. O(n) for linear search).
Efficient storage for dictionaries, databases, and caches.
Used in eSewa’s transaction verification (hashing user IDs to transaction records) and NEPSE’s stock symbol lookup (hashing ticker symbols to stock data).

Key Terms

Hash Table: Array + hash function.
Hash Function: Deterministic mapping (e.g., $h (k) = k mod m$ ).
Bucket/Slot: Array index where a key is stored.
Load Factor (α): $α = \frac{n}{m}$ , where $n$ = entries, $m$ = table size.
- Optimal α: 0.5–0.7 (beyond this, collisions rise sharply).

2. Hash Functions

A good hash function:

Distributes keys uniformly (minimizes collisions).
Computes quickly (e.g., modulo, polynomial rolling hash).

Common Hash Functions

Method	Formula	Example (key = "abc", m = 11)
Division Method	$h (k) = k mod m$	$h (98) = 98 mod 11 = 10$
Multiplication	$h (k) = ⌊ m \cdot (k A mod 1)⌋$	$A = 0.618$ (golden ratio)
Universal Hashing	Randomized function for security	Used in cryptographic hashing

Example: Hash the keys ["apple", "banana", "cherry"] into a table of size 5 using $h (k) = k mod 5$ .

flowchart TD
    A["apple"] -->|"h('apple') = 5 mod 5 = 0"| B["Bucket 0"]
    C["banana"] -->|"h('banana') = 6 mod 5 = 1"| D["Bucket 1"]
    E["cherry"] -->|"h('cherry') = 7 mod 5 = 2"| F["Bucket 2"]

State after insertion:

Bucket 0: apple
Bucket 1: banana
Bucket 2: cherry

3. Collisions and Resolution

When two keys hash to the same index, a collision occurs. Resolution methods:

A. Chaining (Separate Chaining)

Each bucket holds a linked list of colliding keys.
Pros: Simple, handles many collisions.
Cons: Extra memory for pointers.

Example: Insert ["cat", "dog", "bat"] into a table of size 3 with $h (k) = k mod 3$ .

flowchart TD
    A["Bucket 0"] --> B["cat"]
    A --> C["bat"]
    D["Bucket 1"] --> E["dog"]

State:

Bucket 0: cat → bat
Bucket 1: dog

B. Open Addressing (Probing)

No linked lists; find next empty slot via probing.
Probing Methods:
1. Linear Probing: $h_{i} (k) = (h (k) + i) mod m$ .
2. Quadratic Probing: $h_{i} (k) = (h (k) + i^{2}) mod m$ .
3. Double Hashing: $h_{i} (k) = (h_{1} (k) + i \cdot h_{2} (k)) mod m$ .

Example: Insert ["apple", "banana", "cherry"] into a size-5 table with linear probing.

Insert "apple" → Bucket 0.
Insert "banana" → Bucket 1.
Insert "cherry" → Bucket 2.
Insert "date" → $h (" d a t e ") = 4 mod 5 = 4$ .
Insert "elderberry" → $h (" e l d er b er r y ") = 2 mod 5 = 2$ (collision with "cherry").
- Probe: $(2 + 1) mod 5 = 3$ → Bucket 3.

State:

Bucket 0: apple
Bucket 1: banana
Bucket 2: cherry
Bucket 3: elderberry
Bucket 4: date

4. Quadratic Probing

Reduces clustering (unlike linear probing). Formula: $h_{i} (k) = (h (k) + i^{2}) mod m$

Example: Insert ["grape", "kiwi", "lemon"] into a size-5 table with $h (k) = k mod 5$ .

"grape" → Bucket 0.
"kiwi" → Bucket 1.
"lemon" → $h (" l e m o n ") = 3 mod 5 = 3$ .
Insert "mango" → $h (" man g o ") = 4 mod 5 = 4$ .
Insert "apple" → $h (" a ppl e ") = 0 mod 5 = 0$ (collision).
- Probe: $(0 + 1^{2}) mod 5 = 1$ (occupied), $(0 + 2^{2}) mod 5 = 4$ (occupied), $(0 + 3^{2}) mod 5 = 4$ → primary clustering (stuck in a loop).

Fix: Use double hashing to avoid clustering.

5. Double Hashing

Combines two hash functions to reduce clustering: $h_{i} (k) = (h_{1} (k) + i \cdot h_{2} (k)) mod m$ where $h_{2} (k)$ is coprime with $m$ .

Example: $h_{1} (k) = k mod 5$ , $h_{2} (k) = 7 - (k mod 7)$ . Insert ["pear", "orange"] into a size-5 table.

"pear" → $h_{1} (" p e a r ") = 0$ , $h_{2} (" p e a r ") = 3$ .
- Bucket 0.
"orange" → $h_{1} (" or an g e ") = 1$ , $h_{2} (" or an g e ") = 4$ .
- Bucket 1.
Insert "plum" → $h_{1} (" pl u m ") = 2$ , $h_{2} (" pl u m ") = 5$ .
- Bucket 2.
Insert "quince" → $h_{1} (" q u in ce ") = 3$ , $h_{2} (" q u in ce ") = 2$ .
- Bucket 3.
Insert "apple" → $h_{1} (" a ppl e ") = 0$ (collision).
- Probe: $(0 + 1 \cdot 3) mod 5 = 3$ (occupied), $(0 + 2 \cdot 3) mod 5 = 1$ (occupied), $(0 + 3 \cdot 3) mod 5 = 4$ → Bucket 4.

State:

Bucket 0: pear
Bucket 1: orange
Bucket 2: plum
Bucket 3: quince
Bucket 4: apple

6. Comparison Table: Collision Resolution Methods

Method	Pros	Cons	Best For
Chaining	Simple, handles many collisions	Extra memory for pointers	High collision probability
Linear Probing	No extra memory	Clustering, poor performance	Low collision probability
Quadratic Probing	Avoids clustering	Still may cluster	Medium collision probability
Double Hashing	No clustering	Complex, slower	High collision probability

7. Real-World Applications

In the Real World

eSewa’s Transaction Lookup
- Idea: Hashing maps user IDs to transaction records for O(1) access.
- How: When a user requests a transaction history, eSewa uses a hash table to retrieve records instantly.
- Example: If a user’s ID is 12345, the hash function computes an index to fetch their transactions without scanning all records.
NEPSE’s Stock Symbol Indexing
- Idea: Hashing maps stock symbols (e.g., "NCL", "NTC") to stock data.
- How: Traders query symbols like h("NCL") to get real-time prices in milliseconds.
- Example: A trader checks h("NCL") to find Nestle Nepal’s current share price.
Khalti’s Payment Routing
- Idea: Hashing routes payment requests to merchant accounts.
- How: The payment ID (e.g., PAY_12345) is hashed to locate the merchant’s record.
- Example: When a user pays via Khalti, the system uses hashing to verify the merchant’s details in microseconds.

8. Worked Example: Bank Loan Interest Calculation

Scenario: A bank uses hashing to store loan records (key = loan ID, value = interest rate).

Hash Table Size: 1000.
Hash Function: $h (k) = k mod 1000$ .
Loans: ["LOAN_101", "LOAN_202", "LOAN_303"] with rates 5%, 6%, 7%.

Insertion:

$h (" L O A N_{1} 01") = 101 mod 1000 = 101$ .
$h (" L O A N_{2} 02") = 202 mod 1000 = 202$ .
$h (" L O A N_{3} 03") = 303 mod 1000 = 303$ .

State:

Bucket 101: LOAN_101 (5%)
Bucket 202: LOAN_202 (6%)
Bucket 303: LOAN_303 (7%)

Query: Find interest for LOAN_202.

Compute $h (" L O A N_{2} 02") = 202$ .
Retrieve rate: 6%.

Collision Handling: If two loans hash to the same bucket (e.g., LOAN_1001 and LOAN_2001 both → 1), use chaining or linear probing.

9. Time Complexity

Operation	Average Case	Worst Case (Chaining)	Worst Case (Open Addressing)
Search/Insert	O(1)	O(n)	O(n)
Delete	O(1)	O(n)	O(n)

Note: Worst case occurs when all keys collide (e.g., $α \approx 1$ ).

10. Exam Tip

Focus on:
1. Definitions: Hash function, collision, load factor.
2. Probing Methods: Draw linear/quadratic/double hashing steps.
3. Chaining vs. Open Addressing: Compare trade-offs.
4. Real-World Tie-Ins: Link to eSewa/Khalti/NEPSE examples.
5. Worked Examples: Always show state after each insertion/query.
Common Pitfalls:
- Forgetting to handle collisions in open addressing.
- Misapplying quadratic probing (e.g., using $i$ instead of $i^{2}$ ).
- Assuming O(1) always holds (worst case is O(n)).
Formula to Memorize:
- Load factor: $α = \frac{n}{m}$ .
- Quadratic probing: $h_{i} (k) = (h (k) + i^{2}) mod m$ .

11. Code Example: Hash Table with Chaining (Python)

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

    def hash(self, key):
        return key % self.size

    def insert(self, key, value):
        index = self.hash(key)
        bucket = self.table[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # Update
                return
        bucket.append((key, value))  # Insert new

    def search(self, key):
        index = self.hash(key)
        bucket = self.table[index]
        for k, v in bucket:
            if k == key:
                return v
        return None

# Trace: Insert ("apple", 10), ("banana", 20), ("apple", 30)
ht = HashTable(3)
ht.insert("apple", 10)  # Bucket 1: [("apple", 10)]
ht.insert("banana", 20) # Bucket 2: [("banana", 20)]
ht.insert("apple", 30)  # Updates to [("apple", 30)]
print(ht.search("apple"))  # Output: 30

Output Table:

Step	Operation	Bucket State
1	Insert("apple",10)	Bucket 1: [("apple",10)]
2	Insert("banana",20)	Bucket 2: [("banana",20)]
3	Insert("apple",30)	Bucket 1: [("apple",30)]

12. Summary Diagram: Hashing Workflow

flowchart TD
    A["Key"] --> B["Hash Function"]
    B --> C["Index = h(key) mod m"]
    C --> D["Check Bucket"]
    D -->|"Empty"| E["Store Key-Value"]
    D -->|"Collision"| F["Resolve (Chaining/Probing)"]
    F --> G["Store Key-Value"]
    G --> H["Return Value"]

Based on the TU BIT syllabus for Data Structure and Algorithms (BIT201), unit 10.

Discussion

Loading…