Hashing Techniques: Frequency Counting & Custom Hash Design

1. Introduction & Motivation

A hash table turns "search through everything" into "look it up directly," giving $O(1)$ expected-time lookups, inserts, and deletes. That single property is why hash-based structures show up everywhere: caches, symbol tables, deduplication, and a huge share of coding-interview questions. But knowing how a hash table is built is different from knowing when and how to reach for one as a problem-solving tool.

This lesson assumes you already know what a hash table is and how it resolves collisions. It does not re-explain that machinery. Instead it focuses on the techniques that sit on top: recognizing the frequency-counting pattern, combining a hashmap with a running prefix sum, designing a hash function for your own data types, and understanding why some hash functions resist adversarial inputs better than others.

2. Prerequisites

Read Part 11: Heaps, Sorting & Hashing first if you have not already. That lesson covers, in full, the material this one deliberately does not repeat:

• What a hash table / hash set is, including a complete HashTable class with separate chaining, load factor, and rehashing.
• Collision handling — separate chaining versus open addressing, linear probing, and the tradeoffs between them.
• The three classic "Common Hash Table Problems": Two Sum, Group Anagrams, and Longest Consecutive Sequence, each implemented in Python, C++, and Java.

If any of those bullets are unfamiliar, go read that section now — everything below assumes you can already build and use a hash table, and instead teaches you new patterns for applying one.

3. A Concrete Example

4. Core Insight

5. Correctness

The pattern is correct because of a simple invariant: after processing index $i$, the hashmap contains every derived value produced by prefixes ending at or before $i$, each tagged with how many times it occurred. When index $i+1$ queries the hashmap for a target derived value, any hit corresponds to an earlier prefix that, combined with the elements between the two prefixes, produces exactly the property being counted. Because the hashmap is updated strictly after the query at each step, a prefix never matches against itself, and no valid pair is skipped because every earlier prefix remains in the map permanently (counts only grow, never shrink, during a single forward pass).

6. Complexity Analysis

7. Three-Language Implementation

The following implements the general running-derived-value-plus-hashmap technique, specialized here to counting subarrays with a target sum (the same shape used in the worked example above; the full Subarray Sum Equals K writeup with LeetCode framing follows in section 9).

from collections import defaultdict

def count_matches(nums, k):
    """
    Count subarrays whose elements sum to k, using a running
    prefix sum plus a hashmap of prefix-sum occurrence counts.
    Time: O(n), Space: O(n)
    """
    seen = defaultdict(int)
    seen[0] = 1  # empty prefix
    curr_sum = 0
    total = 0

    for value in nums:
        curr_sum += value
        total += seen[curr_sum - k]
        seen[curr_sum] += 1

    return total

sample = [1, 2, 3, -3, 4]
print("Matching subarrays:", count_matches(sample, 3))  # Matching subarrays: 3

#include <iostream>
#include <unordered_map>
#include <vector>

int countMatches(const std::vector<int>& nums, int k) {
    std::unordered_map<int, int> seen;
    seen[0] = 1;  // empty prefix
    int currSum = 0;
    int total = 0;

    for (int value : nums) {
        currSum += value;
        auto it = seen.find(currSum - k);
        if (it != seen.end()) {
            total += it->second;
        }
        seen[currSum]++;
    }

    return total;
}

int main() {
    std::vector<int> sample{1, 2, 3, -3, 4};
    std::cout << "Matching subarrays: " << countMatches(sample, 3) << '\n';
}

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class RunningFrequencyCount {
    static int countMatches(List<Integer> nums, int k) {
        Map<Integer, Integer> seen = new HashMap<>();
        seen.put(0, 1); // empty prefix
        int currSum = 0;
        int total = 0;

        for (int value : nums) {
            currSum += value;
            total += seen.getOrDefault(currSum - k, 0);
            seen.merge(currSum, 1, Integer::sum);
        }

        return total;
    }

    public static void main(String[] args) {
        List<Integer> sample = List.of(1, 2, 3, -3, 4);
        System.out.println("Matching subarrays: " + countMatches(sample, 3)); // Matching subarrays: 3
    }
}

