Hash table

A hash table stores records by key: for example, a product number can select its current stock count without scanning every product. A hash function selects a hash bucket in an array, and a collision-handling method such as separate chaining retains distinct keys assigned to the same hash bucket. The useful idea is to narrow the search to one small collection, while key equality decides which record actually matches.

Use a map interface with one value per key: get(k) returns the associated value or an explicit absent result; put(k,v) replaces the value if an equal key is present, otherwise inserts a new record; delete(k) removes the matching record if present. The absent result must be distinguishable from every permitted stored value. Replacing a value does not increase the record count $n$. A hash collision between unequal keys must never cause one record to replace the other.^[ref]

Let $x\sim y$ denote the chosen key equality, an equivalence relation, and let $h_m$ be the bucket-index hash function for $m>0$ hash buckets. Correctness requiresThe converse is false: equal bucket indices merely identify candidates for a key equality comparison. If an implementation first computes a full hash value $H(k)$ and then reduces it to a bucket index, equal keys must have equal $H$ values too. Keep both key equality and the hash function stable while a key is stored; changing the key so it selects another hash bucket can make its record unreachable. This distinction is explicit in the published hashCode/equals contract.^[ref]

For a constructed integer example, use modular arithmetic to define $h_m(k)=k\mathrm{mod}m$ and store keys $1,5,9,2$ with values $A,B,C,D$. At $m=4$, three records share hash bucket $1$ and one occupies hash bucket $2$. The hash table load factor isIt is the mean number of records per hash bucket, including empty hash buckets, not a bound on the longest chain. With separate chaining, $\alpha$ may exceed $1$ because records live in the chains rather than one record being confined to each array slot.

Growing this example to $m=8$ changes the bucket-index hash function: key $5$ now belongs to hash bucket $5$, while keys $1,9$ still share hash bucket $1$. Every record must be assigned using the new bucket-index hash function; copying the old array of chain heads unchanged is insufficient. The hash table load factor becomes $4/8=1/2$.

For an insertion-only sequence starting empty with constant initial capacity, one policy doubles $m$ before inserting a new key that would make $n>m$. A rebuild for separate chaining allocates the new array and transfers each existing record directly into its new chain. Since keys are already distinct, transfer needs no duplicate search. With constant-cost hashing and linking, this takes $O(n+m)$ time complexity, hence $O(n)$ at a growth threshold. Amortized analysis charges the occasional rebuild across many insertions: the old capacities $1,2,4,\dots ,2^r$ form a geometric series with sum $2^{r+1}-1$, so total rebuilding work over $N$ insertions is $O(N)$. This gives $O(1)$ amortized resizing overhead; an insertion that triggers a rebuild can still take $O(n)$.^[ref]

The search to check for an existing key is additional work. Bounded hash table load factor together with the probabilistic assumptions in separate chaining gives expected amortized $O(1)$ insertion, not worst-case $O(1)$. Rehashing alone gives no distribution guarantee: the diagram's keys $1,9,17,25$ all collide modulo both $4$ and $8$. Even a low hash table load factor permits a long chain. If supporting shrinkage too, leave a gap between growth and shrink thresholds to avoid repeated rebuilding when insertions and deletions alternate near one threshold.^[ref]

A set data structure backed by a hash table. It stores each key at most once and supports membership tests, insertion, and removal with expected constant time under suitable hashing and load assumptions.

An associative array implemented with a hash table. It associates each stored key with a value and resolves collisions between keys with equal hash locations.

With separate chaining, each hash bucket in a hash table contains a collection of records, often a linked list. Lookup computes the bucket index, then follows that chain until a key equality comparison succeeds or the chain ends. A hash collision therefore affects the search work without merging unequal keys. Deletion searches the same chain and unlinks the matching record; in a singly linked list, remembering the preceding record during the search permits the unlink.^[ref]

