Hash Table Pattern: Complete Guide with Examples

Almost every interview question that asks for fast lookups comes back to the hash table. Two Sum, Group Anagrams, LRU Cache, they all use the same trick: spend a little extra memory to get constant-time access. This page explains the pattern behind those problems, when to reach for it, and the mistakes that cost offers in real interviews.

Definition: a hash table maps keys to values. A hash function turns each key into an array index, so each value sits at a known position and a lookup jumps straight to it instead of scanning the collection. A set is the same structure with the values left out. Use a set when you only need to know whether something exists. Use a map when you need to attach data to each key.

Real-World Analogy

Think of a coat check at a busy restaurant. You hand over your coat and get a ticket with a number on it. When you want the coat back, you give the ticket to the attendant and they walk to that exact numbered spot on the rack. Nobody searches through all the coats. The ticket number is the hash, the rack is the array, and the coat is the value. Retrieving a coat takes the same amount of time no matter how many coats are hanging there.

Visual Explanation

Here is the core idea in diagram form. The same key always produces the same index, so the way in is the way out.

    graph TD
    A["Key: alice"] --> B["hash(alice) = 3"]
    C["Key: bob"] --> D["hash(bob) = 7"]
    B --> E["Slot 3 stores alice's value"]
    D --> F["Slot 7 stores bob's value"]
    G["Query: alice"] --> H["hash(alice) = 3"]
    H --> E
  

Two things matter here. First, the hash function always returns the same index for the same key, so a lookup repeats the same computation and lands on the same slot. Second, two different keys can collide onto the same slot. Implementations handle collisions with chaining, where each slot holds a small list, or with open addressing, which probes for the next free slot. Collisions are why the worst case is slower than the average case, as the complexity table below shows.

One more thing worth stating plainly: you will almost never implement a hash table in an interview. Every mainstream language ships one as a built-in. The interview skill is recognizing when the structure is the answer, not building it.

When to Use This Pattern

These characteristics point to a hash table solution.

• Membership tests. Ask “have I seen this value before?” and let a set answer in
  O(1)
  average time. A linear scan over an array costs
  O(N)
  per check, which turns a loop into
  O(N^2)
  .
• Frequency counts. Count how many times each element appears, then compare or consume those counts. Ransom Note and the anagram problems all work this way.
• Complement search. Pair problems like Two Sum store what you have seen and check what you still need, all in one pass.
• Grouping by a shared property. Anagrams share a sorted form, so the sorted form becomes the key and the words collect under it.
• Caching. Designs like LRU Cache pair a map with a linked list to get fast reads and controlled eviction.

Complexity Analysis

The average case is what you will see in practice, and the worst case is what interviewers ask about.

The average numbers come from even spread. A good hash function distributes keys evenly across the buckets, so each bucket holds a constant number of entries on average and every operation touches exactly one bucket. The worst case appears when many keys collide into one bucket and a lookup becomes a list scan. Modern implementations rehash when load gets high and switch to balanced trees for long collision chains, so the average case is what you should assume in an interview.

Common Mistakes

These errors all share a root cause: treating the hash table as a magic box instead of a structure with rules.

Storing before checking in pair problems. Two Sum style algorithms must check for the complement before storing the current element. Store first, and an element can pair with itself. Take nums = [3] and target = 6. With store-first, the complement of 3 is 3, which is already in the map, so the answer comes back as [0, 0]. That is wrong, and it only shows up on tests where the target is exactly double one element. Catch it by tracing a single-element case before writing the loop.

Checking membership with an array scan. Writing if x in list inside a loop costs

Using a mutable key. The hash of a key is computed when it is inserted. If the key changes later, the computed index no longer matches the stored slot and the entry becomes unfindable. This is why tuples are safe keys in Python and lists are not. In an interview, when you are tempted to use a custom object as a key, convert it to something immutable first, like a tuple of its fields or a string.

Building counts from the wrong side. Count-down problems like Ransom Note count the source collection and decrement from the target. Swap the roles and the answer flips. The subtler version is reading a missing key without a default, so the first absent letter either crashes or is silently treated as present. Catch it by testing with a target that contains a letter the source does not have.

Related Patterns

• Two Pointers . When the input is sorted, two pointers find pairs in
  O(N)
  time with
  O(1)
  space. The hash table does the same job with
  O(N)
  memory. Pick two pointers when space matters, pick the hash table when the input is not sorted or you need to keep indices.
• Sliding Window . Window problems keep counts of characters or numbers inside a moving range, and most of them maintain that count in a hash map. If the hard part of a problem is the window mechanics, start on the sliding window page.
• Prefix Sum . Subarray sum problems pair a running sum with a map of sums seen so far. Subarray Sum Equals K lives on the prefix sum page, and the map is the hash table pattern doing the real work.

Next Steps

Once the concept is clear, the next step is making the code automatic. Check out the code templates for memorizable implementations in 6 languages, then work through the practice problems to apply the pattern to real interview questions.