A hash function is a function that maps input data to values in a specified output space, commonly a fixed-length sequence of bits or an integer within a bounded range. Its output is called a hash value, hash code, or, particularly in cryptographic contexts, a digest. Hash functions turn potentially large or complicated objects—such as strings, files, and database records—into values that are easier to index, distribute, or compare. Because different inputs can produce the same output, a hash generally serves as a compact representative of data rather than a unique description of it.
Hash functions underpin hash tables, many database operations, file-integrity checks, distributed storage, and modern cryptography. Their requirements differ sharply by application. A hash used for fast lookup should distribute ordinary keys effectively and be inexpensive to compute; a cryptographic hash must also withstand deliberate attempts to find particular inputs or matching outputs. Other specialized designs preserve aspects of similarity, minimize reassignment when servers change, or deliberately require substantial computational resources. Understanding these distinctions is essential: functions that look similar at their interfaces can provide fundamentally different guarantees.
Mathematical model and collisions
A conventional hash function can be written as
where is the universe of possible inputs and is the number of possible outputs. A function producing an -bit digest instead has an output space of size . Some functions accept only bounded-length inputs, whereas others are specified over all finite bit strings or over strings up to a very large implementation limit. Extendable-output functions allow the caller to request a chosen number of output bits rather than fixing one digest length.
A collision occurs when two distinct inputs and satisfy . If the input space contains more than elements, collisions necessarily exist by the pigeonhole principle. No mixing procedure, secret seed, or cryptographic construction can eliminate this mathematical fact. What a design can control is how frequently collisions occur for relevant inputs, how difficult they are to find deliberately, and how an application responds when one occurs.
Collision probabilities depend on the experiment being considered. Suppose distinct inputs receive independent, uniformly distributed -bit hash values. A new input matches one specified target digest with probability . By contrast, among hashed inputs, there are pairs that might collide. The probability of at least one collision is approximately
This is the birthday effect: the probability becomes substantial after roughly inputs, far fewer than the possibilities needed to exhaust the output space. For a 64-bit output, that scale is around inputs; for a 256-bit output, it is around .
These estimates describe an idealized distribution, not an automatic property of every hash. A function returning the first eight bytes of a record may appear uniform on one dataset and collide catastrophically on another. Even a well-designed function can perform poorly if only weakly mixed output bits are used to select a bucket. Statistical behavior must therefore be considered together with the input distribution and the way outputs are consumed.
A hash is deterministic once its algorithm and parameters are fixed: identical encoded inputs produce identical outputs. Randomization usually means selecting a function from a family using a seed or key, not producing an unrelated value on every call. This distinction permits reproducible lookup while making the mapping less predictable to an adversary.
Hash tables and exact lookup
A hash table is a data structure that uses a hash value to locate a key or a small set of candidate positions. A dictionary mapping account names to records, for example, may compute a hash of a name and reduce it to a bucket index. The table then examines the relevant bucket rather than searching all stored names. Hashing supports sets, associative arrays, compiler symbol tables, caches, and hash-based joins in a database management system.
Collisions are handled by the table, not prevented by the hash function. In separate chaining, a bucket contains a collection of entries sharing its index. In open addressing, entries occupy positions in an array, and a collision triggers a probe sequence to find another position. Linear probing checks successive locations; quadratic probing and double hashing use different sequences. More specialized designs, including cuckoo hashing, permit a key to occupy one of several candidate positions and may relocate existing entries during insertion.
The load factor is commonly written
where is the number of entries and the number of buckets or slots. Under suitable distribution assumptions, separate chaining supports expected lookup time proportional to , excluding the cost of hashing and comparing keys. Open-addressed tables require unused space, and their probe counts generally increase as occupancy approaches capacity. Resizing and rehashing keep the load within a chosen range, although an individual resize can take linear time. Consequently, insertion guarantees are often amortized rather than worst-case constant time.
An exact dictionary must distinguish a hash match from a key match. Two unequal strings can have the same hash, so the implementation normally compares the original keys before reporting equality. Hashing a long string also requires reading it unless a previously computed hash is available. Thus, “constant-time lookup” usually refers to expected table operations under a model in which hash calculation and key comparison are treated separately; it does not mean that processing an arbitrarily long key takes constant time.
Language-level equality introduces another constraint: keys considered equal must have equal hashes. If equality ignores letter case or treats differently represented numbers as equal, the hashing rules must respect that equivalence. A key whose equality-relevant contents change after insertion may become unreachable in its original bucket. Object identity hashes, value hashes, and persistent content digests therefore serve different purposes.
If an attacker can choose many keys with the same bucket index, a table can degrade toward linear scans and become a vehicle for a denial-of-service attack. Secretly keyed hashing, randomized table parameters, collision-resistant fallback structures, and limits on resource consumption address different parts of this problem.
Fast hashing, randomization, and perfect hashing
Noncryptographic hash functions prioritize speed and useful statistical distribution rather than resistance to all deliberate attacks. Typical operations include integer multiplication, exclusive-or, addition, shifts, and bit rotations. These operations mix information from different input positions into the output while mapping efficiently onto processor instructions. MurmurHash, xxHash, and members of the CityHash and FarmHash families are examples of designs used in software systems, although their variants differ in output width, platform assumptions, and intended workloads.
A desirable empirical property is the avalanche effect: changing a small part of the input changes many output bits. Under the strict avalanche criterion, complementing any single input bit changes each output bit with probability one half, with probability taken over inputs. This is a useful way to identify poor mixing, but it is not a proof of security or even a complete characterization of hash-table performance. A function can pass extensive statistical tests while retaining algebraic structure that permits efficient collision construction.
Universal hashing gives a more explicit probabilistic guarantee. Instead of fixing one function, an algorithm selects randomly from a family . A common universality condition requires that, for any distinct fixed keys and ,
The probability is over the function selection, not over an assumption that the keys themselves are random. Carter and Wegman introduced this approach in 1979, connecting hash-table analysis with randomized algorithms. Stronger independence conditions support additional guarantees, but the independence needed depends on the table organization and the operation being analyzed.
Simple constructions include arithmetic over a prime field and multiply-shift schemes over machine words. An illustrative family takes an integer key , computes for a prime , and then maps the result to a bucket range. Exact bounds depend on the parameter choices and final range reduction. These mathematical families are distinct from cryptographic pseudorandom functions: a collision bound for fixed keys does not automatically establish security against an adaptive adversary who learns information about a chosen function.
Perfect hashing takes another approach. For a particular fixed set of keys, a perfect hash assigns distinct outputs to every key in that set. A minimal perfect hash uses exactly as many output positions as there are keys. This does not contradict the inevitability of collisions over a larger universe: the collision-free guarantee applies only to the designated set. Such functions are useful for static dictionaries and compact indexes, but they do not by themselves establish that an arbitrary query belongs to the set. Membership verification requires additional stored information.
A rolling hash supports efficient updates when a fixed-size window moves through a sequence. Polynomial fingerprints can remove the contribution of an outgoing character and incorporate an incoming one without hashing the whole window again. This property supports substring search and some chunking algorithms, but it also exposes algebraic relationships that are generally unsuitable for cryptographic protection.
Cryptographic security properties
A cryptographic hash function is designed to remain useful even when an adversary chooses inputs and knows the algorithm. Three central properties are usually distinguished. Preimage resistance means that, given a target digest , finding an input such that should be computationally infeasible. Second-preimage resistance means that, given a particular input , finding a distinct with the same digest should be infeasible. Collision resistance means that finding any pair of distinct inputs with equal digests should be infeasible.
These are different tasks. A collision attack lets the attacker choose both messages, whereas a second-preimage attack begins with an already fixed message. Breaking collision resistance does not necessarily provide an efficient preimage attack. For an ideal -bit hash, generic classical search requires work on the order of evaluations for a preimage and evaluations for a collision. Actual security can be lower because of structural weaknesses, restrictions on the input space, or properties of the surrounding protocol.
Collision resistance matters especially when a digest stands in for a document in a digital signature. If an attacker can prepare two differently interpreted documents with the same digest, a signature obtained on one may also verify against the other, depending on the signature construction and document format. A chosen-prefix collision is particularly powerful: the attacker begins with two selected prefixes and constructs suffixes that make the complete messages collide. This is more relevant to document substitution than an arbitrary collision between meaningless strings.
Cryptographic hashes are often compared to the random oracle model, in which a public function assigns independent random outputs to previously unseen inputs while remaining consistent on repeated queries. This model is useful for analyzing protocols, but a real hash is a finite algorithm with internal structure. Security proved in the random oracle model does not mean that every concrete replacement automatically inherits the proof.
Cryptographic hashing is not encryption. A hash has no general decryption operation, and a short digest cannot preserve all the information in a long input. Nevertheless, hashing does not guarantee confidentiality. If the input comes from a small set—such as a short access code or a list of common names—an attacker can hash every candidate and compare the results. Preimage resistance is meaningful only in relation to the available input uncertainty and computational resources.
An unkeyed digest also does not establish who created a message. Anyone who can replace a file may be able to replace its accompanying digest. Integrity against an active attacker requires an independently trusted digest, a signature, or a keyed authentication mechanism. The distinction between detecting accidental change and authenticating adversarially supplied data is fundamental to a sound threat model.
Cryptographic constructions and standards
Many cryptographic hashes process long inputs by maintaining a fixed-size internal state. The message is padded, divided into blocks, and combined with the state through repeated transformations. The Merkle–Damgård construction, developed in work by Ralph Merkle and Ivan Damgård in 1989, provides a framework for extending a fixed-input-length compression function into a variable-length hash. Under appropriate conditions, collision resistance of the compression function carries over to the iterated hash.
MD5, designed by Ronald Rivest and published in 1992, produces a 128-bit digest. SHA-1, standardized in 1995, produces 160 bits. Both use iterated designs but are no longer considered collision resistant. Practical MD5 collision attacks were published in 2004, and a public collision for full SHA-1 was demonstrated in 2017. These results illustrate why a digest’s length is only an upper limit on its potential security: cryptanalysis can exploit a construction more efficiently than generic birthday search.
The SHA-2 family includes SHA-224, SHA-256, SHA-384, and SHA-512, as well as specified SHA-512 variants. SHA-256 processes 512-bit message blocks using a 256-bit chaining state; SHA-512 uses 1,024-bit blocks and a 512-bit state. Their compression functions combine message expansion with rounds of Boolean operations, modular addition, and rotations. Output length alone does not determine speed: 64-bit arithmetic can make SHA-512 efficient on some 64-bit processors, while specialized instructions can greatly accelerate particular SHA-2 variants.
SHA-3 follows a different design. In 2012, the United States National Institute of Standards and Technology selected Keccak, designed by Guido Bertoni, Joan Daemen, Michaël Peeters, and Gilles Van Assche, as the winner of its hash competition. SHA-3 was standardized in 2015. Its sponge construction absorbs message blocks into an internal state and then squeezes output from that state. The state is divided conceptually into a rate, which controls input and output processing, and a capacity, which is central to security bounds. SHAKE128 and SHAKE256 provide extendable output within the same standard.
These structural differences affect protocol behavior. Straightforward use of several Merkle–Damgård hashes exposes a length-extension property: from a digest and the original message length, an attacker can compute the digest of certain extended messages without knowing the original contents. This does not recover the message or constitute a collision, but it can break constructions such as a naïve hash of a secret prefix followed by a message. SHA-3’s standardized interface does not expose the same extension mechanism.
Other modern designs emphasize keyed operation, software speed, or parallelism. BLAKE2 was published in 2012 and provides keyed hashing as part of its design. BLAKE3, introduced in 2020, uses a tree structure that supports parallel processing. Different standards and libraries expose different combinations of ordinary hashing, keyed hashing, and derived-key modes; these modes are not interchangeable merely because they share an underlying primitive.
Authentication, key derivation, and password hashing
A message authentication code combines a secret key with a message to produce a tag. A recipient holding the key can verify that the message is consistent with one produced by a key holder. Unlike a public digest, the tag cannot ordinarily be recomputed by an outsider after modifying the message. Unlike a public-key signature, however, a shared-key tag does not distinguish which holder of the secret generated it.
HMAC, standardized in 1997, constructs such a code from a cryptographic hash. Its structure is commonly written
where is the key normalized to the hash’s block size, and are fixed padding values, and denotes concatenation. The nested keyed construction avoids the weaknesses of simply computing . Its security analysis also differs from the collision-resistance analysis of the underlying unkeyed hash; an attack on one property does not automatically break every keyed use.
Hash-based key derivation functions transform secret material into keys suited to particular uses. HKDF, specified in 2010, uses HMAC in an extract-then-expand structure. Extraction concentrates suitable input keying material into a pseudorandom key; expansion produces application-specific output using context information. Distinct context labels can separate keys for encryption, authentication, and different protocol stages. Such separation prevents one byte sequence from inadvertently serving several incompatible cryptographic roles.
Password hashing addresses a different problem. Human-selected passwords often have too little uncertainty to resist exhaustive guessing after a credential database is stolen. A fast general-purpose hash permits an attacker to test many candidates rapidly. Specialized schemes therefore add configurable computational cost, and some impose substantial memory requirements as well. PBKDF2 repeatedly applies a pseudorandom function; bcrypt builds on the Blowfish key schedule; scrypt and Argon2 incorporate memory-intensive computation. Argon2 won the Password Hashing Competition in 2015.
A password record normally includes a salt: a nonsecret value selected separately for each password instance. Salts make equal passwords produce different stored values and prevent a single precomputed table from being reused unchanged across many records. They do not make an individual weak password unguessable. A separately protected secret, sometimes called a pepper, has a different role and introduces its own key-management requirements.
Deliberate slowness is therefore an asset in password hashing but a liability in ordinary hash-table lookup. Memory hardness similarly aims to alter the economics of large-scale guessing, not to improve the statistical uniformity of bucket assignment. Security depends on the complete scheme—parameters, secret handling, password uncertainty, and implementation—not simply on whether a function is described as a hash.
Content addressing, integrity, and Merkle structures
In content-addressable storage, an object is located or identified by a digest of its encoded contents rather than solely by a name or physical address. Identical content naturally receives the same identifier, enabling deduplication and cache reuse. A changed object receives a different identifier with overwhelming probability when an appropriate cryptographic hash is used. Storage systems must still define how collisions are handled and whether full content is compared before data is merged or discarded.
A Merkle tree extends this idea to collections. Leaves represent data blocks or their hashes, and internal nodes contain hashes derived from their children. The root digest commits to the entire structure. To demonstrate that a leaf occurs in a balanced binary tree of leaves, a prover supplies the sibling hashes along its path to the root, requiring hashes rather than transmitting the complete dataset. Verification recomputes the path and compares the resulting root with a trusted value.
The encoding of a tree is security-relevant. Leaf data and internal-node data need distinguishable representations, and child order and lengths must be unambiguous. Otherwise, different structural interpretations can produce the same byte sequence even without a cryptographic collision. Domain separation—such as assigning distinct prefixes to leaf and internal-node hashes—addresses this class of ambiguity. A Merkle root authenticates data only relative to the encoding rules and the authority through which the root itself is trusted.
Git uses content-derived object identifiers for blobs, trees, commits, and annotated tags. An object’s hashed representation includes a header identifying its type and size, not just its visible payload. Trees refer to other objects, and commits refer to trees and parent commits, producing a graph in which changing an earlier object affects identifiers that depend on it. Git’s historical use of SHA-1 and its support for SHA-256 repositories also illustrate the complexity of changing a hash embedded throughout a persistent format and ecosystem.
Hashing also supports file verification, backup deduplication, and reproducible artifacts. A published digest can reveal whether a downloaded file differs from an expected byte sequence, but only if that expected digest has a trustworthy origin. A checksum supplied by the same compromised source as a file offers no independent authenticity. Digital signatures and authenticated release channels provide a different level of assurance.
Not every error-detection mechanism is a cryptographic hash. A cyclic redundancy check detects important classes of transmission and storage errors through polynomial arithmetic. Its linear structure also makes deliberate modification easy to accommodate when an attacker can change both data and check value. CRCs, cryptographic digests, and error-correcting codes solve related but distinct problems: detecting accidental damage, resisting adversarial substitution, and recovering information from specified error patterns.
Distributed placement, probabilistic structures, and similarity
Hashing helps distributed systems decide where data belongs. The simple assignment , where is the number of servers, spreads keys across a fixed set of destinations. Changing , however, can move a large fraction of keys. This is expensive when movement means transferring stored objects or invalidating caches.
Consistent hashing, introduced in 1997, limits this disruption by mapping keys and server positions into a common space. In a ring-based design, a key is assigned to an appropriate successor server position. Adding a server changes ownership of only part of the space rather than remapping nearly everything. Multiple virtual positions per server improve balance and can represent different capacities. Rendezvous hashing instead scores each key–server pair and selects the server with the highest score, achieving a related stability property through a different mechanism.
Placement balance is not the same as workload balance. Uniformly distributing a million keys does not prevent one exceptionally popular key from overwhelming its assigned server. Replication, request routing, caching, and load-aware migration remain separate concerns. Adversarially chosen keys can also undermine predictable placement schemes, making secret parameters or other protective mechanisms relevant.
Probabilistic data structures use hashes to trade exactness for compactness. A Bloom filter stores a set approximately by setting positions in an -bit array for each inserted element. A query is reported absent if any corresponding bit is zero and possibly present if all are one. Under the idealized model, after insertions its false-positive probability is approximately
The conventional insertion-only design has no false negatives for inserted items, assuming correct operation. Its approximate optimal number of hash positions is . Other sketches use hash-derived counters or bit patterns to estimate frequencies and distinct counts.
Similarity-oriented hashing deliberately departs from cryptographic behavior. Locality-sensitive hashing uses families in which similar objects are more likely to collide than dissimilar ones under a specified distance measure. MinHash, for example, supports estimation of the Jaccard similarity of sets by comparing minimum values under random orderings or suitable hash-based approximations. Such methods support near-duplicate detection and approximate nearest-neighbor search in information retrieval.
This is almost the opposite of the avalanche objective. A cryptographic digest should conceal useful relationships between nearby inputs, while a similarity signature must retain selected relationships. Perceptual hashes for images and audio likewise aim to tolerate particular transformations. Their behavior depends on feature extraction and the intended similarity model; they are not substitutes for cryptographic verification of exact bytes.
Representation, implementation, and security limits
A hash operates on an encoding, not directly on an abstract meaning. Two visually identical strings can have different Unicode representations, and two equivalent structured objects can have different serialized byte sequences. A protocol that needs stable content identifiers must specify encoding, field ordering, numerical representation, and any normalization rules. Normalization is not always appropriate: distinctions that are irrelevant to one application may be meaningful to another.
Concatenation is a common source of ambiguity. Hashing the unframed pair of strings ab and c processes the same bytes as hashing a and bc. This is not a collision in the hash function because the actual byte input is identical. Length prefixes, typed encodings, or other unambiguous framing are needed when component boundaries matter. Domain separation similarly distinguishes otherwise overlapping uses, such as hashing a public key, a protocol transcript, and a tree node.
Output representation introduces further choices. A 256-bit digest occupies 32 bytes in binary or 64 characters in hexadecimal. Truncating a cryptographic digest to bits reduces generic collision security to roughly bits and generic preimage security to roughly bits, subject to the underlying function and attack setting. Short fingerprints can still be effective when occasional matches are checked against original data, but they provide different guarantees from a full security-sensitive digest. Persistent formats must also specify byte order and algorithm identifiers rather than relying on platform-specific integer hashes.
Performance depends on message length, processor features, and memory access. Hashing many short keys may be dominated by initialization and dispatch costs; hashing large files may be limited by storage or memory bandwidth. Hardware acceleration, vector instructions, and parallel processing can change relative performance substantially. A function optimized for contiguous buffers may not be optimal for streaming data or fragmented records. Benchmark results therefore describe workloads and implementations, not an intrinsic speed ordering valid everywhere.
Implementation security includes more than the compression algorithm. Keyed hashes must protect secret keys, avoid unintended information leakage, and compare authentication tags without revealing matching prefixes through timing. Persistent data structures require migration procedures when algorithms change. Statistical test suites can expose weak distribution, but cannot establish cryptographic security; conversely, a secure cryptographic hash may be unnecessarily costly for a nonadversarial in-memory index.
Quantum algorithms change theoretical search bounds. Grover’s algorithm gives an idealized square-root reduction for unstructured preimage search, while quantum collision algorithms have different complexity and resource requirements. These are not equivalent attacks, and practical costs depend on reversible circuits, memory, error correction, and available hardware. Hash-based signature schemes are an important branch of post-quantum cryptography because they can derive security from carefully specified hash properties rather than the integer-factorization or discrete-logarithm assumptions threatened by large-scale quantum computation.