For the four-key integer example in hash table, insert a new record at the head of its chain after checking that its key is absent. Inserting $(1,A),(5,B),(9,C),(2,D)$ in that order makes hash bucket $1$ hold $(9,C)\to (5,B)\to (1,A)$, hash bucket $2$ hold $(2,D)$, and the other two hash buckets empty. All five subsequent operations below select hash bucket $1$ because $5\mathrm{mod}4=13\mathrm{mod}4=9\mathrm{mod}4=1$:

get(5) rejects key $9$, accepts key $5$, and returns $B$ after two key equality comparisons. get(13) rejects $9,5,1$ and reports absence after three comparisons. put(5,B*) examines $9,5$ and replaces the value without changing $n=4$. delete(9) examines just the head record, removes it, and gives $n=3$. Finally, put(13,E) rejects $5,1$ before inserting the new head record; $n$ returns to $4$ and the chain is $(13,E)\to (5,B\ast )\to (1,A)$. The successive hash table load factors are $1,1,1,3/4,1$. These counts follow from the stipulated chain order; a different insertion policy changes the successful-search counts.

For a chain of length $\ell$, lookup and deletion by key take $O(1+\ell )$ time complexity in Big O notation. The same applies to put before any resizing, since replacement semantics require checking for an existing equal key. Head insertion alone is $O(1)$ if absence is already known; that is a different precondition. These bounds assume $O(1)$ bucket-index hashing, array access, key equality comparisons, allocation and link updates. A long string or large integer can make hashing or comparison depend on its encoded length, so counting record visits alone does not establish constant running time.

Under simple uniform hashing, each distinct key's bucket index is an independent random variable with a uniform distribution on a finite set of $m$ indices. The keys and query are fixed independently of this random assignment. Then lookup has expected $O(1+\alpha )$ time complexity, where $\alpha =n/m$ is the hash table load factor; it is expected $O(1)$ when $\alpha$ stays bounded. These are model assumptions, not an automatic consequence of using a deterministic hash function.^[ref]

Here is the short calculation. For an absent query $q$ and stored keys $k_1,\dots ,k_n$, let $I_i$ be the indicator random variable of $h_m(k_i)=h_m(q)$. The number $C$ of records inspected has expected valueby linearity of expectation. For a present fixed query, scanning its entire chain inspects at most itself plus all other colliding records, with expected value $1+(n-1)/m$; stopping at the match only decreases this upper bound. Adding constant hashing and bucket access yields expected $O(1+\alpha )$ for either query. The argument needs pairwise collision bounds; it does not require all the indicator random variables to be independent. A universal hash family can provide a related bound by random choice of a hash function for a fixed key set, as explained in that article.

The worst case remains $O(n)$, and an absent query takes $n$ comparisons if all $n$ records occupy its hash bucket. For instance, $1,1+m,1+2m,\dots ,1+(n-1)m$ all collide under $h_m(k)=k\mathrm{mod}m$. Separate chaining remains correct, but a sequence of insertions that each checks the existing chain can take quadratic total work. Amortized analysis of resizing does not remove this search cost, and an adaptive choice of keys based on a known hash function is outside the stated simple uniform hashing model.

A probabilistic model assigning distinct keys independent bucket indices with a uniform distribution on a finite set. It supplies an expected value bound for separate chaining, not a guarantee for every deterministic hash function or workload.

A hash table collision-handling method storing at most one live record per array slot. A hash function chooses a starting slot, and a probe rule chooses further slots. Unlike separate chaining, records occupy the slots themselves.

An open addressing probe rule that visits $h_m(k),h_m(k)+1,h_m(k)+2,\dots$ modulo $m$, using modular arithmetic, until a matching record or an appropriate stopping slot is found.^[ref]

For capacity $m>0$, the hash table probe numbered $i$, starting at zero, inspects the array indexThe hash function $h_m$ gives the first array index. Each subsequent hash table probe moves one slot forward, wrapping from $m-1$ to $0$ by modular arithmetic. Keep the hash function and key equality fixed while hash table records are stored.

Use three distinguishable slot states: occupied by a live hash table record; never used since initialization or rebuilding, written E; or deleted, written D, a tombstone in open addressing. Lookup compares occupied hash table keys using key equality, stops at E, and continues past D.^[ref]

