Hash maps (also called hash tables or dictionaries) are one of the most powerful and frequently used data structures in programming. They provide near-instant access to data through key-value pairs.

Goal: Understand how hash maps work, when to use them, and master common patterns for coding interviews.

Key Insight: Hash maps trade space for time - using O(n) extra space to achieve O(1) average-case lookup, insertion, and deletion. This makes them perfect for problems requiring frequent lookups.

What is a HashMap?

A hash map is a data structure that maps keys to values using a hash function.

Simple Analogy: Think of a library catalog. Instead of searching through every book (O(n)), you look up the book's location using its catalog number (O(1)).

Key-Value Pairs

Key         →    Value
"Alice"     →    25
"Bob"       →    30
"Charlie"   →    35

Operations:

›Insert: Add a key-value pair
›Search: Find value by key
›Delete: Remove a key-value pair

Basic Usage

Python

# Creating a hash map
person_ages = {}

# Inserting key-value pairs
person_ages["Alice"] = 25
person_ages["Bob"] = 30
person_ages["Charlie"] = 35

# Accessing values
print(person_ages["Alice"])  # Output: 25

# Checking if key exists
if "Bob" in person_ages:
    print("Bob's age:", person_ages["Bob"])

# Deleting a key
del person_ages["Charlie"]

# Iterating
for name, age in person_ages.items():
    print(f"{name} is {age} years old")

How Hash Maps Work

The Hash Function

A hash function converts a key into an array index.

Key "Alice" → hash("Alice") → 3
Key "Bob"   → hash("Bob")   → 7
Key "Eve"   → hash("Eve")   → 3  ← Collision!

Properties of Good Hash Functions:

›Deterministic: Same key always produces same hash
›Fast: O(1) computation time
›Uniform: Distributes keys evenly across buckets

Internal Structure

Hash Table (array of buckets)
Index:    0    1    2    3    4    5
         [ ]  [ ]  [ ]  [A]  [ ]  [B]
                        ↓         ↓
                     Alice=25  Bob=30

Basic Operations Flow

Insert "Alice" → 25:

›Compute hash: hash("Alice") = 3
›Go to bucket 3
›Store key-value pair

Search "Alice":

›Compute hash: hash("Alice") = 3
›Go to bucket 3
›Return value: 25

Collision Handling

When two keys hash to the same index, we have a collision.

Method 1: Chaining (Linked Lists)

Each bucket stores a linked list of key-value pairs.

Index:  3
        ↓
     [Alice=25] → [Eve=22] → null

Python

# Python handles collisions automatically
# But here's a simple implementation concept

class HashMapChaining:
    def __init__(self, size=10):
        self.size = size
        self.buckets = [[] for _ in range(size)]
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def put(self, key, value):
        index = self._hash(key)
        # Update if key exists, else append
        for i, (k, v) in enumerate(self.buckets[index]):
            if k == key:
                self.buckets[index][i] = (key, value)
                return
        self.buckets[index].append((key, value))
    
    def get(self, key):
        index = self._hash(key)
        for k, v in self.buckets[index]:
            if k == key:
                return v
        return None

# Usage
hmap = HashMapChaining()
hmap.put("Alice", 25)
hmap.put("Bob", 30)
print(hmap.get("Alice"))  # Output: 25

Method 2: Open Addressing (Linear Probing)

When collision occurs, find the next empty slot.

Index:  0    1    2    3    4
       [A]  [ ]  [ ]  [B]  [C]
                       ↑    ↑
                     Bob  Eve (collided at 3, moved to 4)

Python

class HashMapOpenAddressing:
    def __init__(self, size=10):
        self.size = size
        self.keys = [None] * size
        self.values = [None] * size
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def put(self, key, value):
        index = self._hash(key)
        
        # Linear probing to find empty slot
        while self.keys[index] is not None:
            if self.keys[index] == key:
                # Update existing key
                self.values[index] = value
                return
            index = (index + 1) % self.size
        
        # Insert at empty slot
        self.keys[index] = key
        self.values[index] = value
    
    def get(self, key):
        index = self._hash(key)
        
        # Linear probing to find key
        while self.keys[index] is not None:
            if self.keys[index] == key:
                return self.values[index]
            index = (index + 1) % self.size
        
        return None  # Not found

# Usage
hmap = HashMapOpenAddressing()
hmap.put("Alice", 25)
hmap.put("Bob", 30)
print(hmap.get("Alice"))  # Output: 25

Time Complexity

