HashMap

A hash map (also called a hash table or dictionary) is one of the most useful data structures for interview problem solving because it lets you store information as you scan and then look it up instantly later. This is the classic “space for time” trade: you use more memory so you can avoid repeated searching.

In practice, hash maps are the reason many problems go from “I guess I need nested loops” to “I can do this in one pass.” If you feel yourself repeatedly scanning earlier elements, repeatedly counting, or repeatedly checking membership, a hash map is often the clean fix. That’s why hash maps show up constantly in interviews for counting, searching, and general key → value storage.

What is a HashMap?

A hash map stores key → value pairs. The key is how you identify the data, and the value is the data you want to retrieve quickly. Keys are typically things like strings, numbers, or tuples, anything that can be hashed consistently.

This is different from an array/list. Arrays are accessed by numeric index (arr[0]), while hash maps are accessed by key (map["alice"]). That key-based access is what makes them ideal when you don’t naturally have an index.

Key characteristics of a HashMap

Here are the main characteristics of a hashmap:

• Stores key–value pairs (key maps to a value)
• Very fast average lookup/insert/delete: usually O(1) average
• Uses a hash function to convert a key into an array index (bucket)
• Handles collisions when two keys map to the same bucket
• Resizes (rehashes) when it gets too full to keep performance fast

Why not just use a list?

A list makes you search by scanning. If you want to find "Alice" in a list of a million entries, you might check a huge portion of the list before you find her, which is O(n) time per lookup.

A hash map is designed so that lookups are O(1) average time. You don’t scan through everything; you jump straight to the bucket where the key should live. This difference matters whenever the problem requires many lookups, repeated checks, or counting. If you’re counting frequencies, checking “have I seen this?”, or searching for complements/previous occurrences, a hashmap is usually the first tool to reach for.

How hashing works

Internally, a hash map is built on top of an array of buckets. The key idea is that the map uses a hash function to convert a key (like "Apple") into a large integer. That integer is then converted into a valid array index (commonly via modulo) so the map knows which bucket to use.

Here’s the mental model you should keep in your head:

• Key in: "Apple"
• Hash function: produces a big number (e.g., 5821)
• Bucket index: 5821 % capacity
• Store / retrieve: place or find the key-value pair in that bucket

When you insert a key, the map hashes it, chooses a bucket index, and stores the key-value pair there. When you look up the key later, it repeats the same hashing steps and goes back to the same bucket location.

Collisions

A collision happens when two different keys hash into the same bucket index. Collisions are normal, and good hash map implementations are built to handle them safely.

The most common strategy is chaining, where each bucket holds a small collection (often a linked list or dynamic list) of entries. If two keys land in the same bucket, they both go into that bucket’s list, and lookups check that small list.

Another strategy is open addressing, where each bucket holds at most one entry. If the bucket is taken, the map probes forward to find another available slot. The details vary, but the goal is the same: store everything without losing correctness.

Load factor and resizing

Hash maps stay fast because they avoid getting too full. They track something like a load factor, which is roughly entries / buckets. When the load factor becomes high, collisions become more frequent and buckets become more crowded.

To prevent slowdown, the map will resize (increase its bucket array capacity) and rehash existing entries into the new structure. Resizing costs time at that moment, but it protects the long-run average performance.

HashMap operations

Most interview solutions rely on a small set of hash map actions: insert/update, lookup, delete, and contains. Conceptually, you can treat updates as “insert with the same key again,” because the new value overwrites the old one.

Common operations look like this (language varies, idea doesn’t):

Insert / Update

Insert a new key–value pair or update the value if the key already exists.

hash_map = {}

hash_map["a"] = 1

hash_map["b"] = 2

hash_map["a"] = 3  # Update existing key

Lookup

Retrieve the value associated with a key.

value = hash_map.get("a")  # 3

Using get instead of direct indexing avoids runtime errors when a key is missing.

Delete

Remove a key–value pair from the hash map.

del hash_map["b"]

Existence Check

Check whether a key exists in the hash map.

exists = "a" in hash_map  # True

1 / 6

Complexity analysis

HashMaps are designed for high-speed performance. Under normal conditions, they operate in Constant Time.

What is a set?

A set is like a hash map that stores only keys (no values), so it’s best when you only care about membership—questions like “have I seen this before?” or “is this element unique?” Because sets support O(1) average add and lookup, they often replace slow list-scanning when you need fast membership checks. You typically use a set to detect duplicates quickly, track visited elements or states (common in graphs), or maintain a “seen so far” collection as you iterate.

One important constraint is that set elements must be hashable/immutable (such as strings, integers, or tuples), and you generally shouldn’t rely on iteration order. Space usage is usually O(n) since you’re storing up to n unique elements.

Quick rule:

• Use a set when you only need membership (“seen?”).
• Use a hash map when you need membership + extra data (count/index/group/etc.).

HashMap vs Hash Table vs Dictionary

In interviews, these terms often get used loosely:

• “Hash table” usually refers to the underlying concept/implementation (buckets + hashing).
• “HashMap”/“dictionary” usually refers to the language’s key→value API built on a hash table.
• So most of the time: HashMap ≈ Hashtable ≈ Dictionary (conceptually), unless a language/library makes a specific distinction.

Practical interview guidance:

• If you need key → value storage (counts, indices, groups), pick a hashmap/dict.
• If you only need uniqueness/membership, pick a set.
• If the problem requires sorted keys or ordered iteration by key, a hash-based structure is the wrong tool; use an ordered map/tree structure instead (language dependent).

The most common HashMap patterns

A hash map is your go-to tool whenever you need fast lookups to count occurrences, find matching complements, group by a key/signature, or use prefix sums to solve subarray problems in one pass.

Frequency Counting

If a problem asks “how many times does each item appear,” use a hash map where the key is the item and the value is the count. This turns repeated counting into a single pass. As you scan the list, if the word is already in the map, you increment its value; otherwise, you insert it with a count of 1.

words = ["cat", "dog", "cat", "cat", "bird"]
freq = {}
for w in words:
    freq[w] = freq.get(w, 0) + 1
# {"cat": 3, "dog": 1, "bird": 1}

Complement lookup (Two Sum style)

If you need to find a pair that matches a condition (like sums to target), store past values in a map so you can instantly check whether the needed complement already exists.

def two_sum(nums, target):
    seen = {}  # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i

Grouping

If you need to group related items (like anagrams), compute a “signature” key and map it to a list of items in that group.

from collections import defaultdict

def group_anagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = "".join(sorted(s))
        groups[key].append(s)
    return list(groups.values())

Prefix Sum + Hash Map

For subarray sum problems, store prefix sums in a map so you can quickly count how many times you’ve seen the needed previous sum. This is a classic “hash map turns O(n²) into O(n)” move.

Common pitfalls

Hash maps are simple, but the same mistakes show up again and again in interviews:

• Missing keys: accessing a key that isn’t there can crash your code—use safe access like get() or check existence first.
• Mutable keys: don’t use lists/arrays/objects that can change as keys; changing them can make the entry “disappear.”
• Assuming order: most hash maps don’t guarantee iteration order unless the language/type explicitly promises it.

Language cheat sheet

HashMaps are so fundamental that every major language has them, though the names vary:

• Python: dict
• Java: HashMap
• JavaScript: Map (or {} objects)
• C++: std::unordered_map
• C# / Swift: Dictionary