Hashing: counting and lookups

Hashing is how sets and maps find a value without scanning everything. Many interview problems become easy with one question: "have I seen this before, and how many times?" Interviewers ask hashing problems (two sum, duplicates, word counts, anagrams) because they show whether you can replace a slow loop inside a loop with a fast lookup, the most common speed-up in real code.

Sets and maps

A set stores distinct values and answers "is this value in here?". A map stores keys with a value for each key, such as a word and its count, or a number and its position. Both turn the key into a number (its hash) that points to a place in memory (a slot), so a lookup goes straight to the right place. On average, adding, removing and looking up take constant time. In Java you use HashSet and HashMap; in Python, set and dict.

The payoff is speed. Checking "is x in this list?" by scanning costs O(n), and doing that for every value costs O(n²). With a set, each check costs O(1) on average, so the whole job is O(n). For 100,000 values that is about 100,000 steps instead of about five billion.

Order: the detail that decides many answers

Hidden tests often expect results in a specific order, so know what each structure keeps. Java's HashMap and HashSet promise no order; LinkedHashMap and LinkedHashSet keep insertion order (the order in which values were added); TreeMap and TreeSet keep keys sorted, at O(log n) per operation. A Python dict keeps insertion order (guaranteed since Python 3.7), while a set promises none. When a problem says "in the order the characters first appear", use an insertion-ordered map; when it says "sorted by value", sort the keys at the end or use a sorted map.

Pattern 1: seen before

Walk the values and keep a set of what you have passed. "Remove duplicates but keep the order", "are all characters unique" and "first repeated value" all use it. For 3, 1, 3, 2 the set holds 3, then 3 and 1, and the second 3 is found in it, so 3 is the first repeat. You can stop as soon as the answer is known.

Pattern 2: count, then decide

Count every value in a map first, and only then decide. "First character that does not repeat" needs the full counts before any character can be called unique: in "swiss" the counts are s = 3, w = 1, i = 1, and a second walk over the string finds w first. "Find the duplicates", "word frequency" and "are these anagrams" start the same way. Counting in Java: counts.put(key, counts.getOrDefault(key, 0) + 1); in Python: counts[key] = counts.get(key, 0) + 1.

Pattern 3: value to position

Two sum is the best-known example: find two positions whose values add up to a target. For each value, the partner you need is the target minus that value. Keep a map from each value already seen to its position, check the map for the partner, and only then store the current value. Here is the walk for 3, 2, 4 and target 6:

Position	Value	Partner needed	In the map?	Map afterwards
0	3	3	no (a value cannot pair with itself)	3 at 0
1	2	4	no	3 at 0, 2 at 1
2	4	2	yes, at 1: answer 1 and 2	unchanged

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] nums = {3, 2, 4};
        int target = 6;
        Map<Integer, Integer> positionOf = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            Integer j = positionOf.get(target - nums[i]);
            if (j != null) {
                System.out.println(j + " " + i);
            }
            positionOf.put(nums[i], i);
        }

        Map<Character, Integer> counts = new LinkedHashMap<>();
        for (char c : "banana".toCharArray()) {
            counts.put(c, counts.getOrDefault(c, 0) + 1);
        }
        System.out.println(counts);
    }
}

1 2
{b=1, a=3, n=2}

nums = [3, 2, 4]
target = 6
position_of = {}
for i, value in enumerate(nums):
    if target - value in position_of:
        print(position_of[target - value], i)
    position_of[value] = i

counts = {}
for ch in "banana":
    counts[ch] = counts.get(ch, 0) + 1
print(counts)

1 2
{'b': 1, 'a': 3, 'n': 2}

Pattern 4: a computed key

Sometimes the key is computed from the value. To group anagrams, sort the letters of each word: "eat", "tea" and "ate" all become "aet", so a map from that sorted text to a list of words collects each group. To count runs that add up to k, the key is a running total: keep a map from each running total to how many times it has appeared, and at each step look up the current total minus k.

How to answer in an interview

Start with the brute force (trying every possibility) and its cost ("compare every pair, O(n²)"), then say which question a set or map answers in one step. Name the structure and why you picked it, especially when order matters. Finish with both costs: O(n) time on average, and O(n) extra memory. If memory is tight, sorting first is the usual alternative at O(n log n).

Common mistakes

• Using a map without insertion order when the output must follow first appearance.
• Storing the current value before checking for its partner, so a value pairs with itself.
• Deciding "unique" during the first pass, before all counts are known.
• In Java, comparing two Integer values taken from a map with ==, which compares objects, not numbers. Use equals or convert them to plain int values first.

Recap

When you find yourself writing a loop inside a loop to look something up, ask whether a set or a map can answer that inner question in one step. Count first when you need totals, and choose the structure that keeps the order the problem asks for.