☕ DSA Java Articles

Topics › Basics › Learn Basic Hashing

Basic Hashing

Easy TUF ID 1203 A2Z

Java source ↗ Edit this article ↗

What hashing means here

In interview problems, hashing means one simple strategy: pre-store information about the input once, so that later questions about it can be fetched in constant time instead of rescanning the data. The classic motivating task: given an array, answer many queries of the form “how many times does x occur?”.

This is a concept article. It explains the idea with the counting task, shows the three containers you will use for it (a plain array, a character array, and HashMap), and then opens up HashMap to show what a hash function, a collision and a bucket actually are. Every snippet is a method in the accompanying Java file and is tested in its main.

Running example

arr = [1, 3, 2, 1, 3]
queries = [1, 4, 2, 3, 12]
answers = [2, 0, 1, 2, 0]      // 1 occurs twice, 4 never, 2 once, 3 twice, 12 never

Without hashing: rescan for every query

Intuition. The obvious method is to loop over the array once per query and count matches. It is correct and uses no extra memory, but it does the same scanning work over and over.

static int[] countQueriesBrute(int[] arr, int[] queries) {
    int[] answers = new int[queries.length];
    for (int i = 0; i < queries.length; i++) {
        int count = 0;
        for (int v : arr) if (v == queries[i]) count++;
        answers[i] = count;
    }
    return answers;
}

Complexity. Time O(n × q) for n elements and q queries. With n = q = 10^5 that is 10^10 steps, which is far too slow. Space O(1) beyond the output.

Number hashing with an array

Intuition. Make one pass over the array and record, for every value v, how often it appears, in a second array hash where the value itself is the index: hash[v]++. A query for x is then just hash[x], one memory read. The scan happens once, not once per query.

Two things must hold for this to work: values must be non-negative (they are indices) and bounded by something we can allocate (hash has maxValue + 1 slots). A query outside that range is simply answered with 0.

static int[] countQueriesArrayHash(int[] arr, int[] queries) {
    int maxValue = 0;
    for (int v : arr) maxValue = Math.max(maxValue, v);
    int[] hash = new int[maxValue + 1];
    for (int v : arr) hash[v]++;                                    // pre-storing step
    int[] answers = new int[queries.length];
    for (int i = 0; i < queries.length; i++) {
        int q = queries[i];
        answers[i] = (q >= 0 && q <= maxValue) ? hash[q] : 0;      // fetching step
    }
    return answers;
}

Dry run of the pre-storing step on arr = [1, 3, 2, 1, 3]: hash starts as [0, 0, 0, 0], then becomes [0, 1, 0, 0], [0, 1, 0, 1], [0, 1, 1, 1], [0, 2, 1, 1], [0, 2, 1, 2]. Query 3 reads hash[3] = 2.

Complexity. Time O(n + q + maxValue). Space O(maxValue).

How big can the array be? A Java int[] of 10^7 elements is 40 MB, which is usually acceptable; 10^8 is 400 MB and usually not. So array hashing is the tool when values are at most around 10^6–10^7. If values go up to 10^9, or can be negative, you need a map.

Character hashing

Intuition. Characters are small integers, so a string can be hashed into an array too. For lowercase letters, map 'a' to slot 0, 'b' to slot 1, … with c - 'a', giving a 26-slot table. If the string may contain any character up to code 255 (letters of both cases, digits, punctuation), skip the subtraction and index directly with the character, using 256 slots.

static int[] charFrequencyLowercase(String s) {
    int[] hash = new int[26];
    for (int i = 0; i < s.length(); i++) hash[s.charAt(i) - 'a']++;
    return hash;
}

static int[] charFrequencyAscii(String s) {
    int[] hash = new int[256];
    for (int i = 0; i < s.length(); i++) hash[s.charAt(i)]++;
    return hash;
}

For "hello", charFrequencyLowercase gives hash['l' - 'a'] = 2 and hash['h' - 'a'] = 1. For "Hello, World!", charFrequencyAscii gives hash['l'] = 3, hash['o'] = 2, hash['H'] = 1 and hash['h'] = 0 (case matters), and even counts the space and the exclamation mark.

Complexity. Time O(n), space O(26) or O(256), i.e. constant.

Hashing arbitrary keys with HashMap