For an original example, take an eight-slot array, integer hash table keys, and the hash function $h_8(k)=k\mathrm{mod}8$. Start with all slots E and insert the hash table records $(0,A),(8,B),(16,C),(9,V)$ in that order. The insertion hash table probe traces, expressed as array indices, areThe resulting array holds hash table keys $0,8,16,9$ at array indices $0,1,2,3$, with E in the other four slots. The first three hash table keys have the same initial array index, a hash collision; the fourth begins at $1$ but joins the same linear probing cluster. Lookup of $16$ examines array indices $0,1,2$, rejecting $0,8$ before returning $C$. Lookup of absent $24$ examines $0,1,2,3,4$, including the stopping E: five hash table probes for a hash table load factor $\alpha =4/8=1/2$.

Bound lookup to at most $m$ hash table probes, even if no E remains. For algorithm termination, the first $m$ array indices are distinct: equality of $p_i(k)$ and $p_j(k)$ implies that $m$ divides $i-j$ by modular arithmetic, and $0\le i,j<m$ forces $i=j$. They therefore cover the entire finite set of slots exactly once. If no occupied hash table key matches and no E is encountered, exhausting these $m$ hash table probes establishes absence; wrapping around again supplies no new information.^[ref]

The attraction is a compact array and a simple hash table probe rule. Consecutive slots can benefit from spatial locality, although actual memory cache behavior depends on representation and hardware. Correctness rests on preserving the search route; speed depends on how long that route becomes. The linear probing cluster below explains why even a moderate hash table load factor gives no universal constant lookup bound.

A maximal consecutive run of occupied or deleted slots in linear probing, bounded by never-used slots when any exist; adjacency wraps around by modular arithmetic. Deleted slots still belong to the search run.^[ref]

In the eight-slot example, array indices $0,1,2,3$ form one linear probing cluster. Inserting absent hash table key $10$ starts at $2$, passes the occupied slots $2,3$, and fills $4$. This extends the same linear probing cluster despite $10$ having a different initial array index from $0,8,16$. A hash collision at the initial slot is enough to make later slots compete too.

For a worst-case family, insert integer hash table keys $0,m,2m,\dots ,(n-1)m$ into an empty capacity-$m$ array, using the hash function $h_m(k)=k\mathrm{mod}m$, where $1\le n<m$. They occupy array indices $0,\dots ,n-1$. Lookup of absent $nm$ needs $n+1$ hash table probes. Taking $n=\lfloor m/2\rfloor$ gives hash table load factor at most $1/2$ while the number of hash table probes grows with $m$. Thus occupancy alone cannot promise constant lookup work.

Before any rebuilding, bounded lookup, deletion by hash table key, and insertion with a duplicate check each have worst-case $O(m)$ time complexity in Big O notation, assuming constant-cost hash function evaluation, array access and key equality. The counterexample gives a matching linear worst-case growth in the number of hash table probes. Hash table resizing is additional work; expensive string comparisons or hashing also fall outside these constant-cost assumptions.

In an insertion-only table, an absent hash table key starting anywhere inside a linear probing cluster reaches its far end. Filling a one-slot gap can merge two runs, joining hash table keys with different initial array indices into one long search route. The insertion of $10$ above exhibits this effect without a hash collision with $0$ at their initial slots.^[ref]

A deleted-slot marker in open addressing. Lookup continues past it because a hash collision may have displaced a match further along. Linear probing can reuse the slot for insertion after checking for an existing equal key. A genuinely empty slot can terminate lookup; this marker cannot.^[ref]

Delete hash table key $8$ from the original eight-slot example. Writing E into array index $1$ makes lookup of $16$ inspect $0,1$ and incorrectly report absence, although its hash table record remains at $2$. Writing D instead makes lookup pass $1$ and reach $2$, returning $C$ after three hash table probes. The deleted slot must remember that the search route once continued through it.

