Hashing (Hash Map) in Python

Hashing is a technique used to store and retrieve data efficiently using key-value pairs. Python’s dict is a built-in hash map that provides very fast average operations.

A hash map is one of the most important tools in DSA because it reduces search time from O(n) to O(1) average.

---

Introduction to Hashing and Hash Functions

What is a Hash Function?

A hash function takes an input (key) and returns an integer index (hash code).

Example idea:

key -> hash(key) -> index in table -> store value

What makes a good hash function?

• Fast to compute
• Distributes keys evenly
• Minimizes collisions

What is a Collision?

A collision happens when two different keys produce the same index.

Example:

• hash(“abc”) % 10 = 3
• hash(“xyz”) % 10 = 3 → collision

---

Implementing Hash Tables/Dictionaries in Python

Python dictionary:

• Uses hashing internally
• Average lookup/insert/delete is O(1)

Example:

student = {
    "name": "Amit",
    "age": 21,
    "course": "DSA"
}

print(student["name"])  # Amit

Insertion / Update

student["grade"] = "A"
student["age"] = 22

Deletion

del student["course"]

Safe Lookup

print(student.get("course", "Not found"))

---

Handling Collisions

Internally, hash tables handle collisions using strategies like:

Chaining

Each index stores a list of key-value pairs.

Conceptual example:

index 3 -> [(k1,v1), (k2,v2)]

Open Addressing

If the slot is occupied, search another slot (linear probing/quadratic probing).

Python’s dict uses a probing-based approach (implementation detail).

---

Applications of Hashing

• Fast lookup (username → user object)
• Counting frequencies (most common in interviews)
• Caching (store results of expensive operations)
• Duplicate detection (using sets/dicts)
• Two-sum style problems

Example: Frequency Count

from collections import Counter

nums = [1, 2, 1, 3, 2, 1]
freq = Counter(nums)

print(freq)  # Counter({1: 3, 2: 2, 3: 1})

Example: First non-repeating character

from collections import Counter

s = "aabbcddee"
count = Counter(s)

for ch in s:
    if count[ch] == 1:
        print(ch)  # c
        break

---

Summary

Hashing enables fast search using key-value mapping. Python dictionaries are highly optimized hash tables. Hash maps are essential for frequency problems, caching, and lookup-based algorithms.