How hash functions work

What does a hash function actually do?

A hash function takes a key, which might be a number, a word or an entire document, and returns a short value of fixed length. That output goes by several names: hash value, hash code, digest, or simply hash. The input can be any length; the output is always the same size.

The function has to be deterministic. Feed it the same input twice and it must produce the same hash both times. Otherwise a program could store something under one hash and later look for it under another. For that reason a hash cannot depend on the time of day, a random number drawn at each call, or where an object happens to sit in memory.

Inside, a typical hash function does three jobs. It folds a long key into a value the size of a machine word, often by repeatedly combining pieces with addition or exclusive-or. It scrambles the bits so that similar keys end up far apart. Then it scales the result down to fit the size of the table it will index.

How does hashing make lookups fast?

The main use of a hash function is to index a hash table, an array of numbered slots, sometimes called buckets. To store a value, the program hashes its key and puts the entry in the slot the hash points to. To find it later, the program hashes the same key and looks directly in that slot.

This is why hash tables are so widely used. Searching an unsorted list means checking items one by one, and even a balanced tree needs several comparisons. A well-sized hash table, on average, needs roughly the same small amount of work regardless of how many entries it holds. Many programming languages ship one as a built-in, from the dictionary in Python to the map type in Go.

Hashing is a trade between time and memory. With unlimited memory, every possible key could have its own slot, which would be very fast but enormously wasteful. With unlimited time, everything could sit in one compact list and be searched slowly. A hash function lands between the two: modest storage, quick access.

What happens when two keys get the same hash?

Because there are far more possible keys than slots, two different keys will sometimes hash to the same place. This is a collision, and it cannot be avoided completely. Even when the table is much larger than the number of entries, a few collisions are virtually certain, for the same reason that a small group of people often contains two who share a birthday.

Hash tables therefore need a collision-resolution method. In separate chaining, each slot holds a short list, and colliding items are added to it. In open addressing, a newcomer that finds its slot taken probes onward, by linear probing, quadratic probing or double hashing, until it finds an empty one. Lookups follow the same path.

How full the table is matters a great deal. This fullness, the load factor, is the number of stored items divided by the number of slots. Open addressing degrades badly as the table approaches full, so such tables are usually enlarged when the ratio reaches somewhere around 0.6 to 0.75. Chained tables slow down more gradually.

What does a small example look like?

Imagine a table with ten slots and a simple hash that adds up the alphabet positions of a word's letters and keeps the last digit. The word "cab" scores 3 plus 1 plus 2, which is 6, so it goes in slot 6. Looking it up later repeats the sum and goes straight to slot 6, with no searching.

Now store "bad": 2 plus 1 plus 4 is 7, slot 7. But "abc" also sums to 6 and collides with "cab". With chaining, slot 6 simply holds both words, and a lookup checks the short list there. The toy also shows why this particular hash is poor: any rearrangement of the same letters always collides, so real hash functions scramble bits far more thoroughly.

What makes a hash function good or bad?

A good hash function is fast and spreads the inputs it will actually meet as evenly as possible across its outputs. Evenness matters because the cost of a hash table rises sharply as collisions pile up in a few slots. Designers test this with statistical checks such as the chi-squared test, and look for the strict avalanche criterion: flipping a single input bit should change each output bit with even odds.

Things go wrong when the table is too full, when the key set is unusually patterned, or when the function is poorly designed. In those cases lookups can slow until they take time proportional to the number of items, no better than a plain list. When every key is known in advance and never changes, a perfect hash with no collisions at all can sometimes be built, but finding one for more than a small set is usually impractical.

Hash functions also do security work. Cryptographic hash functions are designed so that tiny input changes produce unrecognisably different outputs. They are used to detect altered files, to derive keys, to build message authentication codes, to sign a short digest instead of a whole message, and to store passwords as hashes rather than in readable form.

What does it teach about thinking?

Hashing is a reminder that clever organisation can beat brute effort. Instead of looking everywhere, decide in advance where each thing belongs, and the search almost disappears.

It also shows that good design plans for failure. Collisions are guaranteed, so a sound system does not pretend they will not happen; it chooses a cheap, predictable way to deal with them and keeps the load low enough that they stay rare.

Questions people ask

The thinking behind it

• margin of safety
• redundancy
• bottleneck

More algorithms, explained

• How backpropagation works
• How decision tree learning works
• How k-means clustering works
• How tf–idf works: weighing words by how much they tell you