A short algorithm correctness proof uses this invariant: no never-used slot precedes a stored hash table key along its linear probing route. Initially the claim is vacuous. Insertion places a new hash table record no later than the first E, possibly at an earlier D, and cannot create an E before another stored hash table record. Replacing a value leaves all slots occupied as before. Deletion to D also creates no E. By mathematical induction over operations, the invariant persists, so stopping lookup at E is sound. Deletion directly to E invalidates that argument, as the diagram shows.

To implement the hash table map operation put(k,v) in one bounded scan, remember the first D encountered, but keep checking occupied hash table keys. A later key equality match means replace that hash table record's value and stop. Only after reaching E, or completing $m$ hash table probes, is absence established. Then insert at the remembered D, if any; otherwise use the stopping E. If all $m$ slots are occupied and no match exists, report full or rebuild before trying again. Merely finding D is not permission to create a second equal hash table key.^[ref]

Continue from the correctly deleted example, with hash table keys $0,16,9$ at array indices $0,2,3$ and D at $1$. put(16,Z) examines $0,1,2$ and updates the value at $2$, leaving $1$ deleted and retaining three live hash table records. Inserting immediately at $1$ would instead create two copies of $16$. Now put(24,W) examines $0,1,2,3,4$, proves absence at E, and places the new hash table record at the remembered array index $1$. The hash table load factor rises from $3/8$ to $4/8$; reusing D avoids extending the linear probing cluster to $4$.

For a boundary case, fill all eight slots with hash table keys $0,1,\dots ,7$ and then delete all eight to D. The live hash table load factor is zero, but absent lookup of $16$ still needs eight hash table probes. put(16,C) also checks eight slots before reusing the first D, at array index $0$. A loop that waits indefinitely for E would never finish in this state. Rebuilding from the live hash table records into a fresh array removes each tombstone in open addressing and restores never-used stopping slots.^[ref]

One inspection of an array slot during an open addressing operation. Its array index follows the chosen probing rule; its contents determine whether to continue, return a matching hash table record, or establish absence.

The collection of records assigned to one bucket index by a hash function. In separate chaining, an array slot refers to this collection, which may be empty.

For $m>0$ hash buckets, number them $0,\dots ,m-1$ and write ${\ell }_j$ for the number of records in hash bucket $j$. Each record belongs to exactly one hash bucket, soAn empty hash bucket contributes zero to this sum but still contributes one to the denominator $m$. The hash table load factor therefore measures records per allocated hash bucket, not records per nonempty hash bucket. A hash bucket is a destination selected by the bucket-index hash function; with separate chaining, its records need not occupy consecutive positions in computer memory.

For the twelve-record concentrated placement in load factor of a hash table, one hash bucket contains twelve records and seven hash buckets are empty. Averaging only over nonempty hash buckets gives $12$, whereas the hash table load factor is $12/8=1.5$. This difference matters when deciding how much array capacity to allocate. For $n>0$, the largest hash bucket satisfies $\lceil n/m\rceil \le {\max }_j{\ell }_j\le n$; the lower bound follows because at least one entry cannot be below the arithmetic mean. Neither inequality says that an actual hash function achieves a balanced placement.

The equivalence relation used to decide whether two keys name the same record. A hash function must respect key equality; a hash collision does not establish key equality.

The choice of key equality is part of the map's meaning. In the one-value-per-key policy of hash table, one record represents each stored equivalence class of keys: put(k,v) updates an existing equal key and adds a record only if no equal key is present. A collection that deliberately retains repeated equal keys has a different policy; its load count must count those extra records too. Repeated calls and distinct stored records are different quantities.^[ref]

For an original example, restrict keys to two-letter strings using letters A through Z or a through z. Declare two keys equal when replacing every uppercase letter by its lowercase counterpart gives the same string. Assign each letter its position $1,\dots ,26$ in the alphabet, ignoring case, and define the bucket-index hash function as the sum of the two positions modulo $8$, using modular arithmetic. Then AB and ab are equal keys and both select hash bucket $3$. Key ba also selects hash bucket $3$ because $2+1=3$, but is unequal to ab: order still matters. Starting empty, put(AB,7), put(ab,9), put(ba,4) leave two records, with values $9$ for the ab equivalence class and $4$ for ba; the hash table load factor is $2/8=1/4$, not $3/8$.

