Exercises — Hash function — properties - deterministic, uniform, fast

Broken property: Deterministic. Because a fresh $r$ is drawn on every call, the same key $k$ gives a different bucket each time. Concretely: insert("cat") might compute $r=57$ and land in bucket $(h_0+57)\mathrm{mod}100=57$ say; a later lookup("cat") draws a new $r=42$ and computes bucket $42$. The key sits in bucket $57$ but is searched for in bucket $42$ — retrieval fails. This directly breaks $k_1=k_2⟹h(k_1)=h(k_2)$. What about the other two? Fast: drawing one integer and doing one add + one $\mathrm{mod}$ is a fixed handful of operations, so it costs $O(1)$ — no dependence on $n$. Uniform: since $r$ is uniform on $\{0,\dots ,99\}$, the output $(k+r)\mathrm{mod}100$ is also uniform on $\{0,\dots ,99\}$ (adding a fixed $k$ just cyclically shifts a uniform value, which stays uniform) — so on its own it would scatter keys evenly. The only failure is determinism — but a hash table lives or dies on put-then-find matching, so that single failure is fatal. The fix: draw $r$ once when the table is created and store it as a fixed seed. Then $h$ is deterministic (same $k$, same $r$, same bucket) and still well-spread — this is exactly the legitimate "random salt fixed per table" idea from the parent note.

Compute each remainder:

• $16\mathrm{mod}8=0$
• $24\mathrm{mod}8=0$
• $40\mathrm{mod}8=0$
• $88\mathrm{mod}8=0$

Every key lands in bucket 0. All odd buckets stay empty. This wrecks Uniformity. Reason: $8=2^3$ is a power of two, so $k\mathrm{mod}8$ only looks at the lowest 3 bits of $k$. Multiples of 8 have those bits all zero, so they all collide.

Check a tricky one: $18=11+7$, so remainder $7$. And $73=66+7=6\cdot 11+7$, remainder $7$. Buckets used: 0, 4, 7 (twice), 8, 9, 10. Collision: $18$ and $73$ both land in bucket 7. Everything else is unique. With $n=7,m=11$, load factor $\alpha =7/11\approx 0.64$, so a single collision is entirely normal.

First, why Horner at all? We want the value of the polynomial $c_0{p}^2+c_1{p}^1+c_2{p}^0$ (for a 3-char string). The naive way computes each power $p^2,p^1,p^0$ separately and adds — that repeats multiplications and builds huge numbers. Horner's method factors the powers out from the inside: $c_0{p}^2+c_{1}p+c_2=((c_0)\cdot p+c_1)\cdot p+c_2.$ Read that right-hand side: start with the first char, then each new step multiplies the running total by $p$ (shifting everything up one "place" in base $p$) and adds the next char. Every character passes through exactly one multiply and one add, so the whole thing is $O(L)$ and never needs a separate power. That is precisely the update rule $\text{hash}\leftarrow \text{hash}\cdot p+c_i$.

Now apply it. Start hash = 0. Process characters k, e, y.

1. k = 11: $0\cdot 31+11=11$.
2. e = 5: $11\cdot 31+5=341+5=346$.
3. y = 25: $346\cdot 31+25=10726+25=10751$.
4. Take mod: $10751\mathrm{mod}100=51$.

Answer: $h(\text{"key"})=51$. Why we may mod at every step (self-contained why). Taking $\mathrm{mod}100$ inside the loop gives the same final answer because of one algebra fact: $(a\cdot b+c)\mathrm{mod}m=((a\mathrm{mod}m)\cdot b+c)\mathrm{mod}m$. In words, reducing a running total mod $m$ before the next multiply-and-add cannot change what it becomes mod $m$ afterwards — the quotient we throw away was already a multiple of $m$, and multiples of $m$ stay multiples of $m$. So we may keep the running number small at all times: it never exceeds about $m\cdot p$, which fits in a machine word. That is what keeps the cost $O(L)$ and the hash Fast.

Plain sum:

• "abc": $1+2+3=6\Rightarrow 6\mathrm{mod}100=6$.
• "cab": $3+1+2=6\Rightarrow 6\mathrm{mod}100=6$.