8. Topic-Specific Deep Dives

The Frequency-Counting Pattern

The frequency-counting pattern is a general technique, not a single trick tied to one problem: use a hashmap to count how many times each value, character, or derived key appears, then answer the actual question from those counts instead of rescanning the input. Recognizing it means noticing any of these question shapes:

• "How many times does X occur?" — count directly.
• "What is the most/least frequent element?" — count, then take a max/min over the counts.
• "Are two collections permutations of each other?" — count both, compare the count maps.
• "How many pairs/subarrays/substrings satisfy a sum, difference, or parity condition?" — count a derived quantity (a running sum, a running XOR, a character-count signature) rather than the raw elements.

The pattern always has the same two-phase shape: a counting phase that builds a hashmap of key → frequency in $O(n)$, followed by a query phase that reads from that map in $O(1)$ per query. When the "key" being counted is the raw input value, this looks like plain frequency counting (contains-duplicate style problems). When the "key" is a running derived value computed incrementally, it looks like the running-sum technique traced above — same pattern, different key.

Subarray Sum Equals K

LeetCode 560, Subarray Sum Equals K: given an integer array nums and an integer k, return the number of contiguous subarrays whose sum equals k. This is the general technique from section 7, made concrete and complete:

from collections import defaultdict

def subarray_sum(nums, k):
    """
    LeetCode 560: Subarray Sum Equals K
    Time: O(n), Space: O(n)
    """
    prefix_counts = defaultdict(int)
    prefix_counts[0] = 1
    running_sum = 0
    result = 0

    for num in nums:
        running_sum += num
        # If (running_sum - k) was seen before, every subarray
        # from just after that earlier prefix to here sums to k.
        result += prefix_counts[running_sum - k]
        prefix_counts[running_sum] += 1

    return result

print("Count:", subarray_sum([1, 2, 3, -3, 4], 3))  # Count: 3
print("Count:", subarray_sum([1, 1, 1], 2))          # Count: 2

#include <iostream>
#include <unordered_map>
#include <vector>

int subarraySum(const std::vector<int>& nums, int k) {
    std::unordered_map<int, int> prefixCounts;
    prefixCounts[0] = 1;
    int runningSum = 0;
    int result = 0;

    for (int num : nums) {
        runningSum += num;
        auto it = prefixCounts.find(runningSum - k);
        if (it != prefixCounts.end()) {
            result += it->second;
        }
        prefixCounts[runningSum]++;
    }

    return result;
}

int main() {
    std::vector<int> a{1, 2, 3, -3, 4};
    std::cout << "Count: " << subarraySum(a, 3) << '\n'; // Count: 3
    std::vector<int> b{1, 1, 1};
    std::cout << "Count: " << subarraySum(b, 2) << '\n'; // Count: 2
}

import java.util.HashMap;
import java.util.Map;

public class SubarraySumEqualsK {
    static int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> prefixCounts = new HashMap<>();
        prefixCounts.put(0, 1);
        int runningSum = 0;
        int result = 0;

        for (int num : nums) {
            runningSum += num;
            result += prefixCounts.getOrDefault(runningSum - k, 0);
            prefixCounts.merge(runningSum, 1, Integer::sum);
        }

        return result;
    }

    public static void main(String[] args) {
        System.out.println("Count: " + subarraySum(new int[]{1, 2, 3, -3, 4}, 3)); // Count: 3
        System.out.println("Count: " + subarraySum(new int[]{1, 1, 1}, 2));         // Count: 2
    }
}

It is tempting to file this under "just prefix sums," but it needs more than the plain prefix-sum technique from Prefix Sums, Difference Arrays & Coordinate Compression. That lesson's prefix-sum array answers range-sum queries: given fixed endpoints $i$ and $j$, what is the sum of nums[i..j]? It precomputes an array once and then answers each query in $O(1)$ by subtracting two precomputed values, because the endpoints are known in advance.