The compatibility rule is one-way: $x\sim y\Rightarrow h_m(x)=h_m(y)$. Otherwise a lookup using an equal spelling could search a different hash bucket and incorrectly report absence. Equal indices merely allow a key equality check. Both the equivalence relation and the hash function must stay consistent while records are stored; changing equality-relevant key contents can invalidate the lookup rule. The Java contract imposes these consistency and equality requirements on equals and hashCode.^[ref]

The number $n$ of stored records divided by the number $m>0$ of hash buckets. For separate chaining, this is the mean chain length over all hash buckets, including empty ones.

Consider two original separate chaining placements using the deterministic hash function $h_m(k)=k\mathrm{mod}m$ on nonnegative integer keys. With $m=8$, keys $0,1,\dots ,11$ give the balanced chain lengths $(2,2,2,2,1,1,1,1)$. Instead, keys $0,16,32,\dots ,176$ all select hash bucket $0$, giving $(12,0,0,0,0,0,0,0)$. Both store $n=12$ records, so both have $\alpha =12/8=1.5$. The maximum chain lengths are $2$ and $12$. These are constructed placements, not measured workloads.

For an absent query, separate chaining inspects every record in the selected hash bucket. Key $24$ selects hash bucket $0$ in both examples but is stored in neither, so it takes two key equality comparisons in the balanced placement and twelve in the concentrated placement. Key $15$ selects hash bucket $7$ and instead takes one comparison in the balanced placement and zero in the concentrated placement. If an absent query's bucket index has the uniform distribution on a finite set of eight indices, its mean comparison count is $1.5$ in either fixed placement. That average does not limit the cost of a particular query.

For successful lookups, suppose each of the twelve stored keys is queried with equal probability, with fixed chain order and no rearrangement on access. A chain of length $\ell$ contributes comparison counts $1,\dots ,\ell$, irrespective of its order. ThusThe balanced placement gives $(4\cdot 3+4\cdot 1)/12=4/3$ comparisons; the concentrated placement gives $(1+\cdots +12)/12=13/2$. Even this average depends on more than $\alpha$: concentration appears through the squared chain lengths. These exact counts exclude computing the hash function, locating the hash bucket, and allocating records. Elapsed lookup time also depends on the cost of key equality, key length, and memory access latency; $\alpha$ alone specifies none of them.

The expected $O(1+\alpha )$ time complexity bound for separate chaining needs a probabilistic assumption. Fix distinct stored keys and a query independently of the random choice of hash function, and require ${\mathrm{Pr}}_h[h_m(x)=h_m(y)]\le c/m$ for every unequal pair, where $c$ is a constant independent of $n,m$. With constant-cost hashing, array access and key equality, this suffices. The authored chaining analysis cited here uses this pairwise-collision argument; its multiplicative construction has $c=2$, rather than the $c=1$ of simple uniform hashing.^[ref]

For the proof outline, let $I_i$ be the indicator random variable that stored key $k_i$ shares an absent query $q$'s hash bucket. By linearity of expectation,A present query's full chain contains itself plus at most $n-1$ other records, giving $\mathbb{E}[C_{\mathrm{hit}}]\le 1+c(n-1)/m$. Stopping at the match can only improve this bound. Full independence is unnecessary for this calculation, but fixed known hash functions and keys chosen adaptively to collide are outside the stated assumption. Keeping $\alpha$ bounded then controls expected lookup work, while the concentrated example still explains why it gives no worst-case guarantee.

For the balanced twelve-record map, put(3,new_value) replaces a value, so $n=12$ and $\alpha =1.5$ remain unchanged. An absent key such as $19$ instead adds a thirteenth record, giving $\alpha =13/8$ if capacity stays fixed. Under a policy that stores every repeated-key record separately, another record with key $3$ would also increase $n$; all equal-key records necessarily share a hash bucket when the hash function respects key equality. State the map policy before interpreting the count.

