Hashing & Hash Tables

A hash table stores key-value pairs and lets you look up a value by its key in average O(1) time. It works by running the key through a hash function that converts it into an array index, then storing the value at that index. Instead of scanning through data, you jump almost directly to the right slot. This is the structure behind dictionaries, maps, and sets in nearly every language.

What a hash function does

A hash function takes a key — a string, a number, anything — and produces an integer. That integer, reduced with modulo to fit the table size, becomes the slot (or bucket) where the value lives. Storing "phone" -> 9876543210 might compute hash("phone") % size = 4, so the pair goes in bucket 4. To look it up later, you recompute the same hash, land on bucket 4, and read the value. No searching required.

A good hash function spreads keys evenly across buckets and is fast to compute. Even distribution is what keeps lookups close to O(1).

Collisions are inevitable

Because many possible keys map into a limited number of buckets, two different keys will sometimes hash to the same slot. This is a collision, and handling it well is the heart of a hash table. Two common strategies:

• Chaining — each bucket holds a small linked list of entries. Colliding keys append to the list; lookup scans the short list.
• Open addressing — on collision, probe to the next free slot by a fixed rule and store there.

As long as collisions stay rare (the table is not too full), operations stay near O(1).

A simple chained hash table in Java

import java.util.*;

// A tiny string-to-integer hash map using chaining.
class SimpleHashMap {
    private List<List<int[]>> buckets; // each bucket holds [keyHash, value] pairs
    private List<List<String>> keys;   // parallel keys for correctness on collisions
    private int size;

    SimpleHashMap(int size) {
        this.size = size;
        buckets = new ArrayList<>();
        keys = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            buckets.add(new ArrayList<>());
            keys.add(new ArrayList<>());
        }
    }

    // Reduce a key to a bucket index. O(length of key).
    private int bucketIndex(String key) {
        int h = key.hashCode();
        return Math.floorMod(h, size); // floorMod keeps the index non-negative
    }

    // Store or update a key. Average O(1).
    void put(String key, int value) {
        int i = bucketIndex(key);
        List<String> ks = keys.get(i);
        List<int[]> vs = buckets.get(i);
        for (int j = 0; j < ks.size(); j++) {
            if (ks.get(j).equals(key)) { // key already present: update it
                vs.get(j)[0] = value;
                return;
            }
        }
        ks.add(key);                    // new key: append to the bucket's chain
        vs.add(new int[]{value});
    }

    // Look up a key. Average O(1); worst case O(n) if all keys collide.
    Integer get(String key) {
        int i = bucketIndex(key);
        List<String> ks = keys.get(i);
        for (int j = 0; j < ks.size(); j++) {
            if (ks.get(j).equals(key)) {
                return buckets.get(i).get(j)[0];
            }
        }
        return null; // not found
    }

    public static void main(String[] args) {
        SimpleHashMap map = new SimpleHashMap(8);
        map.put("phone", 9876543210 % 100000); // store a value
        map.put("city", 425001);
        System.out.println(map.get("city"));  // 425001
        System.out.println(map.get("email")); // null
    }
}

Most of the time the bucket's chain is short, so get and put touch only a handful of entries — effectively constant time.

Average O(1), worst case O(n)

The headline O(1) is an average under a good hash function and a reasonable load factor (entries divided by buckets). In the worst case — a bad hash function, or an attacker deliberately feeding colliding keys — every key lands in one bucket and lookup degrades to scanning a single long chain, which is O(n). Real implementations defend against this by resizing the table when it fills and using well-designed hash functions.

When to use a hash table

Reach for a hash table when you need fast lookups, insertions, and deletions by key and you do not care about order. It is the go-to for counting frequencies, deduplication, caching, and membership tests. If you need keys kept in sorted order or range queries, a binary search tree is the better choice.

Common mistakes

• Letting the table get too full. A high load factor means more collisions and slower operations. Resize before it fills up.
• Using a weak hash function. Poor distribution clusters keys into few buckets and ruins performance. Use the language's built-in hashing for standard types.
• Mutating keys after insertion. If a key's hash changes after you store it, you can never find it again. Use immutable keys.
• Expecting order. Hash tables do not preserve insertion or sorted order. If iteration order matters, use an ordered map or sort separately.
• Quoting O(1) as a guarantee. It is an average. Mention the O(n) worst case when correctness or security depends on timing.

FAQ

Hash table or BST? A hash table gives faster average lookups but no ordering. A binary search tree keeps keys sorted and supports range queries. Choose based on whether you need order.

What is a load factor? It is the ratio of stored entries to buckets. Keeping it low (resizing when it grows) keeps collisions rare and operations near O(1).

Keep learning

Compare ordered lookups in Binary Search Trees, revisit Big-O Notation to ground the average-versus-worst-case idea, and browse the full DSA hub.

Want to build hash tables and handle collisions with instructor feedback in Jalgaon? Join the waitlist for our Data Structures & Algorithms course.