Same value ⟶ collision. Addition is commutative, so it ignores order — every anagram maps identically. That is a systematic (non-uniform) failure.

Polynomial hash (Horner, left→right):

• "abc" (a=1,b=2,c=3): $((0\cdot 31+1)\cdot 31+2)\cdot 31+3=(1\cdot 31+2)\cdot 31+3=33\cdot 31+3=1026\Rightarrow 1026\mathrm{mod}100=26$.
• "cab" (c=3,a=1,b=2): $((0\cdot 31+3)\cdot 31+1)\cdot 31+2=(93+1)\cdot 31+2=94\cdot 31+2=2916\Rightarrow 2916\mathrm{mod}100=16$.

$26\ne 16$ — the weights $p^i$ give each position a different "place value", so order now matters. No more anagram collision.

(a) $\alpha =\frac{n}{m}=\frac{20}{5}=4$. (b) Self-contained why. Fix one bucket $j$. For each key $i$, define an indicator $X_i$ that is $1$ if key $i$ lands in bucket $j$ and $0$ otherwise. Under Simple Uniform Hashing $P(h(k_i)=j)=\frac{1}{m}$, so $E[X_i]=\frac{1}{m}$. The number of keys in bucket $j$ is ${\sum }_{i=1}^n{X}_i$, and linearity of expectation (the expectation of a sum is the sum of expectations, even when the $X_i$ are dependent) gives $E\left[{\sum }_{i=1}^n{X}_i\right]={\sum }_{i=1}^{n}E[X_i]={\sum }_{i=1}^n\frac{1}{m}=\frac{n}{m}=\alpha .$ So the expected keys in a fixed bucket is exactly $\alpha =4$. (Sanity: $20\cdot \frac{1}{5}=4$.) (c) Average successful-search probes $\approx 1+\frac{\alpha }{2}=1+\frac{4}{2}=3$.

Why $1+\alpha /2$, not $1+\alpha$? The $1$ is fixed cost: you must compute the hash and step to the head of the chain — one unavoidable operation. The extra term measures how far down the chain you walk to find a key that is already stored. Here is the sketch: think of the keys inserted into one chain in order. When you later search for the $t$-th key inserted into that chain, it sits behind the $t-1$ keys that were already there, so finding it costs about $t$ steps into the chain. Average that cost over all keys, and each key on average sits behind half of its chain-mates (some are near the front, some near the back, evening out to the middle). Since a full chain averages $\alpha$ keys, half of that is $\alpha /2$. Add the fixed $1$ and you get $1+\alpha /2$. (Contrast an unsuccessful search, where you must walk the whole average chain, giving $1+\alpha$.)

With $\alpha =4$ the chains are long — you're doing ~3 comparisons per lookup on average, no longer close to $O(1)$. This is the signal to rehash. See Load Factor and Rehashing.

(a) Each of the 3 positions has 26 choices, independent: $|U|=26^3=17576$. (b) Pigeonhole Principle: distributing $17576$ items into $100$ buckets, the fullest bucket holds at least $\lceil \frac{17576}{100}\rceil =\lceil 175.76\rceil =176\text{ keys.}$ No hash function — however clever — can avoid this. Since $|U|=17576\gg m=100$, collisions are unavoidable. The best a good hash can do is make the distribution even (close to 176 everywhere) rather than lumpy. This is why a hash function's job is not "no collisions" but "few, evenly spread collisions."

Resize triggers when $\alpha =n/m>0.75$. With $m=8$: threshold count is $0.75\times 8=6$. So while $n\le 6$, $\alpha \le 0.75$ (OK). Inserting the 7th key gives $\alpha =7/8=0.875>0.75$ ⟶ trigger. After doubling: $m=16$. Now $\alpha =7/16=0.4375$, comfortably below threshold. All 7 keys are rehashed into the 16-bucket table (each recomputed with $\mathrm{mod}16$).

First resize at $n=7$; new $m=16$.

Start $m=5$. Threshold count $=0.75\times 5=3.75$, so resize fires once $n\ge 4$ (since $4/5=0.8>0.75$).

