Hash Map

A hash map stores values by key and supports fast lookup in typical cases. In Python, the built-in dict is the standard hash map.

Hash maps are one of the most common ways to replace repeated scanning with direct lookup.

Core Idea

The algorithm chooses a key that identifies what it needs to find later. The map stores the answer, count, position, group, or object associated with that key.

Typical lookup, insertion, and update are treated as O(1) average time.

The important design choice is the key. A good key captures exactly the lookup question the algorithm will ask later. For example, a frequency counter uses the value itself as the key. A memoization table may use a tuple of state variables as the key.

Function Contract

two_sum_indices(values, target) expects a list of numbers and a target sum.

It returns a pair of indexes (i, j) when values[i] + values[j] == target and i != j. If no such pair exists, it returns None. The dictionary maps a value already seen to the index where it appeared.

Python Example

counts = {}
 
for word in ["red", "blue", "red"]:
    counts[word] = counts.get(word, 0) + 1

After the loop, counts["red"] is 2 and counts["blue"] is 1.

A Common Algorithm Pattern

The two-sum pattern shows why a hash map is useful:

def two_sum_indices(values, target):
    index_by_value = {}
 
    for i, value in enumerate(values):
        needed = target - value
        if needed in index_by_value:
            return index_by_value[needed], i
        index_by_value[value] = i
 
    return None

The brute-force version checks every pair. The hash-map version stores earlier values so each new value can ask one direct question: “Have I already seen the value that completes the target?”

Key Design

Keys can represent simple values or compound states:

memo = {}
state = (row, col, remaining_steps)
memo[state] = answer

The tuple is useful because it combines several pieces of state into one hashable key.

Step-by-Step Trace

For values = [3, 8, 4] and target = 11, the algorithm first stores that 3 appeared at index 0. At value 8, the needed complement is 3, which is already in the map, so it returns (0, 1).

The dictionary avoids scanning all earlier values again.

Common Confusions

The key must be hashable. Strings, numbers, and tuples of hashable values can be keys. Lists cannot be keys because they are mutable.

Hash maps do not keep values sorted. If the algorithm needs sorted order, a plain Python dictionary is not the right structure by itself.

Average O(1) does not mean every dictionary operation is literally one machine step. It means the operation is treated as constant time for normal algorithm analysis.

When To Use It

Use a hash map when the algorithm needs fast lookup by key, counting frequencies, grouping items, storing previously seen positions, or memoizing results.

Do not use a hash map merely because it is powerful. If a simple list scan is enough for a tiny input or one-time lookup, the simpler solution may be clearer.

The Main Point

A hash map is useful when a value should lead directly to associated information. It often replaces repeated scans with direct lookup.