What is a hash function? Explained with an interactive hash table

What is a hash function?

A hash function $h$ maps keys from a large, often unbounded, set $U$ to a small fixed range of values:

For a hash table, $m$ is the number of buckets, perhaps a few thousand. For a general-purpose hash it is a power of two such as $2^{32}$ or $2^{64}$, and the result is reduced modulo the table size afterwards. The word “hash” comes from chopping and mixing: a good hash function chops the key into pieces and mixes them so thoroughly that the result looks random, even though it is completely determined by the key.

Take the key "hello". The polynomial hash used by Java’s String.hashCode gives 99162322; the 32-bit FNV-1a hash gives 0x4f9f2cab. In a table of 16 buckets these land in buckets 2 and 11. Try your own keys:

What makes a hash function good

• Deterministic. The same key always gives the same hash. Without this, you could never find a key again after storing it.
• Uniform. Keys should spread evenly over the $m$ buckets, so no bucket is crowded while others sit empty. Real keys are anything but random (names share prefixes, IDs are consecutive, prices end in 99), so the function has to break up these patterns.
• Fast. A hash table is only fast if the hash is. Good non-cryptographic hashes process several bytes per CPU cycle.
• Avalanche. Changing one bit of the key should change about half the bits of the hash, in an unpredictable pattern. The playground measures this: change the last letter of a key and count the bits that flip. The character-sum hash fails badly, the polynomial hash only disturbs a few low bits, and FNV-1a and SHA-256 flip about half.

Notice what is not required: a hash does not have to be reversible, and different keys are allowed to have the same hash. That second point is unavoidable, as the next section shows.

Simple hash functions

The division method

For an integer key, $h(k) = k \bmod m$. It is a single instruction, but the choice of $m$ matters. If $m = 2^p$, the hash is just the lowest $p$ bits of the key, so keys that differ only in their high bits always collide. A prime $m$ not close to a power of two works much better. For example, $1234 \bmod 11 = 2$.

The multiplication method

Multiply the key by a constant $0 < A < 1$, keep the fractional part, and scale it to the table: $h(k) = \lfloor m \cdot (kA \bmod 1) \rfloor$. Here the choice of $m$ no longer matters, so powers of two are fine. Knuth suggests $A = (\sqrt{5} - 1)/2 \approx 0.618$, which spreads consecutive keys out well; with $m = 10{,}000$, the key 123456 lands in bucket 41. Real implementations do the same thing in integer arithmetic, with a multiply and a shift (“Fibonacci hashing”).

Polynomial string hashing

Treat the characters of a string $s_0 s_1 \dots s_{n-1}$ as digits in base $b$:

Computed with Horner’s rule, $h \leftarrow h \cdot b + s_i$, it costs one multiply and one add per character. Unlike simply adding the characters, it depends on their order, so “stop”, “pots” and “tops” get different hashes. It is also rolling: the hash of a sliding window can be updated in constant time when one character leaves and another arrives, which is the trick behind the Rabin–Karp string-search algorithm.

FNV-1a

FNV-1a processes one byte at a time: XOR the byte into the hash, then multiply by a fixed prime. For 32 bits, start from 0x811c9dc5 and multiply by 16777619 (0x01000193) each time, all modulo $2^{32}$. The multiplication spreads each byte’s influence into the higher bits, which is why its avalanche behaviour is much better than the polynomial hash’s. It is short, fast on small keys, and widely used inside compilers, databases and DNS servers. For long keys, modern hashes such as xxHash and SipHash process several bytes at once.

Collisions are unavoidable

A collision is two different keys with the same hash. When there are more possible keys than hash values, collisions must exist: this is the pigeonhole principle. There are infinitely many strings and only $2^{32}$ 32-bit hashes, so infinitely many strings share each one.

Collisions also come much sooner than intuition suggests. Put $n$ keys into $m$ buckets at random. The chance that they all land in different buckets is

This is the birthday problem: with $m = 365$, only 23 people are needed for a 50.7% chance that two share a birthday, and with 50 people the chance is 97%. In general a collision becomes likely once $n$ reaches about $\sqrt{m}$. For a 32-bit hash that is just 77,164 keys for even odds, which is why 32-bit hashes are fine for tables but useless as unique identifiers, and why cryptographic hashes use 256 bits.

