A hash table is a data structure that stores keys, or key–value pairs, by using a hash function to determine where entries belong in an array. It commonly implements an associative collection: given a key such as a name, identifier, or network address, a program can retrieve the corresponding value without searching every stored entry. Because different keys can map to the same position, a hash table also requires a method for resolving these collisions.
Hash tables are important because lookup, insertion, and deletion can take expected constant time under appropriate assumptions about hashing and table occupancy. These guarantees are not unconditional: poor hash distributions, excessive occupancy, costly key comparisons, or adversarial inputs can substantially increase the work required. Practical designs therefore combine hashing with collision resolution, capacity management, and safeguards appropriate to their operating environment.
Hash tables underpin language dictionaries, sets, database operations, caches, and many other software components. Their design connects mathematical analysis with memory layout, programming-language semantics, concurrent access, and security. Different implementations trade memory consumption, predictability, ordering, and implementation complexity against average speed.
Keys, values, and the dictionary abstraction
The abstract interface most commonly implemented by a hash table is an associative array, also called a map or dictionary. Its basic operations are to associate a value with a key, retrieve the value associated with a key, and remove an association. A set can use essentially the same machinery while storing only keys. In a conventional map, inserting a key that is already present replaces or updates its value; a multimap instead permits multiple associations for an equivalent key.
A hash table is an implementation technique, not the abstract interface itself. An associative array can also be implemented using a balanced tree, a sorted array, or other structures. The distinction matters because the interface may promise behavior that hashing alone does not provide. For example, a sorted map supports traversal in key order, whereas a basic hash table does not. Some hash-based maps maintain insertion order through additional arrays or linked relationships, but this is a separate property rather than a consequence of hashing.
The defining correctness requirement connects hashing to equality. If two keys are considered equal, they must produce equal hash values:
The converse is not required. Unequal keys may have identical hashes, so matching a hash value is generally only a preliminary test; the implementation must still determine whether the stored key equals the query key. Equality can mean identical integers, equal character sequences, or a user-defined relation appropriate to a particular type.
Keys must remain stable with respect to hashing and equality while stored. If a mutable object's hash depends on a field that changes after insertion, a later lookup may search a different location and fail to find the entry. Consequently, many libraries favor immutable keys or place responsibility for maintaining this invariant on the programmer. Object identity can also serve as the key relation, in which case changing the object's contents need not affect its identity-based hash.
The familiar claim of constant-time lookup usually counts table probes and treats hashing and equality as bounded-cost operations. For a previously unhashed string of length , computing a content-based hash generally requires work. A comparison between long strings may also be expensive. Thus, a table can perform an expected constant number of probes without providing a running time independent of key size. Implementations sometimes cache hash values in objects or entries to reduce repeated computation.
Hash computation and index selection
A hash function transforms a key into a value from a fixed range, commonly a machine-sized unsigned integer. The table then converts that value into an array index. These are conceptually distinct steps: a key's hash can remain unchanged while its bucket index changes when the table grows. A common indexing rule for buckets is
If is a power of two, reduction can instead use a bit mask, selecting the low-order bits of the hash.
Good distribution depends on the interaction between key patterns, the hash function, and the indexing rule. Consider integer keys that are all multiples of 16. Taking their unmodified low four bits sends every key to the same bucket in a 16-bucket table. Mixing the bits before indexing can avoid this particular failure. Prime table sizes are useful with some arithmetic hashing schemes, but choosing a prime does not by itself repair an inadequate hash function.
A useful noncryptographic hash spreads the key patterns expected in the application across the available range while remaining inexpensive to compute. Many designs seek an avalanche effect, in which changing a small part of the input changes many output bits. This is a desirable engineering property, not a proof that a function behaves randomly for every possible key set. Structured inputs can expose weaknesses that ordinary random test data does not reveal.
Universal hashing supplies a more explicit probabilistic framework. Instead of fixing one function for every execution, the implementation selects a function from a family with a bounded collision probability for any two distinct keys. A standard goal is
for distinct and , with probability taken over the random choice of function. This makes it possible to prove expected performance for any fixed input set without assuming that users naturally supply random keys.
A cryptographic hash function has additional security objectives, such as making collisions or preimages computationally difficult to find. These properties are not normally necessary for an internal table processing trusted data, and they may impose extra computation. Conversely, a fast unkeyed hash with good statistical distribution may be unsuitable when an attacker controls the keys. Hash-table design therefore distinguishes distribution quality, evaluation cost, and resistance to deliberate manipulation rather than treating them as interchangeable requirements.
Separate chaining
In separate chaining, the table is an array of buckets, and each bucket holds a collection of entries whose keys map to it. The simplest representation uses a linked list per bucket. Lookup computes the bucket index and searches that bucket for an equal key. Insertion adds an entry or updates an existing one; deletion removes the matching entry from the bucket.
If entries occupy buckets, the load factor is
Under a uniform distribution of keys, a bucket contains entries on average. A lookup therefore takes expected time, including the initial indexing operation. Chaining permits to exceed 1 because multiple entries can occupy the same bucket. Nevertheless, an increasing load factor generally means more comparisons and memory accesses.
For a concrete example, suppose a table has eight buckets and uses . The integer keys 10, 18, and 26 all belong to bucket 2. Looking up 18 requires searching that bucket, not examining entries in the other seven buckets. If all keys have this same remainder, however, the table behaves like a search through a single collection and may require linear time. Collision resolution preserves correctness in this case but does not preserve the intended speed.
Linked lists are not essential to chaining. Buckets may instead contain small arrays, vectors, or tree structures. Small contiguous collections can improve locality and reduce allocation overhead. Some implementations convert unusually large buckets into balanced trees, reducing the cost of searching those buckets when the relevant comparison rules permit it. These alternatives complicate insertion and deletion but can improve performance for particular workloads or provide protection against severe collision patterns.
Chaining can offer stable entry addresses when nodes are separately allocated: expanding the bucket array need not move the objects themselves. This is useful when other program components retain references to stored entries. Its costs include pointers, allocator bookkeeping, and potentially poor memory locality. Following a chain can require several dependent memory reads, each of which must wait for the preceding read to identify the next address.
Deletion is comparatively straightforward because removing one entry does not change how the other entries are reached. That simplicity is one reason chaining remains useful despite the popularity of compact, array-based tables. Actual behavior depends strongly on bucket representation, allocation strategy, and whether entries store their full hash values to avoid unnecessary key comparisons.
Open addressing and probe sequences
In open addressing, entries reside directly in the table's slot array. When a key's initial slot is occupied, the implementation follows a probe sequence until it finds the key or a suitable insertion position. Lookup must follow the same sequence used for insertion. In basic forms that depend on an empty slot to terminate an unsuccessful search, the table must retain unused capacity.
Linear probing examines consecutive positions:
where . Its main advantage is locality: nearby probes often access the same cache line. Its main weakness is primary clustering. A run of occupied slots attracts additional keys whose starting positions fall anywhere inside that run, causing the cluster to grow. At high occupancy, even a short logical operation can scan a long sequence of slots.
Quadratic probing uses offsets based on a quadratic expression in the probe number. Double hashing derives a step size from a second hash:
For the sequence to visit every slot, its step size must be relatively prime to . For a power-of-two capacity, an odd step satisfies that requirement. Quadratic schemes likewise require suitable choices of capacity, coefficients, and occupancy limits; an arbitrary quadratic sequence need not reach every slot.
Deletion cannot usually turn an occupied slot directly into an ordinary empty slot. A key displaced beyond that position might then become unreachable because lookup would stop too soon. A common solution is a tombstone, marking a deleted slot that searches must pass but insertions may reuse. Tombstones preserve probe continuity but can accumulate and degrade performance. Some linear-probing designs instead shift later entries backward when doing so preserves their lookup paths.
Robin Hood hashing modifies insertion by comparing displacement from each key's initial position. A more-displaced incoming entry may replace a less-displaced resident, which is then inserted farther along. This tends to reduce variation in displacement and can support early termination during lookup when the maintained ordering rules justify it. It does not eliminate the need for sufficient capacity or correct deletion handling.
Cuckoo hashing takes a different approach: a key has a small number of candidate positions, and inserting it may evict another key to one of that key's alternatives. Lookup examines only a fixed number of candidate locations, but insertion can encounter cycles or require rebuilding with different hash functions. Practical variants use buckets and sometimes a small auxiliary stash.
Expected performance, occupancy, and resizing
Hash-table performance is analyzed through computational complexity, but its guarantees require careful qualification. A basic table can have worst-case lookup if many keys collide or occupy a long probe sequence. Expected behavior usually depends on a distributional assumption or randomized choice of hash function, together with a controlled load factor. Expectations over input distributions and expectations over internal randomness are different claims.
For open addressing under the idealized uniform-hashing model, the expected number of probes in an unsuccessful search is at most
The corresponding bound for a successful search, under the usual assumptions about how entries were inserted, is
These expressions show why occupancy matters: as approaches 1, unsuccessful searches become increasingly expensive. They do not directly describe every practical probing method.
Linear probing has different classical estimates because its probes are correlated. Under standard random-home-position assumptions, approximate expected probe counts are
for successful search and
for unsuccessful search. At a load factor of 0.9, the latter expression is about 50.5 probes. The numerical estimate is model-dependent, but it illustrates the sharp cost of high occupancy with simple linear probing.
Dynamic tables generally expand after crossing an occupancy threshold. Expansion allocates a larger table and redistributes entries because their bucket indices or probe paths may change. Rebuilding normally costs . If capacity grows geometrically, for example by doubling, the total rebuilding work across a long sequence of insertions is linear in the number of inserted entries. Amortized analysis therefore assigns constant rebuilding cost per insertion, assuming the ordinary insertion work is also suitably bounded.
Amortized efficiency does not guarantee short individual pauses. One insertion may trigger a full rebuild, which matters in interactive or latency-sensitive systems. Incremental rehashing spreads migration over several operations, temporarily maintaining old and new tables and searching both when necessary. Its bookkeeping is more complicated because updates must remain consistent while entries move.
Shrinking introduces a related problem. Growing and shrinking at nearly the same occupancy can cause repeated expensive rebuilds when the size fluctuates. Implementations commonly use different thresholds, creating hysteresis. Open-addressed tables may also rebuild without changing capacity to remove tombstones. Effective occupancy then depends on both live entries and deleted positions that cannot terminate searches.
Static, perfect, and external-memory variants
Some applications know the entire key set before queries begin. This permits preprocessing that would be inconvenient for a general-purpose dynamic map. Perfect hashing constructs a collision-free mapping for a specified set of keys. It does not imply that the chosen function is collision-free over every possible input, only over the designated set.
A classic two-level construction associated with Michael Fredman, János Komlós, and Endre Szemerédi uses a first-level hash to divide keys into buckets and a separate second-level table for each bucket. If a bucket contains keys, allocating second-level space makes it possible to find a collision-free function by randomized trials. Choosing a suitable first-level function keeps the sum of these squared bucket sizes linear in , giving linear space and worst-case constant-time lookup for a static set under the construction's assumptions.
A minimal perfect hash function maps known keys bijectively to the integers . It can provide a compact index for fixed dictionaries, compiled keyword sets, and immutable data collections. However, the function alone does not establish whether an arbitrary query belongs to the original set: a nonmember can still produce an index. Exact membership requires additional information, such as storing and checking the original key. Compact fingerprints can instead provide probabilistic verification.
Storage systems face another constraint: reading one disk page or storage block is much more expensive than examining another nearby byte already in memory. Extendible hashing, introduced in 1979 by Ronald Fagin and colleagues, uses a directory indexed by a variable number of hash bits. Buckets split as needed, and the directory grows when additional distinguishing bits are required. Local bucket depth and global directory depth allow different buckets to represent different amounts of the hash space.
Linear hashing, developed by Witold Litwin and published in 1980, expands through an incremental sequence of bucket splits rather than repeatedly doubling an entire directory. A split pointer and the current expansion level determine which indexing rule applies. The next bucket to split is determined by the expansion schedule, not necessarily by the bucket receiving the triggering insertion.
These external-memory methods make growth more gradual and organize collisions around storage pages. Their costs are measured partly in page reads, writes, and overflow chains rather than only in CPU instructions. The distinction illustrates why no single hash-table layout is best for every setting: a design optimized for a small in-memory dictionary may behave poorly when entries are accessed through a database management system and persistent storage.
Memory layout and processor efficiency
Tables with similar asymptotic bounds can have very different measured performance. Modern processors move data through a memory hierarchy, and an access that misses in the CPU cache can cost much more than a simple arithmetic operation. Consequently, pointer chasing, cache-line utilization, allocation overhead, and key size often matter as much as the nominal number of comparisons.
Chaining distributes entries among separately allocated nodes unless an allocator deliberately groups them. Open addressing places slots contiguously, allowing several candidates to be examined after one cache-line fetch. This can make a table that performs more logical probes faster than one that follows fewer pointers. The benefit depends on entry size: large inline values reduce the number of slots per cache line and make relocation more expensive.
Many modern implementations separate compact control information from keys and values. A control byte may record whether a slot is empty or deleted and, for occupied slots, contain a small fingerprint derived from the hash. Lookup scans a group of these bytes before fetching full entries. If a fingerprint matches, the implementation checks the corresponding key; if not, it skips that entry without accessing its larger payload.
Vector operations, including single instruction, multiple data instructions, can compare several control bytes simultaneously. In an idealized model, an independently distributed -bit fingerprint matches an unrelated query with probability . A seven-bit fingerprint therefore rejects most unrelated candidates before full key comparison. Fingerprints are filters, not substitutes for equality checks, and their practical effectiveness depends on hash quality and layout.
The placement of values creates another trade-off. A flat table keeps entries inline and often offers excellent locality, but resizing or collision handling can move them. A node-based table stores pointers to separately allocated entries, potentially preserving addresses at the cost of indirection and allocation. Implementations can also store compact indices into an auxiliary entry array, separating the probing structure from payload storage and iteration order.
Benchmark results must therefore be interpreted in context. Successful and unsuccessful lookups exercise different paths; short integer keys differ from long strings; deletion-heavy workloads accumulate different costs from append-only ones. A table that fits in cache may behave differently once it grows beyond cache capacity. Meaningful evaluation specifies occupancy, key and value sizes, lookup distribution, mutation rate, memory use, and latency variability rather than reporting only operations per second.
Concurrent access and synchronization
A hash table shared by multiple threads must preserve its invariants while operations overlap. Without suitable coordination, one thread might observe an entry before its key or value is fully initialized, follow a pointer to freed memory, or search an array that another thread is replacing. These problems belong to concurrent computing and cannot be solved merely by selecting a well-distributed hash function.
The simplest strategy protects the entire table with a lock. This makes operations straightforward to reason about but serializes access, limiting scalability under contention. Finer-grained designs use locks for individual buckets or groups of buckets. Sharding partitions entries among several independent tables, usually according to hash bits, so unrelated operations can proceed concurrently. Workloads concentrated on a few popular keys may still overload particular shards.
Concurrent operations are often specified using linearizability: each completed operation should appear to take effect at one instant between its invocation and completion. This permits users to reason about a concurrent map in terms of a sequential specification. Iteration commonly has weaker guarantees. An iterator may observe some concurrent updates but not others, or traverse a snapshot created at additional memory and synchronization cost.
Atomic machine instructions can support implementations that avoid a single blocking lock. A compare-and-swap operation, for example, can install a new pointer only if the old pointer still has an expected value. However, using atomic instructions does not automatically make an algorithm lock-free, nor does it address every issue of memory visibility. The algorithm must establish how publication, deletion, and conflicting updates interact under the programming language's memory model.
Memory reclamation is particularly difficult. A removed node cannot be freed while another thread might still hold a reference to it. Techniques such as hazard pointers, epoch-based reclamation, and read-copy-update delay reclamation until access is safe. Each introduces costs or restrictions, and managed runtimes with garbage collection change—but do not eliminate—the synchronization problems surrounding logical deletion and updates.
Resizing adds another layer because old and new arrays can coexist. Threads may help migrate buckets, follow forwarding markers, or consult both tables according to a defined protocol. A correct design must prevent lost updates, duplicate visible entries, and false reports that a key is absent. In systems with strict latency requirements, progress guarantees and migration behavior can matter more than a small improvement in single-threaded lookup speed.
Adversarial inputs and security
A hash table can become a security liability when external users control its keys. If an attacker can construct many distinct keys that collide or generate long probe sequences, processing them may consume far more time than expected. A request containing many such fields can turn otherwise ordinary parsing or dictionary insertion into a denial-of-service attack.
For a simple chained table, inserting deliberately colliding keys can require quadratic total work when each insertion searches the existing chain for duplicates:
The attacker need not find two keys with identical full machine-sized hashes if merely forcing them into the same bucket is enough to cause costly behavior. The relevant attack surface depends on the hash function, capacity policy, collision handling, and information exposed by the application.
This class of attack received broad attention in 2011, when hash-collision denial-of-service weaknesses were demonstrated across multiple web programming environments. Web request parameters provided a particularly practical input channel because servers commonly inserted attacker-supplied names into dictionaries. The underlying issue was not incorrect retrieval: the tables still distinguished unequal keys. The failure was loss of an expected performance property under hostile inputs.
A major defense is keyed hashing, in which a secret chosen for the process or table influences the hash function. SipHash, introduced by Jean-Philippe Aumasson and Daniel J. Bernstein in 2012, was designed as a keyed pseudorandom function suited to short inputs and has been used for hash-table protection. Secret-dependent hashing makes offline preparation of collision sets substantially harder, although the complete security argument depends on the implementation and attacker's capabilities.
Other defenses include limiting request sizes, restricting the number of entries processed, or switching heavily populated buckets to structures with stronger worst-case search bounds. Randomization is not a universal guarantee: weakly seeded functions, information leaks, or adaptive queries can undermine particular schemes. Security analysis must specify which aspects of the table an attacker can observe or influence.
A secure hash choice also does not make a hash table a cryptographic commitment, password-storage mechanism, or integrity verifier. These tasks impose different requirements. Moreover, access patterns and timing may reveal information even if hash computation itself uses a secure primitive. Ordinary hash tables are generally not designed to provide constant-time or oblivious memory access.
Historical development and uses
Hashing developed from early efforts to locate records without scanning complete files or maintaining expensive ordered structures. A 1953 internal memorandum by Hans Peter Luhn at IBM is frequently cited in histories of the subject. Early terminology included “scatter storage,” reflecting the placement of records across an address space according to a computed transformation of their keys. Several researchers contributed to practical methods during the 1950s, so the history is broader than a single modern implementation.
The mathematical analysis of collision handling developed alongside these techniques. Donald Knuth's work on linear probing in the 1960s helped establish a detailed account of clustering and search costs; the subject later received extensive treatment in his 1973 book The Art of Computer Programming, Volume 3: Sorting and Searching. J. Lawrence Carter and Mark Wegman's 1979 publication on universal classes of hash functions provided a foundational way to connect randomized function selection with collision bounds.
Later work explored stronger guarantees and different storage environments. The static perfect-hashing construction of Fredman, Komlós, and Szemerédi appeared in 1984. Pedro Celis's work in the 1980s developed Robin Hood hashing, while Rasmus Pagh and Flemming Friche Rodler introduced cuckoo hashing in 2001. These developments address different objectives: compactness, bounded lookup, reduced variation in search distance, or more predictable behavior under specified assumptions.
In language implementations, hash tables commonly support dictionaries, sets, object-property storage, and symbol tables. A compiler may map an identifier to information about its declaration, type, or scope. A program can also use a table for memoization, storing previously computed results under argument-derived keys. Such uses require equality semantics that match the application's notion of an identical identifier or repeated computation.
In a relational database, a hash join builds a table from one input relation and probes it with rows from another to find matching join keys. Hash-based aggregation similarly maps grouping keys to partial results such as counts or sums. Large operations may partition their input so that processing fits available memory. These are uses of hashing within execution algorithms, distinct from maintaining a persistent hash index for individual record lookups.
Hash tables are less suitable when an application primarily needs ordered traversal, predecessor queries, or range searches. Balanced trees, binary search over sorted arrays, and storage-oriented ordered indexes address those tasks more directly. Likewise, a hash table alone does not define an eviction policy for a cache or a placement protocol for a distributed system. Those applications add separate mechanisms around the key-to-entry lookup structure.