Free lesson · DSA Mastery - Interview Prep, End to End

Introduction to Hash Tables

Medium6 min readdsahash-tables

Introduction to Hash Tables

Hash tables are the most useful data structure in interview problems. Probably more than half the problems you'll encounter have a hash table somewhere in the solution - either as the main tool or as a supporting structure. If you can recognize when a hash table is the right answer and use it correctly, you've covered a huge fraction of the algorithmic landscape.

This chapter gives you the mental model. The operations, the costs, the common patterns, and the reasons hash tables show up where they do.

What a Hash Table Is

A hash table is a data structure that stores key-value pairs with three core operations, all running in O(1) average time:

• Insert a key-value pair.
• Get the value for a given key.
• Delete a key.

The O(1) is what makes hash tables transformative. Operations that would naturally be O(n) on an array (find an element, count occurrences, group items by a property) drop to O(1) per query, turning O(n²) algorithms into O(n) ones.

Internally, a hash table uses a hash function to map keys to array indices, plus some collision-handling strategy (chaining or open addressing). You'll implement these yourself in topic 9.2 - for now, treat the hash table as a black box that supports O(1) average-time operations.

The Two Hash Table Variants

Most problems use one of two flavors:

Hash map (key → value): Used when you need to associate data with each key. Frequency counters (char → count), index lookups (value → index), graph adjacency (node → list of neighbors).

Hash set (just keys): Used when you only need to test membership. Duplicate detection, deduplication, set operations.

In Java, the standard implementations are HashMap<K, V> and HashSet<K>. The set is essentially a map with dummy values, so anything you can do with a set you can do with a map (and vice versa).

Time Complexity

The standard hash-table operations are O(1) average time, O(n) worst case.

The worst case happens when many keys collide on the same bucket. For Java's HashMap, the worst-case lookup is O(log n) (not O(n)) because once a bucket gets too long, it converts to a balanced tree.

For interview purposes, treat hash tables as O(1) average. Mention the worst case only if asked.

Space Complexity

A hash table storing n key-value pairs uses O(n) space - the n entries themselves, plus some overhead (typically 1.5x to 2x the entries for the underlying array and metadata).

The space overhead isn't free. When a problem says "O(1) extra space," using a hash table breaks that constraint.

The Five Patterns Worth Memorizing

Most interview problems involving hash tables use one of these five patterns.

Pattern 1: Frequency Counting

Count how often each key appears.

Map<Character, Integer> count = new HashMap<>();
for (char c : s.toCharArray()) {
    count.merge(c, 1, Integer::sum);
}

Then answer questions like "which character appears most?", "is any character repeated?", "do two strings have the same characters?"

Used in: Valid Anagram (topic 7.7), First Unique Character (topic 9.6), Group Anagrams (topic 9.13), and many others.

Pattern 2: Set Membership / Deduplication

Track which values you've seen.

Set<Integer> seen = new HashSet<>();
for (int num : nums) {
    if (!seen.add(num)) {
        // num is a duplicate
    }
}

Used in: Contains Duplicate (topic 9.8), Two Sum (next topic in Section 11), Longest Consecutive Sequence (topic 9.17).

Pattern 3: Lookup with Index

Store value → index (or value → some metadata) so you can answer "where is X?" in O(1).

Map<Integer, Integer> indexOf = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
    indexOf.put(nums[i], i);
}
// indexOf.get(targetValue) gives the index in O(1)

Used in: Two Sum (Section 11), LRU Cache (Section 27), many graph problems.

Pattern 4: Grouping by Key

Map each "category" to its members.

Map<String, List<String>> groups = new HashMap<>();
for (String s : strings) {
    String key = canonicalForm(s);
    groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}

Used in: Group Anagrams (topic 9.13), Group Shifted Strings (topic 9.14), partition problems.

Pattern 5: Complement Lookup

For each element, check if its "complement" exists in the set.

Set<Integer> seen = new HashSet<>();
for (int num : nums) {
    int complement = target - num;
    if (seen.contains(complement)) {
        // found a pair (complement, num) summing to target
    }
    seen.add(num);
}

Used in: Two Sum, Three Sum (Section 10), Subarray Sum problems (Section 11).

When to Reach for a Hash Table

If you find yourself writing nested loops with a "look up something I've seen before" pattern, the inner loop is usually doing a linear search that a hash table can replace with O(1) lookup. That's the most reliable signal.

Other signals:

• "Has this value been seen before?"
• "What's the count of each X?"
• "Given a key, return its value/index/metadata."
• "Group these items by some derived property."
• "For each item, does its complement exist?"

Counter-signals where you should not use a hash table:

• You need ordering. Hash tables don't maintain insertion order (or any order). Use TreeMap for sorted order, LinkedHashMap for insertion order, or sort the data.
• O(1) extra space is required. Hash tables use O(n) extra space.
• The keys are small integers in a known range. An array indexed by the value is faster than a hash table.
• The keys are characters from a small alphabet. A 26-entry array beats a hash map for lowercase letters.

Hash Table vs. Array vs. Tree

A quick comparison of the three most common "lookup" data structures:

The decision tree:

• Need O(1) lookup by key and don't care about order → hash table.
• Need to walk in sorted order or do range queries → tree.
• Keys are small integers in a contiguous range → array.

Common Pitfalls With Hash Tables

A few things that trip up candidates:

Using mutable keys. If you mutate a key after inserting it, the hash table can't find it again (because the hash code may have changed). Treat keys as immutable.

Using arrays as keys. Java's int[] doesn't override hashCode and equals, so two arrays with the same contents have different hash codes. Wrap arrays in Arrays.asList(...), use String representations, or use Arrays.toString(...) as the key.

Forgetting equals and hashCode. Custom classes used as keys must implement both methods consistently. If you only override one, the hash table will behave unexpectedly.

Treating O(1) as guaranteed. It's average. For adversarial inputs (rare in interviews, real in security-sensitive contexts), worst-case O(n) can hit.

Ignoring iteration order. HashMap.entrySet() iterates in some order that may vary between JVM versions and runs. Don't rely on iteration order; use LinkedHashMap if you need insertion order.

What This Section Covers

The 20 problem topics in Module 9 are organized by pattern:

• Design HashMap (1 topic): Implementing the data structure yourself - collision handling, resizing, the works.
• Frequency & Counting (5 topics): Maximum Number of Balloons, Number of Good Pairs, Ransom Note, First Unique Character, Find All Numbers Disappeared in an Array.
• Duplicate Detection (3 topics): Contains Duplicate, Contains Duplicate II, Intersection of Two Arrays II.
• Pattern Matching (4 topics): Isomorphic Strings, Word Pattern, Group Anagrams, Group Shifted Strings.
• Advanced Hashing (7 topics): TinyURL, Reorganize String, Longest Consecutive Sequence, and others that combine hashing with other techniques.

By the end of Module 9, you'll be able to identify when a hash table is the right answer for a problem you've never seen, and you'll have the patterns to apply it cleanly.

Let's start with the most foundational exercise: implementing a hash map from scratch.

Back to DSA Mastery - Interview Prep, End to End