Operation	Average Case	Worst Case
Insert	O(1)	O(n)
Search	O(1)	O(n)
Delete	O(1)	O(n)

Why Worst Case O(n)?

›All keys hash to same bucket (poor hash function)
›Requires traversing entire chain or probing entire table

In Practice:

›Good hash function → Average case O(1)
›Load factor < 0.75 → Performance stays good

Common HashMap Patterns

Pattern 1: Frequency Counter

Count occurrences of each element.

Python

def count_frequencies(arr):
    """Count frequency of each element"""
    freq = {}
    
    for num in arr:
        freq[num] = freq.get(num, 0) + 1
    
    return freq

# Example
arr = [1, 2, 2, 3, 3, 3]
print(count_frequencies(arr))
# Output: {1: 1, 2: 2, 3: 3}

Pattern 2: Two Sum Problem

Find two numbers that add up to target.

Python

def two_sum(nums, target):
    """Find indices of two numbers that sum to target"""
    seen = {}  # value → index
    
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    
    return []

# Example
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))  # Output: [0, 1]

Pattern 3: Group Anagrams

Group strings that are anagrams of each other.

Python

def group_anagrams(strs):
    """Group anagrams together"""
    anagram_map = {}
    
    for s in strs:
        # Sort string to use as key
        key = ''.join(sorted(s))
        if key not in anagram_map:
            anagram_map[key] = []
        anagram_map[key].append(s)
    
    return list(anagram_map.values())

# Example
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(strs))
# Output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Pattern 4: Longest Substring Without Repeating Characters

Find length of longest substring without duplicates.

Python

def longest_unique_substring(s):
    """Find longest substring without repeating characters"""
    char_index = {}  # character → last seen index
    max_length = 0
    start = 0
    
    for end in range(len(s)):
        char = s[end]
        
        # If character seen and in current window
        if char in char_index and char_index[char] >= start:
            start = char_index[char] + 1
        
        char_index[char] = end
        max_length = max(max_length, end - start + 1)
    
    return max_length

# Example
s = "abcabcbb"
print(longest_unique_substring(s))  # Output: 3 ("abc")

HashMap vs Array

Feature	HashMap	Array
Access by index	O(n)	O(1)
Access by key	O(1)	O(n)
Space	O(n) extra	O(1) extra
Ordered	No	Yes
Use when	Need fast lookup by key	Need ordered data

When to Use HashMap

✅ Use HashMap When:

›Need fast lookups - Finding elements in O(1)
›Counting frequencies - Track occurrences
›Caching/memoization - Store computed results
›Finding pairs - Two sum, complement problems
›Grouping items - Group anagrams, etc.

❌ Don't Use HashMap When:

›Need ordering - Use sorted containers instead
›Memory constrained - HashMap uses extra space
›Keys are integers in small range - Use array instead
›Need to iterate frequently - Arrays are faster

Key Takeaways

HashMap Essentials:

Definition: Data structure mapping keys to values using hash function

Core Operations:

›Insert: map[key] = value - O(1) average
›Search: value = map[key] - O(1) average
›Delete: del map[key] - O(1) average

How It Works:

›Hash function converts key to index
›Store key-value pair at that index
›Handle collisions with chaining or open addressing

Collision Handling:

›Chaining: Each bucket stores a linked list
›Open Addressing: Find next empty slot

Time Complexity:

›Average: O(1) for all operations
›Worst: O(n) with poor hash function

Common Patterns:

›Frequency counter
›Two sum / finding pairs
›Group by key (anagrams)
›Sliding window with uniqueness

When to Use:

›Fast lookups by key needed
›Counting/grouping elements
›Caching results
›Finding complements/pairs

Remember:

›HashMap trades space for time
›Good hash function is crucial
›Average O(1) only with good hash function
›Load factor affects performance

Interview Tip: Hash maps solve most "find in O(1)" problems!

What's Next?

Now that you understand hash maps:

›HashSet - Set implementation using hash map
›Advanced Hashing - Rolling hash, custom hash functions
›Practice Problems - Master through practice

Practice Problems

Problem 1: Valid Anagram

Check if two strings are anagrams using a hash map.

Problem 2: First Unique Character

Find first non-repeating character in a string.

Problem 3: Subarray Sum Equals K

Find number of subarrays with sum equal to K.

Problem 4: Longest Consecutive Sequence

Find longest sequence of consecutive numbers in unsorted array.

Congratulations! You now understand hash maps and can use them to solve problems efficiently!

←

PreviousPractice Problems

NextFrequency Count

→