Subarray Sum Equals K does not have fixed endpoints — it asks "for how many pairs of endpoints does the sum equal $k$," across all possible pairs simultaneously. There is no query with known $i$ and $j$ to look up; instead, the problem needs to count how many times a particular running-sum value has occurred so far, so that every earlier occurrence can pair with the current position. That counting requirement — not just storing prefix sums, but tallying how often each one repeats — is exactly why a hashmap is layered on top of the running sum. Plain prefix sums answer range queries; this problem counts occurrences of a running value, which is a hashmap's job.

Designing a Custom Hash Function

Built-in types already have good hash functions, but real systems frequently need to hash custom objects — a 2D point, a composite key, a small record. Suppose you want to hash a point (x, y) with integer coordinates so it can be used as a dictionary key or set member.

A naive first attempt, hash = x + y, is a poor choice: points like (1, 5) and (3, 3) collide even though they are unrelated, and the hash barely uses the available output range — points along any diagonal x + y = c all land in the same bucket, causing exactly the clustering that good hash design tries to avoid. A better approach mixes the coordinates so that changing either one changes most of the output bits, and multiplies by odd, non-trivial constants (large primes work well) to spread values across the table:

class Point:
    """
    A hashable 2D integer point. Python requires that objects
    which are equal (__eq__) also produce equal hashes (__hash__) -
    breaking this contract silently corrupts sets and dict lookups.
    """
    __slots__ = ("x", "y")

    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __eq__(self, other):
        return isinstance(other, Point) and self.x == other.x and self.y == other.y

    def __hash__(self):
        # Mix both coordinates with distinct large primes so that
        # points on the same diagonal or row do not cluster together.
        return hash((self.x * 73856093) ^ (self.y * 19349663))

    def __repr__(self):
        return f"Point({self.x}, {self.y})"

seen = set()
seen.add(Point(1, 5))
seen.add(Point(3, 3))
print("(1, 5) already seen:", Point(1, 5) in seen)  # True
print("(5, 1) already seen:", Point(5, 1) in seen)   # False - order matters

#include <cstddef>
#include <functional>
#include <iostream>
#include <unordered_set>

struct Point {
    int x, y;
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// C++ requires a matching hash specialization or a custom hasher
// passed to the container - equal points must hash identically.
struct PointHash {
    std::size_t operator()(const Point& p) const noexcept {
        std::size_t hx = std::hash<int>{}(p.x) * 73856093u;
        std::size_t hy = std::hash<int>{}(p.y) * 19349663u;
        return hx ^ hy;
    }
};

int main() {
    std::unordered_set<Point, PointHash> seen;
    seen.insert({1, 5});
    seen.insert({3, 3});
    std::cout << "(1, 5) already seen: " << (seen.count({1, 5}) > 0) << '\n'; // 1
    std::cout << "(5, 1) already seen: " << (seen.count({5, 1}) > 0) << '\n'; // 0
}

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

public class Point {
    private final int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object other) {
        if (!(other instanceof Point)) return false;
        Point p = (Point) other;
        return x == p.x && y == p.y;
    }

    @Override
    public int hashCode() {
        // Java requires equal objects (equals()) to share a hashCode() -
        // violating this contract makes HashMap/HashSet lookups fail silently.
        return Objects.hash(x * 73856093, y * 19349663);
    }

    public static void main(String[] args) {
        Set<Point> seen = new HashSet<>();
        seen.add(new Point(1, 5));
        seen.add(new Point(3, 3));
        System.out.println("(1, 5) already seen: " + seen.contains(new Point(1, 5))); // true
        System.out.println("(5, 1) already seen: " + seen.contains(new Point(5, 1))); // false
    }
}

Three design points generalize beyond points: (1) the equals/hash contract is non-negotiable — Python's __hash__/__eq__ and Java's hashCode()/equals() both require that objects considered equal produce the same hash, or lookups silently fail even when an "equal" entry is already stored. (2) combine fields with XOR and multiplication by distinct constants, never plain addition, so that no simple linear relationship between fields (like a shared diagonal) creates clustering. (3) test distribution by hashing a representative sample of your real keys and checking bucket occupancy is roughly uniform, not just testing a handful of arbitrary examples.

A Note on Universal Hashing

