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.
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
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"))
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).
- 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
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.