Intuition. When values can be negative, huge, or sparse (a handful of distinct values spread across the whole int range), an array indexed by value is impossible. HashMap<Integer, Integer> provides the same “value in, count out” interface without needing a slot for every possible key: it stores only the keys that actually occur. merge(v, 1, Integer::sum) means “if v is absent store 1, otherwise add 1 to the stored count”, and getOrDefault(x, 0) fetches a count or 0 for an unseen key.

static int[] countQueriesMapHash(int[] arr, int[] queries) {
    Map<Integer, Integer> hash = new HashMap<>();
    for (int v : arr) hash.merge(v, 1, Integer::sum);               // pre-storing step
    int[] answers = new int[queries.length];
    for (int i = 0; i < queries.length; i++) answers[i] = hash.getOrDefault(queries[i], 0);   // fetching step
    return answers;
}

Complexity. Time O(n + q) on average, because put, merge and get are O(1) on average. Space O(d) where d is the number of distinct values, never more than n.

When to use which. Array hashing when keys are small non-negative integers or characters: it is faster, has no boxing overhead and a guaranteed O(1). HashMap for everything else. TreeMap when you also need keys in sorted order; its operations are O(log n).

What a hash table does internally

Intuition. HashMap cannot have one slot per possible key, so it keeps a small array of buckets and uses a hash function to decide which bucket a key belongs to. The simplest hash function is the division method: bucket = key mod capacity. Different keys can land in the same bucket, which is called a collision; the standard fix, separate chaining, makes each bucket a linked list of the entries that hashed there. Looking up a key means hashing to its bucket and walking that short list.

The class below is a deliberately small table (16 buckets) that counts integer keys exactly like countQueriesMapHash. Math.floorMod is used instead of % so that negative keys still map into [0, capacity).

static class ChainedHashTable {
    private static class Node {
        final int key;
        int count;
        Node next;
        Node(int key, Node next) { this.key = key; this.count = 1; this.next = next; }
    }

    private final Node[] buckets;

    ChainedHashTable(int capacity) { buckets = new Node[capacity]; }

    /** The hash function. floorMod keeps negative keys inside [0, capacity). */
    int bucketOf(int key) { return Math.floorMod(key, buckets.length); }

    void increment(int key) {
        int b = bucketOf(key);
        for (Node cur = buckets[b]; cur != null; cur = cur.next) {
            if (cur.key == key) { cur.count++; return; }            // key already in this chain
        }
        buckets[b] = new Node(key, buckets[b]);                     // new key: push onto the chain
    }

    int count(int key) {
        for (Node cur = buckets[bucketOf(key)]; cur != null; cur = cur.next) {
            if (cur.key == key) return cur.count;
        }
        return 0;
    }
}

Using it looks exactly like using the map:

static int[] countQueriesChained(int[] arr, int[] queries) {
    ChainedHashTable table = new ChainedHashTable(16);              // tiny on purpose, so collisions really happen
    for (int v : arr) table.increment(v);
    int[] answers = new int[queries.length];
    for (int i = 0; i < queries.length; i++) answers[i] = table.count(queries[i]);
    return answers;
}

Dry run with arr = [0, 16, 32, 48, 1]. All of 0, 16, 32, 48 are 0 mod 16, so they collide into bucket 0, whose chain becomes 48 → 32 → 16 → 0 (new keys are pushed at the front). Key 1 goes to bucket 1. A query for 64 hashes to bucket 0, walks four nodes, finds nothing and returns 0; a query for 16 walks to the third node and returns 1.

Why it is O(1) on average, and when it is not. With a decent hash function and a table that grows when it fills up (Java’s HashMap doubles its capacity when the number of entries exceeds 75 % of it), chains stay a constant length on average, so operations are O(1). If every key collides, as in the dry run, the table degrades into one long linked list and every operation becomes O(n). That is the famous worst case and the reason anti-hash tests exist in competitive programming; Java mitigates it by converting long chains into balanced trees. For interviews, “average O(1), worst case O(n)” is the thing to say.

hashCode and equals. When you use your own class as a HashMap key, both methods must be overridden consistently: equal objects must have equal hash codes, otherwise the map looks in the wrong bucket and never finds the entry. Records and the boxed primitives already do this correctly.

Edge cases and pitfalls