Hashing
A hash function maps arbitrary data to a fixed-size integer; good hashing spreads inputs uniformly and underlies tables, caches, and fingerprints.
Data to a fixed-size number
A hash function takes an input of any size and returns an integer in a fixed range. The same input always produces the same output, and good hash functions scatter different inputs across the output range as evenly as possible. This mapping is the foundation of hash tables, content fingerprinting, and load balancing.
What makes a hash good
For general-purpose use a hash should be fast to compute, deterministic, and produce a near-uniform spread so that similar inputs do not cluster. The avalanche property is desirable: flipping one input bit should flip about half the output bits, so tiny input changes give unrelated outputs. Weak hashing that clusters keys degrades every table operation toward its linear worst case.
- Deterministic: same input, same output
- Uniform: outputs spread evenly across the range
- Fast: computable in time linear in the input size
- Avalanche: small input change, large output change
Collisions are unavoidable
Since the input space is larger than the output range, distinct inputs must sometimes share a hash, a collision. The birthday paradox means collisions appear surprisingly early. Data structures handle them with chaining or probing; the goal of a good hash is to make collisions rare and evenly distributed, not to eliminate them.
Families of hashing
Non-cryptographic hashes prioritise speed for tables and checksums. Cryptographic hashes add the property that finding two inputs with the same output, or reversing the hash, is computationally infeasible, which is what makes them suitable for integrity checks and digital signatures. A separate idea, consistent hashing, minimises how many keys move when the number of buckets changes, which is essential for distributed caches and sharded storage.