Hashing
Noun · Verb · Development
Definitions
Hashing is the process of transforming input data of any size into a fixed-size output (called a hash, digest, or fingerprint) using a mathematical function called a hash function. Good hash functions are deterministic (same input always produces the same output), fast to compute, and produce outputs that appear random with minimal collisions (different inputs producing the same hash). Hashing has diverse applications across computing. Hash tables use hashing for O(1) average-case lookups, insertions, and deletions, making them one of the most important data structures. Cryptographic hash functions (SHA-256, bcrypt, Argon2) are used for password storage, digital signatures, and data integrity verification, with additional properties like pre-image resistance (infeasible to reverse) and avalanche effect (small input changes produce dramatically different outputs). Git uses SHA hashes to identify every commit, tree, and blob. Checksums verify file integrity during downloads. Bloom filters use multiple hash functions for probabilistic set membership testing. Consistent hashing distributes data across servers in distributed systems.
In plain English: Turning data into a fixed-length fingerprint that's easy to compute but practically impossible to reverse — used to verify data hasn't been tampered with or to store passwords safely.
Example: "We hash passwords with bcrypt — never, ever store them in plaintext."
Etymology
- 1953
- Hans Peter Luhn at IBM filed a patent for a hash table using chaining, establishing hashing as a fundamental technique for fast data retrieval.
- 1970s
- Hash functions became standard in databases, compilers (symbol tables), and operating systems. Linear probing and open addressing provided alternatives to chaining.
- 1990s
- Cryptographic hashing emerged as distinct from data-structure hashing. MD5 (1991) and SHA-1 (1995) became standard for integrity verification, digital signatures, and password storage.
- 2000s-Present
- SHA-256 replaced weakened predecessors. Consistent hashing enabled distributed systems (Dynamo, Cassandra). Password hashing evolved to bcrypt, scrypt, and Argon2 to resist brute-force attacks.
Origin Story
Turning Data into Digital Fingerprints
Hashing is the process of transforming input data of arbitrary size into a fixed-size output (a hash value or digest) using a mathematical function. The concept has roots stretching back to the 1950s, when IBM researcher Hans Peter Luhn developed hash-based lookup tables for information retrieval. Luhn's 1953 internal IBM memorandum described using a hash function to map keys to storage addresses, creating what would become the hash table, one of the most fundamental data structures in computing. The idea was further developed by Wesley Peterson, who published a paper on hash functions for symbol tables in 1957. As computing matured, hashing found applications far beyond simple lookups: cryptographic hash functions like MD5 (1992, Ronald Rivest) and SHA-1 (1995, NSA) enabled digital signatures, password storage, and data integrity verification. Today, hashing is everywhere. Git uses SHA hashes to identify every commit. Blockchains chain together cryptographic hashes. Password systems store salted hashes instead of plaintext. Load balancers use consistent hashing to distribute traffic. The simplicity of the core idea, converting data to a compact fingerprint, belies its extraordinary versatility.
Coined by: Hans Peter Luhn
Context: Luhn described hash-based lookup methods in a 1953 IBM memorandum on information retrieval.
Fun fact: In 2017, Google and CWI Amsterdam demonstrated the first practical SHA-1 collision, producing two different PDF files with the same SHA-1 hash. The computation required 6,500 years of CPU time and 110 years of GPU time, executed in parallel over several months.