Hash tables: hash function, collisions and load factor

← Back to the section

Trees search in O(log N) — fast. But there is a structure that is faster still: a hash table gives access by key in O(1) on average — constant time that does not depend on how much data you hold. It is the fastest structure for lookup by key, and therefore one of the most used.

The idea: turn a key into an index

An array has one superpower — instant access by index. The only problem is that an index is a number from 0 to the array size, while keys can be anything (large numbers, strings). A hash table bridges that gap: it runs the key through a hash function that turns it into an array index.

The simplest example is taking the key modulo the array size: index = key % size. The index is then computed in a single step and we go straight to the right slot: no scanning, no descending a tree.

Let's spread the keys over the buckets: eight keys, seven buckets, the remainder of a division instead of a hash function.

live example

import java.util.ArrayList;
import java.util.List;

public class Buckets {
    public static void main(String[] args) {
        int[] keys = {31, 9, 18, 25, 44, 12, 7, 20};
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < 7; i++) buckets.add(new ArrayList<>());
        int collisions = 0;
        for (int key : keys) {
            List<Integer> bucket = buckets.get(key % 7);
            if (!bucket.isEmpty()) collisions++;
            bucket.add(key);
        }
        System.out.println("buckets: " + buckets);
        System.out.println("collisions: " + collisions + " of " + keys.length);
    }
}

Two keys out of eight landed in a bucket that was already taken.

Collisions are unavoidable

There are many different keys and only a limited number of slots, so sooner or later two keys produce the same index. That is a collision: it cannot be avoided, only handled — in one of two ways.

Open addressing

On a collision we look for another free slot in the same array. The variants differ in how exactly we look:

• linear probing — walk the neighbouring slots (index+1, index+2…) until a free one shows up. Simple, but it causes clustering — long occupied runs that slow the search down;
• quadratic probing — step further and further away (index+1, index+4, index+9…) so that clusters do not build up as badly;
• double hashing — the step size comes from a second hash function, so different keys scatter differently. The best of the open-addressing variants.

The common trouble with open addressing: the denser the array, the longer the probes. Hence an important notion — the load factor, the ratio of stored entries to array size. While it stays low (say, up to ~2/3), access remains close to O(1); as it approaches one, the table slows down sharply and has to grow (rehash into a bigger array).

Separate chaining

The other approach is to keep in every slot not a single entry but a linked list of all entries with that index. A collision simply appends an element to the list of the right slot. Here the load factor may exceed one, and the table does not freeze when it fills up — it degrades gradually. Chaining is simpler and more tolerant of a high load, which is why it is often preferred.

Hash functions

The quality of a table is decided by its hash function. A good one has to be:

• fast — it is called on every operation;
• uniform — spreading keys over the whole range of indices instead of piling them up (otherwise collisions go through the roof).

The practical tricks depend on how the bucket number is computed. If it is the remainder of dividing the hash by the array size, the size is chosen to be a prime number — regular keys such as "every tenth one" then collide less often. The other route is a power-of-two size and cheap bit operations instead of a division; that is how HashMap is built. Strings are hashed by combining character codes with multiplication (Horner's scheme) so that different strings produce different hashes. A poor hash function turns a fast table into a slow list.

What a hash table cannot do

Speed has a price:

• no order. Elements are scattered across the array pseudo-randomly, so you cannot walk them in ascending order or find the "next larger" one quickly — trees are used for that;
• useless without the key. Fast access exists only when the exact key is known; a range search or a partial match gains nothing;
• spends memory. To keep collisions rare, the array is held noticeably roomier than the data.

How it is done in Java

You almost never have to write your own hash table — Java already ships one. What matters more is knowing what you take off the shelf: both the speed and the question of whether your object will be found at all depend on it.

The reference implementation is HashMap. Inside it is exactly what this article described: an array of buckets and chaining — entries that land in one bucket lie in a linked list. The bucket number is not a remainder of a division but a cheap bit operation on the low bits of the hash: the array size is always a power of two. So that the high bits do not go to waste, HashMap first mixes them into the low ones — without that, keys sharing a hash "tail" would all pile into one bucket.

The default load factor is 0.75: as soon as entries outnumber three quarters of the buckets, the array doubles and every key is laid out anew. A rebuild costs O(n), so for a hundred thousand entries the size is set in the constructor up front — otherwise the table lives through fourteen rebuilds.

One more detail arrived in Java 8. If eight entries pile into one bucket while the table already has at least 64 buckets, the list inside that bucket turns into a red-black tree. The search inside an overloaded bucket goes from O(k) to O(log k) — insurance against a poor hash function and against deliberately crafted data that would otherwise degenerate the table into a list.

Hence the honest complexity. get and put are O(1) on average, provided the hash function spreads keys evenly. The worst case is not O(1) but O(log n) thanks to the tree in the bucket — and only if the keys are Comparable; otherwise HashMap orders them by a fallback and the gain is more modest. HashMap has no iteration order at all, and it may change after any resize — when insertion order matters, LinkedHashMap is taken, which additionally links the entries into a list. HashSet is the same HashMap with the values unused.

The trap people fall into most often: a key that changes after it has been put into the table. The bucket number was computed once, on insertion. Change a field that takes part in hashCode and the object stays in the old bucket, while the lookup now goes to the new one.

live example

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

public class MutableKey {
    static class Order {
        int id;
        Order(int id) { this.id = id; }
        @Override public int hashCode() { return Integer.hashCode(id); }
        @Override public boolean equals(Object o) { return o instanceof Order other && other.id == id; }
    }

    public static void main(String[] args) {
        Map<Order, String> orders = new HashMap<>();
        Order order = new Order(1);
        orders.put(order, "paid");
        System.out.println("right after put: " + orders.get(order));
        order.id = 2;
        System.out.println("after editing the key: " + orders.get(order));
    }
}

Hence the rule: keys of a hash table are made immutable, and hashCode and equals are overridden together and over the same fields. Let them diverge and two equal objects end up in different buckets (or, the other way round, become indistinguishable).

In short

• A hash table turns a key into an array index with a hash function: access in O(1) on average, faster than trees.
• Collisions are unavoidable; they are resolved by open addressing (find another free slot: linear or quadratic probing, double hashing) or by chaining (a list in every slot).
• The load factor decides when to grow the table: HashMap uses 0.75, beyond which the array doubles and all keys are laid out anew — O(n).
• A hash function must be fast and uniform. With a remainder the size is a prime number; in HashMap it is a power of two with the high bits mixed in.
• The price of speed — no order, useless without the exact key, and a memory reserve.
• Keys are made immutable, and hashCode and equals are overridden together over the same fields — otherwise the entry is lost in the old bucket.

What to read next

• Heaps — the structure that instantly hands over the largest element and backs a priority queue.
• Red-black trees — what you pay for the order a hash table has no notion of: TreeMap instead of HashMap.
• Linked lists — what the chains inside the buckets are made of.
• Choosing a data structure — when a table, when a tree, when a plain array.