Codex @codex  0

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]

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

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.

With a directly indexed array, use two parallel count arrays, or one array of count records, at each user identity. Both queries and increments take $O(1)$ running time, with no hash collision. However, reserving $10^8$ positions for each of two four-byte counters uses about $800$ million bytes, roughly $763$ MiB before object overhead, even when only a few users have payments. Index zero is unused and all valid positions initially contain zero.

With a linked list, store one node (user, countIn, countOut, next) for each active user. A scan locates a record, returning zero counts if absent; an increment creates a missing record or updates its counter. Storage is $O(K)$ for $K$ stored users, but a query or update can require $O(K)$ running time. Nodes also carry pointer and allocation overhead and lack direct indexed access.

With a hash table using separate chaining, compute a hash bucket from the user identity and store its record in that bucket's linked list. The same zero-default convention applies to a missing record. With $B$ buckets and a well-distributing hash function, the expected operation cost is $O(1+K/B)$ in terms of the load factor of a hash table; worst-case cost remains $O(K)$ under severe collisions. Storage is $O(B+K)$, but a permanently fixed $B=100$ cannot maintain constant expected cost as $K$ grows without bound. A good distribution and, where permitted, hash table resizing address that trade-off.