Every hash function has inputs that collide — for any fixed function $h$ mapping a large key space into $m$ buckets, an adversary who knows $h$ can always construct a set of keys that all hash to the same bucket, collapsing average-case $O(1)$ operations into worst-case $O(n)$. This is not a bug in a particular implementation; it is unavoidable for any single, fixed hash function.

Universal hashing sidesteps the problem by using a family of hash functions rather than one fixed function, and choosing a member of that family at random each time a hash table is created. A family is called universal if, for any two distinct fixed keys, the probability that a randomly chosen function from the family sends them to the same bucket is at most $1/m$ — the same bound you would expect from a genuinely random function. Because the choice of function is randomized and hidden from whoever supplies the keys, no adversary can pick inputs in advance that are guaranteed to collide against whichever function actually gets chosen.

This matters most for adversarial-input resistance: a public-facing service that hashes attacker-controlled strings (form fields, URL parameters, uploaded identifiers) into an internal hash table can be deliberately driven toward its worst case unless the hash function is unpredictable to the attacker. A full treatment of universal hashing families — their construction, the algebra behind proving the $1/m$ bound, and how languages like Python randomize string hashing per-process to get this property in practice — lives in a later, more advanced curriculum entry; this is just the concept, not an implementation.

9. Applications & Alternatives

Alternatives exist for each technique: a Fenwick tree or segment tree can answer sum-range queries with updates, trading simplicity for $O(\log n)$ update support the hashmap-based running count does not need. A sorted structure (balanced BST, sorted array with binary search) can replace a hash set when ordered traversal or range queries matter more than raw $O(1)$ lookup. For custom hash functions, language-provided combinators (Python's hash(tuple), C++'s boost::hash_combine, Java's Objects.hash) are usually good enough and safer than a hand-rolled mix unless you have measured a real distribution problem.

10. Exercises

Easy

1. Given an array and an integer k, determine whether the array contains two equal values whose indices differ by at most k (a Two Sum variant using a hashmap of value → last-seen index).
2. Given two strings, use frequency counting to determine whether one is an anagram of the other without sorting either string.

Medium

1. Given an array nums and an integer k, count the number of contiguous subarrays whose sum is divisible by k (a Subarray Sum Equals K variant: hash the remainder of the running sum modulo k instead of the sum itself).
2. Design a hash function for a small fixed-length string (for example, a 3-character ticker symbol) and discuss how you would verify it distributes realistic inputs evenly across a table of 1024 buckets.

Hard

1. Given a string and an integer k, find the length of the longest substring containing at most k distinct characters. This combines the frequency-counting pattern with the sliding-window technique from Two Pointers & Sliding Window: maintain a hashmap of character counts inside a shrinking/growing window and shrink the window whenever the distinct-character count exceeds k.

Review rhythm: tomorrow, re-derive the running-sum-plus-hashmap trace for a new small array without looking at this page; next week, implement Subarray Sum Equals K from memory in all three languages and then adapt it to the divisible-by-k variant; several weeks later, design a hash function for a different custom type (a 3-tuple, a small immutable record) and check it against the same three design points — contract, mixing, distribution. Finally, explain to someone else why plain prefix sums and this lesson's technique solve different problems despite both starting from a running sum.

11. Summary Cheat Sheet

• The frequency-counting pattern: build a hashmap of key → count in one pass, then answer the real question from those counts.
• The running-derived-value technique: compute a quantity incrementally (running sum, running XOR, running remainder) and query a hashmap of past values before inserting the current one.
• Subarray Sum Equals K needs a hashmap on top of a running sum because it counts occurrences of a value across all pairs of endpoints, not a single range query with fixed endpoints — that is the job of plain prefix sums.
• Custom hash functions must respect the equals/hash contract, mix fields with XOR and distinct multipliers instead of addition, and be checked against representative real data for uniform distribution.
• Universal hashing uses a randomly chosen family member per hash table instance so no adversary can predict collisions in advance; it defends against algorithmic-complexity attacks on public-facing hash tables.
• These techniques compose: frequency counting plus sliding window solves substring-with-constraint problems; running-sum-plus-hashmap generalizes to any "count occurrences of a repeated derived value" problem.