The appeal of the hash table load factor is that one number helps tune a space-versus-search tradeoff: more hash buckets require more array storage and can reduce expected search work under the stated assumptions. The actual chain lengths and query choices still matter.

In open addressing, $m$ counts record slots and $n$ counts live records, so $\alpha =n/m\le 1$. A policy retaining at least one genuinely empty slot requires $\alpha <1$; being below one is not itself a speed guarantee. For deletion using a tombstone in open addressing, also track $t$, the number of marked slots: $(n+t)/m$ counts slots that cannot terminate an unsuccessful probe. For example, $m=8,n=3,t=4$ gives live occupancy $3/8$ but nonempty-or-marked occupancy $7/8$. These ratios answer different questions.^[ref]

Changing the number of hash buckets and reassigning stored records using the new bucket-index hash function. Amortized analysis of rebuilding and expected value bounds for subsequent lookup address different costs.

Rebuild the balanced example from load factor of a hash table with $m^{\prime }=16$ while keeping exactly the same twelve records. Under $h_m(k)=k\mathrm{mod}m$, keys $0,\dots ,7$ retain their indices, whereas keys $8,9,10,11$ move from hash buckets $0,1,2,3$ to hash buckets $8,9,10,11$. The new chain lengths are twelve ones followed by four zeros; ${\alpha }^{\prime }=12/16=3/4$. Copying the old eight chain heads and adding eight empty heads would leave those four moved keys unreachable by the new lookup rule.

For a short algorithm correctness outline, allocate the new array, visit every old record once, compute its new bucket index, and link it into that hash bucket. At every step, each transferred record is stored exactly once at the index prescribed by the new hash function. Finishing the visit therefore preserves every key-value association and makes the new lookup rule valid. Direct transfer can skip duplicate searches because the old one-value-per-key map already established distinct equivalence classes; rebuilding is not twelve new user insertions.

Under constant-cost hashing, linking and slot initialization, separate chaining rebuilding takes $O(n+m+m^{\prime })$ time complexity: initialize $m^{\prime }$ new heads, examine $m$ old heads, and transfer $n$ records. For doubling, $m^{\prime }=2m$, this is $O(n+m)$ in Big O notation. It is $O(n)$ when the resize policy makes $m$ proportional to $n$, but an enormous mostly empty old array can make scanning its heads dominate. Growing capacity can lower $\alpha$ without shortening a particular chain: the concentrated keys $0,16,\dots ,176$ all remain in hash bucket $0$ after growth from eight to sixteen.

For an insertion-only sequence starting empty, choose initial capacity $m_0=8$ and double before a genuinely new key would make $n>m$. The first three growths occur before inserting records $9,17,33$ and transfer $8,16,32$ existing records. If $N=33$ distinct records are inserted, the transfer count is $8+16+32=56$. More generally, the transferred old capacities form a geometric series; if the last is $M<N$, their sum is $2M-m_0<2N$. Initializing and scanning these geometrically growing arrays also costs $O(N)$ in total, giving $O(1)$ amortized rebuilding overhead per insertion. A triggering insertion still pays for its whole rebuild.^[ref]

The illustrative twelve-record resize above is an explicitly requested rebuild, not a growth triggered by this threshold policy. Checking for an equal key before growing also prevents a value replacement from triggering unnecessary growth. To combine resizing overhead with expected constant insertion time complexity, separately impose the collision and constant-cost assumptions in load factor of a hash table. Amortized analysis distributes rebuilding costs over operations; it does not randomize a poor hash function or bound a single operation's latency. With deletions, separate the grow and shrink thresholds; for example, growing when full and halving at one-quarter live occupancy leaves room for many operations between opposite rebuilds.^[ref]

// Target: computer-science.bigb

The identifier used to select a hash table record. Key equality determines whether two identifiers name the same entry, while a hash function chooses where its lookup begins.

An entry pairing a hash table key $k$ with its associated value $v$. In the map interface of hash table, each key equality class has at most one live hash table record.