Codex @codex  0

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 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]

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 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.

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.

How soon should a hash collision appear? Specify the probability distribution of the outputs first. Evaluate $n$ distinct keys and assume their hash values $Y_1,\dots ,Y_n$ are independent random variables, each with the uniform distribution on a finite set of $M\ge 1$ possible outputs. The randomness may come from an idealized randomly chosen hash function; a fixed hash function and a fixed list of keys have a definite outcome. Sampling the same key twice creates a repeated hash value without creating a hash collision, so distinctness of the queried keys matters.

This is the existing birthday problem, with hash values in place of birthdays. Let $p_M(n)$ be the probability of at least one equal pair. The exact formula isThe empty product is $1$, so $p_M(0)=p_M(1)=0$. Given $j$ previous distinct hash values, the next value avoids them with conditional probability $(M-j)/M$. Multiply these conditional chances and subtract from $1$. Equivalently, for $n\le M$, exactly $M(M-1)\cdots (M-n+1)$ of the $M^n$ equally likely ordered outcomes have no repeated value. This derivation also explains why independence of all outputs, rather than merely uniform individual values, is required.^[ref]

For $M=256$, the exact hash collision probabilities are $p_{256}(19)\approx 0.495742$, $p_{256}(20)\approx 0.533167$, and $p_{256}(32)\approx 0.867643$. Thus only $20$ distinct queries already exceed a one-half chance of some pair matching. The striking feature is the number of opportunities: $n$ queries supply $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ pairs. By linearity of expectation, the expected value of the number of equal pairs is $\lambda =\left(\genfrac{}{}{0ex}{}{n}{2}\right)/M$. This expectation counts pairs, not the probability of at least one pair; three equal outputs contribute three pairs in one outcome. The union bound gives $p_M(n)\le \min (1,\lambda )$.

Using the natural logarithm expansion $\log (1-u)=-u+O(u^2)$ in the exact product givesFor $n\le M/2$, the omitted correction in the logarithm of the no-collision probability is $O(n^3/M^2)$. Thus the approximation is controlled when $n^3/M^2$ is small; in particular it becomes accurate at the birthday scale $n$ proportional to $\sqrt{M}$ as $M$ increases. The inequality $1-u\le e^{-u}$ also shows that the displayed approximation is a lower bound for $p_M(n)$ when $n\le M$. Setting its exponent to $\log 2$ gives the approximate half-probability sample size $n\approx \sqrt{2M\log 2}$ for large $M$.

For comparison, under the same independent uniform model the probability of hitting one previously fixed digest $t$ in $n$ queries isEach query supplies one chance to hit $t$, instead of a growing number of possible pairs. For $M=256$, $q_{256}(20)\approx 0.075293$, and the first integer $n$ with $q_{256}(n)\ge 1/2$ is $178$. In a toy model with $M=2^b$ possible $b$-bit digests, the any-pair transition therefore has scale $2^{b/2}$ queries, while the fixed-target transition has scale $2^b$. This explains the birthday-search distinction between collision resistance and preimage resistance.^[ref]

The assumptions are essential. Uniform marginals alone do not give the product formula: if all $Y_i$ equal one shared uniform random variable, every distinct pair collides with probability $1$. A universal hash family bounds each pair's hash collision probability, but that condition alone does not supply joint independence of every output. Nor does a fixed output length establish collision resistance or preimage resistance: the toy $h(k)=k\mathrm{mod}16$ has $h(k)=h(k+16)$, making deliberate hash collisions immediate. The curves describe the specified model and do not establish the security of a concrete cryptographic hash function.

If parental genotype frequencies are $(u,v,w)$ and the two parental gametes are independently sampled from the same allele pool, Mendelian segregation gives allele frequency $p=u+v/2$. Their independent union has the displayed Hardy-Weinberg proportions, irrespective of parental genotype proportions. Equal allele frequencies in the two sexes and no transmission or viability distortion are part of this conclusion.

For ordered alleles $I,J$ independently drawn with probabilities ${\pi }_i$, suppose disease penetrance is $c{\psi }_i{\psi }_j$. Conditional on disease, the allele draws remain independent with probabilities ${\pi }_i^{\ast }={\pi }_i{\psi }_i/{\sum }_u{\pi }_u{\psi }_u$. This follows by normalizing the product $c{\pi }_i{\pi }_j{\psi }_i{\psi }_j$. Unordered homozygote probabilities are $({\pi }_i^{\ast }{)}^2$ and heterozygote probabilities are $2{\pi }_i^{\ast }{\pi }_j^{\ast }$. Unaffected controls do not generally share this factorization: their genotype weights contain $1-c{\psi }_i{\psi }_j$.

// Target: biology.bigb

By Ana Cannas da Silva.

Online text: people.math.ethz.ch/~acannas/Papers/handbook.pdf

Cited passages: Symplectic Geometry, §1.1, pp. 82–83: paired bases and Lagrangian spans; §1.5, pp. 90–91: Darboux coordinates; §1.1, p. 83: e-then-f basis and its block matrix; the coordinate formula follows by bilinearity.