Hash function

Hash functions are central to hash tables, where they map keys to array indices, enabling average-case constant-time insertions, deletions, and lookups. The quality of a hash function directly affects performance: a good hash distributes keys uniformly to minimize collisions, which are handled via chaining or open addressing. In data integrity, cryptographic hash functions like SHA-256 produce digests that detect accidental or malicious changes to data; even a single-bit alteration yields a completely different hash. They also underpin digital signatures and password storage, where hashing (often with salting) protects credentials. The concept originated in the 1950s with Hans Peter Luhn's work on IBM, and the term 'hash' was coined by Donald Knuth in his influential The Art of Computer Programming.¹

Hash functions fall into two broad categories: non-cryptographic and cryptographic. Non-cryptographic functions, such as MurmurHash and CityHash, prioritize speed and are used in hash tables and bloom filters, where collision resistance is not security-critical. Cryptographic hash functions, including SHA-2 and SHA-3, must satisfy additional properties: preimage resistance (given a hash, it is infeasible to find an input), second-preimage resistance (given an input, it is infeasible to find another input with the same hash), and collision resistance. Design considerations include avalanche effect (a small change in input causes a large change in output), computational efficiency, and resistance to length-extension attacks. The choice of hash function depends on the application's threat model and performance requirements.²

Beyond common uses, hash functions appear in surprising contexts. In load balancing, consistent hashing minimizes remapping when the number of servers changes, used in distributed systems like DynamoDB. In file deduplication, content-defined chunking uses rolling hashes (e.g., Rabin fingerprint) to identify duplicate data blocks. Hash functions also enable the hash-based message authentication code (HMAC), which combines a secret key with a hash to verify data authenticity. A niche application is in hash-based signatures, such as the Merkle signature scheme, which are considered quantum-resistant. Historically, the Cyclic Redundancy Check (CRC) is a non-cryptographic hash used for error detection in network protocols. Even in chess engines, Zobrist hashing represents board positions as hashes for efficient transposition tables.³

Cryptographic hash functions are not immune to attacks. Collision attacks, such as the 2017 SHAttered attack on SHA-1, demonstrated that theoretical weaknesses can be exploited in practice, leading to deprecation of SHA-1 in favor of SHA-2. The birthday paradox sets a fundamental limit: for a hash with n-bit output, collisions can be found in about 2^(n/2) operations, so a 128-bit hash provides only 64 bits of collision resistance. To mitigate this, modern functions like SHA-256 use 256-bit outputs. Additionally, length extension attacks affect certain hash constructions, prompting the design of SHA-3 with a sponge construction that resists such attacks. In password storage, unsalted hashes are vulnerable to rainbow table attacks, so salts and key derivation functions like bcrypt are recommended. These limitations drive continuous evolution in hash function design.⁴

Collision

When two distinct inputs produce the same hash output.

Avalanche effect

A property where a small change in input causes a drastically different output.

Preimage resistance

The difficulty of finding an input that hashes to a given output.

Salt

Random data added to a password before hashing to prevent rainbow table attacks.

Sponge construction

A framework used in SHA-3 that absorbs input and squeezes output, resistant to length extension.