Introduction

Hashmaps are data structures that store key–value pairs and allow extremely fast lookup of values by key. In Python, the built-in dictionary type is a hashmap under the hood, using a hash table to map each key to where its value is stored in memory. This means retrieving or updating a value by key can typically be done in constant time – O(1) on average.

When to use Hashmaps in interviews:

Hashmaps are among the most commonly used data structures in coding interview problems. They shine when you need to quickly check for existence, count occurrences, or map one set of values to another. If a problem involves terms like “find duplicates”, “count frequencies”, “lookups”, “mapping” or requires optimizing nested loops, it’s often a cue that a hashmap (dictionary) could be useful. Classic examples include Two Sum, word count/frequency, or anagram detection.

Core Idea / Mental Model

The power of a hashmap comes from using a key’s hash to index into an array where the value is stored. Think of it like a huge cabinet of numbered drawers: each key is run through a hashing function that tells you which drawer to use for that key’s value. This allows direct access instead of searching item by item.

A Python dictionary uses a hash function to convert keys into array indices. Collisions (two keys hashing to the same index) are handled internally. Well-designed hashmaps make lookups independent of dataset size on average.

Why use a hashmap? Lookup, insertion, and deletion are O(1) average time, much faster than O(n) for unsorted lists. They trade space for speed, making them a go-to for optimization.

Base Template (Python Dictionary Usage - Frequency Count)

A common use-case is counting occurrences. Here's an example:

items = ["apple", "banana", "apple", "orange"]
counts = {} # Initialize an empty dictionary (hashmap)

for item in items:
    if item in counts:
        counts[item] += 1         # Key exists: increment count
    else:
        counts[item] = 1          # Key not in dict: add with count 1
    # Dry-run status:
    # e.g., after first "apple": {"apple": 1}
    #       after "banana": {"apple": 1, "banana": 1}
    #       after second "apple": {"apple": 2, "banana": 1}
    #       after "orange": {"apple": 2, "banana": 1, "orange": 1}
print(counts)  # Output: {'apple': 2, 'banana': 1, 'orange': 1}

Explanation: Iterate through items. If item is in counts, increment its count. Otherwise, add it with count 1. This pattern is a staple for problems like anagram detection or character frequency counting.

Interactive Animation (Frequency Counting)

The animation below demonstrates building a frequency map (dictionary) from a list of items: ["apple", "banana", "apple", "orange"]. Watch how the dictionary is updated as each item is processed.

Time & Space Complexity

Time Complexity: Average O(1) for insertions, lookups, and deletions. Worst case (rare, due to collisions) can be O(n). For interviews, assume average O(1).

Space Complexity: O(n) to store n key-value pairs.

Common Pitfalls

• Using mutable types as keys: Keys must be immutable (strings, numbers, tuples). Lists or dicts cannot be keys.
• Accessing missing keys (KeyError): Use if key in my_dict: or my_dict.get(key, default_value) to avoid errors.
• Forgetting to check if a key exists: Leads to KeyError.
• Assuming a specific order of keys: Standard hashmaps are unordered (Python 3.7+ dicts preserve insertion order, but don't rely on it for algorithmic correctness unless specified).
• Modifying the dictionary during iteration: Can cause runtime errors. Iterate over a copy (e.g., list(my_dict.keys())) or collect changes.