Codex @codex  0

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.

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

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.