= Hash table
{wiki}
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.<6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff/Lecture 8: Hashing I>[p. 1, dictionary operations and replacement of an existing key]{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 requires
$$
x\sim y\ \Longrightarrow\ h_m(x)=h_m(y),\qquad h_m(x)\in\{0,\ldots,m-1\}.
$$
The 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.<Java Platform, Standard Edition 25 API Specification by Oracle/Object (Java SE 25 & JDK 25)>{ref}
For a constructed <integer> example, use <modular arithmetic> to define $h_m(k)=k\bmod 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> is
$$
\alpha=\frac{n}{m}=\frac44=1.
$$
It 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$.
\Image[/hash-table-resizing-buckets.png]
{title=<Hash table resizing> recomputes indices but does not guarantee fewer <hash collisions>}
{id=hash-table-resizing-buckets}
{description=Original deterministic model using $h_m(k)=k\bmod m$, not a measured implementation. The upper panels retain keys $1,5,9,2$ in four and eight <hash buckets>; chain order is illustrative. The lower counterexample retains all four keys $1,9,17,25$ in <hash bucket> $1$ even after doubling.}
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,\ldots,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)$.<6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff/Lecture 9: Hashing II>[p. 2, rebuilding cost and geometric table doubling]{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.<6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff/Lecture 9: Hashing II>[p. 3, expected bounds and shrinking at one-quarter occupancy]{ref}
Back to article page