Insert 12: $12\mathrm{mod}5=2$. Bucket 2 = [12]. $n=1,\alpha =0.2$. OK. Insert 22: $22\mathrm{mod}5=2$. Collision with 12 — chain in bucket 2 = [12, 22]. $n=2,\alpha =0.4$. OK. Insert 9: $9\mathrm{mod}5=4$. Bucket 4 = [9]. $n=3,\alpha =0.6$. OK. Insert 5: $5\mathrm{mod}5=0$. Bucket 0 = [5]. $n=4,\alpha =4/5=0.8>0.75$ ⟶ RESIZE.

Double to $m=10$. Rehash all 4 keys with $\mathrm{mod}10$:

• $12\mathrm{mod}10=2$
• $22\mathrm{mod}10=2$ (still collide! — bucket 2 = [12, 22])
• $9\mathrm{mod}10=9$
• $5\mathrm{mod}10=5$

Now $\alpha =4/10=0.4$. OK.

Insert 17: $17\mathrm{mod}10=7$. Bucket 7 = [17]. $n=5,\alpha =0.5$. OK, no resize.

(d) Final table ($m=10$):

Note: $12$ and $22$ collide under both $\mathrm{mod}5$ and $\mathrm{mod}10$, because $22-12=10$ is a multiple of both. Resizing doesn't magically separate keys whose difference is a multiple of the new $m$ — that's the honest limit of the division method.

Step 1 — anagrams are forced to collide. If two strings $s$ and $s^{\prime }$ are anagrams, they have the same multiset of characters, hence ${\sum }_i{c}_i(s)={\sum }_i{c}_i(s^{\prime })$. Since $h$ reads only that sum, $h(s)=f(\text{same sum})=h(s^{\prime })$. So every anagram class maps to a single bucket, whatever $f$ is — $f$ never even sees the order, so it cannot separate what the sum has already merged.

Step 2 — counting shows this is a structural, not rare, failure. Fix strings of length $L$ over an alphabet of size $A$ with character values in $\{1,\dots ,A\}$. The number of distinct sums is bounded: ${\sum }_i{c}_i$ ranges only from $L$ (all smallest) to $LA$ (all largest), so there are at most $L(A-1)+1$ possible sum-values, i.e. linear in $L$. But the number of distinct strings is $A^L$, exponential in $L$. By pigeonhole (Pigeonhole Principle), the strings crush into at most $\sim L(A-1)+1$ groups, so some group has at least $\frac{A^L}{L(A-1)+1}$ strings — an enormous pile forced onto one hash value before the table's $m$ buckets are even considered.

Step 3 — why $f$ cannot save it. Uniformity demands $P(h(k)=j)=\frac{1}{m}$ for a typical key drawn from the language. But real dictionaries contain heavy anagram families ("listen"/"silent"/"enlist", "stop"/"pots"/"tops"/"opts"). All members of each family land in one bucket, so those buckets are systematically overloaded while many others stay empty. $f$ can relabel the sums (send sum $6$ to bucket $3$ instead of $6$) but it can never un-merge two keys that already share a sum — relabelling is a function of the sum alone. Hence the distribution is inherently lumpy: not uniform.

The fix (ties back to L3.1). Make the hash depend on position, not just the multiset. The polynomial hash $h(s)=\left({\sum }_i{c}_i{p}^i\right)\mathrm{mod}m$ gives character position $i$ the distinct weight $p^i$, so reordering characters changes the value — exactly what separated "abc" (26) from "cab" (16) in L3.1. Positional weighting is precisely the ingredient the commutative sum was missing.

One-line takeaway ::: A hash that reads only the character sum forces every anagram into one bucket, and there are exponentially many strings but only linearly many sums, so the overloaded buckets are structural, not bad luck — positional weights $p^i$ are the fix.

The figure below shows the five rungs of this page stacked as a staircase: L1 Recognition (blue) at the bottom, then L2 Application (green), L3 Analysis (yellow), L4 Synthesis (red), and L5 Mastery (white) at the top. Each coloured box carries the one-line skill for that rung, and the white arrows show that every level reuses the one below it — you cannot analyse why a hash works (L3) until you can apply one (L2), and you cannot apply one until you can recognise the property in play (L1). Use it as a checklist: if a problem stumps you, drop one rung and make sure that skill is solid first.