How a Hash Table Works (Build a Tiny One)

The coat check

At a theatre you hand in your coat and get ticket #17. Later you show the ticket and the attendant walks straight to hook 17 – no searching through every coat. A hash table works the same way: a hash function turns any key into a hook (bucket) number.

A tiny hash set

Our hash function: the number modulo the number of buckets. Each bucket is a small list, because two keys can land in the same bucket (a collision):

import java.util.ArrayList;

class TinyHashSet {
    private ArrayList<ArrayList<Integer>> buckets = new ArrayList<ArrayList<Integer>>();

    TinyHashSet(int bucketCount) {
        for (int i = 0; i < bucketCount; i++) buckets.add(new ArrayList<Integer>());
    }

    private int bucketOf(int key) {             // the hash function
        return Math.abs(key % buckets.size());
    }

    void add(int key) {
        ArrayList<Integer> b = buckets.get(bucketOf(key));
        if (!b.contains(key)) b.add(key);
    }

    boolean contains(int key) {                 // look in ONE small bucket only
        return buckets.get(bucketOf(key)).contains(key);
    }

    void show() {
        for (int i = 0; i < buckets.size(); i++) System.out.println("bucket " + i + ": " + buckets.get(i));
    }
}

public class Main {
    public static void main(String[] args) {
        TinyHashSet set = new TinyHashSet(5);
        int[] keys = {12, 7, 33, 20, 18, 45};
        for (int k : keys) set.add(k);
        set.show();
        System.out.println("has 33? " + set.contains(33));
        System.out.println("has 34? " + set.contains(34));
    }
}

Output

bucket 0: [20, 45]
bucket 1: []
bucket 2: [12, 7]
bucket 3: [33, 18]
bucket 4: []
has 33? true
has 34? false

To find 33 we only looked in bucket 3 – not at all six numbers. If the buckets stay short, every add and lookup is O(1) on average. Java's real HashSet and HashMap keep buckets short by growing (doubling the buckets) when they fill up – the same trick as your growing list.

Remember: Hashing = key → bucket number → look only there. Average O(1) for add, remove and contains.

Tip: For Strings and your own classes, Java calls hashCode() to get the number and equals() to compare keys inside a bucket. Built-in types like String and Integer already have both.