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]