Hash tables: chaining and open addressing

A hash table stores each key in the bucket its hash points to, so finding a key takes one hash computation and a look in one place, rather than a search through everything. Since collisions will happen, every hash table needs a strategy for them:

• Separate chaining keeps a short list in each bucket. A collision simply adds the key to the list. Lookups scan one list, whose expected length is the load factor $\alpha = n/m$.
• Open addressing stores every key in the array itself. When the home slot is taken, it probes other slots in a fixed sequence until it finds a free one. Linear probing tries the next slot, then the next. Quadratic probing jumps by growing offsets (here 1, 3, 6, 10, … slots from home). Double hashing moves in steps whose size comes from a second hash of the key.

Fill the table below and switch strategies: the same keys are re-inserted each time. “Add keys that clash” adds numbers with the same remainder modulo $m$, the worst case for any table.

How full can a table get?

Under the assumption that the hash is uniform, the expected number of probes depends only on the load factor $\alpha$. For a lookup of a key that is not present:

Chaining degrades gently and can even run above $\alpha = 1$. Open addressing gets slow as the table fills, linear probing fastest of all, so real implementations resize: when $\alpha$ passes a threshold (often 0.75 for chaining, 0.5–0.875 for open addressing), allocate a table about twice the size and re-insert every key. A single resize costs $O(n)$, but because the size doubles, the cost averaged over all insertions is still $O(1)$. Linear probing remains popular anyway: probing neighbouring slots is very cache-friendly, which often outweighs the extra probes.

Note the word expected. If many keys share a hash, every operation degrades to $O(n)$. Attackers can exploit this by sending keys chosen to collide, so web servers and language runtimes use a seeded hash such as SipHash, whose secret random seed makes collisions impossible to predict from outside.

Cryptographic hash functions

A cryptographic hash function such as SHA-256 has to survive a deliberate attacker, not just ordinary data. It must be:

• preimage-resistant: given a hash, it is infeasible to find any input that produces it;
• second-preimage-resistant: given one input, it is infeasible to find a different input with the same hash;
• collision-resistant: it is infeasible to find any two inputs with the same hash.

Collisions still exist, by the pigeonhole principle, but with 256 output bits the birthday bound puts a generic search at around $2^{128}$ evaluations, far beyond any computer. That makes the hash usable as a fingerprint: to check that a downloaded file is intact, compare its SHA-256 with the published one. Cryptographic hashes are also the basis of digital signatures, Git commit IDs and blockchains. MD5 and SHA-1 are now broken in this sense: practical collisions have been found, so they must not be used where an attacker could choose the input.

The price is speed. SHA-256 is many times slower than FNV-1a or xxHash, so hash tables use a fast non-cryptographic hash, and security-sensitive code uses a cryptographic one.

Where hash functions are used

• Dictionaries and sets in almost every language (Python’s dict, Java’s HashMap, C++’s unordered_map) are hash tables.
• Deduplication and caching: hash each item and compare the hashes before comparing whole items.
• Checksums: CRCs catch accidental corruption in network packets and archives; cryptographic hashes also catch deliberate tampering.
• Probabilistic data structures: Bloom filters test set membership in a few bits per item, and HyperLogLog counts distinct items in a few kilobytes, both by hashing.
• Distributed systems: consistent hashing decides which server stores which key, so that adding a server moves only a small fraction of the keys.

Hashing turns up in other algorithms on this site too. A Big-O analysis of a hash table’s $O(1)$ operations is an expected bound over the hash’s randomness, unlike binary search’s guaranteed $O(\log n)$. And Dijkstra’s algorithm typically keeps its distances in a hash map keyed by vertex.

References

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022. Chapter 11, “Hash tables”.
2. D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998. Section 6.4.
3. J. L. Carter and M. N. Wegman, “Universal classes of hash functions”, Journal of Computer and System Sciences 18(2), 1979. doi:10.1016/0022-0000(79)90044-8
4. “Fowler–Noll–Vo hash function”, Wikipedia.