TAOCP 6.4: Hashing

Section 6.4 exercises: 78/78 solved.

78 items

Section 6.4. Hashing

Exercises from TAOCP Volume 3 Section 6.4: 78/78 solved.

# Rating Category Status Time
1 [20] medium solved 4m16s
2 [20] medium solved 3m58s
3 [23] medium solved 2m30s
4 [M30] math-hard solved 1m15s
5 [15] simple verified 1m20s
6 [15] simple solved 2m14s
7 [HM30] hm-hard solved 3m32s
8 [M34] math-hard solved 2m37s
9 [M30] math-hard solved 1m22s
10 [M38] math-project solved 6m14s
11 [16] medium solved 3m47s
12 ▶ [21] medium solved 6m48s
13 ▶ [24] medium solved 9m12s
14 [24] medium solved 5m15s
15 [16] medium verified 1m19s
16 [10] simple verified 1m02s
17 [15] simple solved 1m19s
18 ▶ [21] medium solved 7m01s
19 [40] project solved 2m34s
20 [M25] math-medium verified 4m18s
21 ▶ [20] medium solved 1m46s
22 [27] hard solved 2m58s
23 ▶ [33] hard solved 2m33s
24 [M20] math-medium verified 1m05s
25 [M19] math-medium verified 1m09s
26 [M20] math-medium solved 1m10s
27 [M27] math-hard solved 4m11s
28 [M30] math-hard verified 1m22s
29 [M21] math-medium solved 47s
30 [M38] math-project solved 1m12s
31 [M40] math-project solved 14m30s
32 [M27] math-hard solved 12m33s
33 ▶ [M23] math-medium solved 4m19s
34 ▶ [M23] math-medium solved 26m37s
35 [M24] math-medium solved 12m05s
36 [M23] math-medium solved 3m43s
37 ▶ [M29] math-hard solved 2m31s
38 [M32] math-hard solved 6m20s
39 [M28] math-hard solved 12m51s
40 [M33] math-hard solved 3m51s
41 [M40] math-project solved 5m05s
42 ▶ [M20] math-medium verified 1m21s
43 [HM44] hm-project solved 1m06s
44 [M43] math-project solved 5m06s
45 [M43] math-project verified 4m25s
46 [M42] math-project solved 4m55s
47 [M25] math-medium solved 5m17s
48 ▶ [M21] math-medium solved 1m19s
49 [HM24] hm-medium solved 4m50s
50 [M20] math-medium verified 1m27s
51 [HM17] hm-medium solved 3m37s
52 [HM20] hm-medium verified 1m03s
53 [HM20] hm-medium verified 2m47s
54 [HM28] hm-hard solved 4m03s
55 [HM43] hm-project solved 5m
56 [HM43] hm-project solved 4m21s
57 [M47] math-research verified 1m33s
58 [M21] math-medium verified 1m16s
59 [M25] math-medium verified 2m37s
60 [M47] math-research solved 2m40s
61 [M46] math-research solved 4m39s
62 [M49] math-research solved 4m44s
63 [M25] math-medium verified 1m12s
64 [M41] math-project verified 2m41s
65 [20] medium verified 1m15s
66 [25] medium solved 9m25s
67 [M41] math-project solved 4m38s
68 [M41] math-project verified 1m09s
69 [M25] math-medium solved 4m16s
70 [HM43] hm-project solved 4m35s
71 [40] project verified 1m12s
72 ▶ [M28] math-hard solved 3m46s
73 [M26] math-hard verified 1m12s
74 [M29] math-hard verified 1m16s
75 [M26] math-hard verified 1m10s
76 ▶ [M21] math-medium verified 1m14s
77 [M22] math-medium solved 4m49s
78 [M26] math-hard verified 4m06s
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 1

The previous solution fails because it replaces MIX instruction semantics with an unsupported linear model and ignores control flow.
taocp mathematics algorithms volume-3 Medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 2

The previous solution fails because it never executes the MIX program in Table 1 and never derives an actual address from the algorithm.
taocp mathematics algorithms volume-3 Medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 3

The proposed program computes a hash address using only a very small and fixed portion of each key $K$, namely the characters accessed by the instructions $LDI\ K(1!:!1)$ or $LDIN\ K(4!:!1)$, $LD2\ K(...
taocp mathematics algorithms volume-3 Medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 4

Let $N = 365$ and let $n$ be the number of people.
taocp mathematics algorithms volume-3 Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 5

Let a FORTRAN identifier be a string $K = c_1 c_2 \dots c_n$ with $1 \le n \le 10$, and let the proposed hash function be h(K) = \text{leftmost byte of } K.
taocp mathematics algorithms volume-3 simple Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 6

In MIX arithmetic, the instruction `DIV d` interprets the concatenation $AX$ as a single signed integer formed with $A$ as the high-order word and $X$ as the low-order word.
taocp mathematics algorithms volume-3 simple Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 7

Let $F = \mathrm{GF}(2^n)$, and let $a \in F$ be an element of order $n$.
taocp mathematics algorithms volume-3 Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 8

We restart from the correct structure and avoid any use of invalid fractional-part algebra.
taocp mathematics algorithms volume-3 math-hard Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 9

Let $\theta \in (0,1)$ be irrational, and let the sequence of points ${n\theta}$ be inserted into $[0,1]$ as in Theorem S of Section 6.
taocp mathematics algorithms volume-3 math-hard Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 10

Let \[ S_j=\{\,\{n\theta+a_j\}:0\le n<N_j\,\},\qquad 1\le j\le d, \] and let \(S=\bigcup_{j=1}^d S_j\).
taocp mathematics algorithms volume-3 math-project Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 11

The proposed interchange is not valid in general, because it violates a dependency in the control flow of Program C.
taocp mathematics algorithms volume-3 Medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 12

We first recall the structure of Program C (linear probing) as given in the text.
taocp mathematics algorithms volume-3 Medium Jul 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 13

In Algorithm C (separate chaining) the hash table consists of \(M\) list headers.
taocp mathematics algorithms volume-3 Medium Jul 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 14

The previous solution fails because it replaces the problem with a partitioned memory model.
taocp mathematics algorithms volume-3 Medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 15

Let the hash table contain $M$ locations and let $N$ be the number of keys currently stored.
taocp mathematics algorithms volume-3 Medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 16

The computation performed by Program L does not fail arithmetically when $K = 0$.
taocp mathematics algorithms volume-3 simple Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 17

In double hashing with open addressing, a key $K$ is examined in the sequence of table positions h_1(K),\; h_1(K) + h_2(K),\; h_1(K) + 2h_2(K),\; \dots \pmod{M}, so that $h_2(K)$ determines the step s...
taocp mathematics algorithms volume-3 simple Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 18

The analysis of Program D in the text computes the average values of three key quantities,\(A\), \(S_1\), and \(C\),for the two alternative instruction sequences (30) and (31) that replace lines 10-13...
taocp mathematics algorithms volume-3 Medium Jul 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 19

The previous solution failed in two fundamental ways: it did not perform an empirical investigation and it misinterpreted the constraint $1 < h_2(K) < r$ for small $r$.
taocp mathematics algorithms volume-3 project Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 20

In the modified Algorithm D, step D3 sets c\leftarrow0, and each time step D4 is entered, the counter is first increased:
taocp mathematics algorithms volume-3 math-medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 21

No, the variable \(N\) should not be decreased.
taocp mathematics algorithms volume-3 Medium Jul 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 22

We work in the setting of Algorithm C, where each key $x$ is inserted into a singly linked chain for bucket $h(x)$ by _inserting at the head_.
taocp mathematics algorithms volume-3 Hard Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 23

We assume the chained hash table data structures as used in Algorithm C (Section 6.
taocp mathematics algorithms volume-3 Hard Jul 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 24

Let the sample space consist of all sequences $(K_1,\dots,K_7)$ of seven distinct keys chosen from the set of $MP$ possible keys, with each such sequence having equal probability under successive unif...
taocp mathematics algorithms volume-3 math-medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 25

Equation (39) expresses the probability that $N$ distinct keys $K_1,\dots,K_N$ hash into $N$ distinct table positions when each key is assumed to be mapped independently and uniformly into a hash tabl...
taocp mathematics algorithms volume-3 math-medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 26

Let the hash table be initially empty and let linear probing be used for collision resolution.
taocp mathematics algorithms volume-3 math-medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 27

The previous argument failed because it replaced both the definition of $s(n,\alpha,y)$ and Abel’s identity with unverified variants.
taocp mathematics algorithms volume-3 math-hard Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 28

Let $X_M$ denote the number of probes required for an unsuccessful search in a linear probing table of size $M$ containing $N$ stored keys.
taocp mathematics algorithms volume-3 math-hard Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 29

Working
taocp mathematics algorithms volume-3 math-medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 30

Let $a_1,\dots,a_n$ be the preferred parking positions, where each $a_j \in {1,\dots,n}$ and $n=m$.
taocp mathematics algorithms volume-3 math-project Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 31

A *parking sequence* (or *parking function*) of length $n$ is a sequence $a_1 a_2 \dots a_n$ with $1 \le a_i \le n$ such that when cars $1,2,\dots,n$ arrive in that order and each car $i$ parks in the...
taocp mathematics algorithms volume-3 math-project Jul 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 32

In the context of linear probing hashing (or the equivalent parking problem), let \(M\) be the table size (number of parking spaces).
taocp mathematics algorithms volume-3 math-hard Jul 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 33

Equation (51) gives the approximation \[ C_N \approx \frac{1}{2}\left(1 + \frac{1}{1-\alpha}\right) \] for the average number of probes in a successful search using Algorithm L (linear probing), where...
taocp mathematics algorithms volume-3 math-medium Jul 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 34

The $M^N$ hash sequences are equally likely, so each of the $N$ keys independently falls into any given list with probability $1/M$.
taocp mathematics algorithms volume-3 math-medium Jul 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 35

We consider the model of Exercise 34: \(N\) distinct keys are hashed independently and uniformly into \(M\) separate lists.
taocp mathematics algorithms volume-3 math-medium Jul 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 36

We consider the model of Exercise 34: a chained hash table with \(M\) lists, \(N\) keys already inserted, and the \(M^N\) hash sequences equally likely.
taocp mathematics algorithms volume-3 math-medium Jul 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 37

We consider a hash table with \(M\) buckets using separate chaining.
taocp mathematics algorithms volume-3 math-hard Jul 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 38

We consider a hash table with \(M\) buckets and \(N\) keys.
taocp mathematics algorithms volume-3 math-hard Jul 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 39

We consider Algorithm C, which is separate chaining.
taocp mathematics algorithms volume-3 math-hard Jul 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 40

We analyze Algorithm C (chaining) with a hash table of \(M\) lists and \(N\) keys already inserted.
taocp mathematics algorithms volume-3 math-hard Jul 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 41

Let $M$ be the table size and $N$ the number of occupied cells under simple uniform hashing, so that all $\binom{M}{N}$ occupied sets are equally likely.
taocp mathematics algorithms volume-3 math-project Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 42

Let $M$ be the number of hash addresses and let $n$ be the number of occupied cells at the moment a new key $K$ is inserted by Algorithm C.
taocp mathematics algorithms volume-3 math-medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 43

Let $N$ denote the number of items stored.
taocp mathematics algorithms volume-3 Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 44

The previous solution failed because it replaced the actual dependent probing process by an unjustified permutation model.
taocp mathematics algorithms volume-3 math-project Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 45

We restart from the actual stochastic structure of tertiary clustering and keep track of the dependence that was incorrectly removed in the previous solution.
taocp mathematics algorithms volume-3 math-project Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 46

Let the table size be $M$, with $n$ stored keys and load factor $p=n/M$.
taocp mathematics algorithms volume-3 math-project Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 47

Let the table have size $M$, with $n$ stored keys and load factor $\alpha=n/M$.
taocp mathematics algorithms volume-3 math-medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 48

We consider an open addressing hash table of size \(M\) containing \(N\) keys (\(0 \le N < M\)).
taocp mathematics algorithms volume-3 math-medium Jul 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 49

Let $K$ be the number of records in a fixed bucket.
taocp mathematics algorithms volume-3 hm-medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 50

By equation (42), the quantity $Q_o(M,N)$ satisfies Q_o(M,N) = 1 + \frac{N}{M} Q_o(M,N-1).
taocp mathematics algorithms volume-3 math-medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 51

Let $X(a,n)$ denote the random variable whose expectation is $R(a,n)$ as defined in (55).
taocp mathematics algorithms volume-3 Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 52

From equation (42), $Q_o(M,N)$ is given by the finite sum Q_o(M,N)=\sum_{k=0}^{N} \binom{N}{k}\frac{k!
taocp mathematics algorithms volume-3 hm-medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 53

The error in the proposed solution occurs at the change of variables and the resulting failure to preserve the structure needed for an incomplete gamma representation.
taocp mathematics algorithms volume-3 hm-medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 54

Start from Eq.
taocp mathematics algorithms volume-3 hm-hard Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 55

The previous argument failed at the very start because it assumed a functional equation without deriving the Schay–Spruth state recursion.
taocp mathematics algorithms volume-3 hm-project Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 56

Let $n = Mb$.
taocp mathematics algorithms volume-3 hm-project Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 57

Let the table have size $M$, and let $n$ records be present, so exactly $M-n$ locations are empty.
taocp mathematics algorithms volume-3 math-research Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 58

Uniform probing, in the sense of Theorem U, corresponds to generating a probe sequence by selecting a permutation of the table addresses ${0,1,2,3,4}$ uniformly from the set of all $5!$ permutations.
taocp mathematics algorithms volume-3 math-medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 59

Let $S_M$ be the set of all permutations of $\{0,1,\dots,M-1\}$, and let $\mathbb{P}$ be a probability assignment on $S_M$ that is equivalent to uniform probing in the sense of Theorem U.
taocp mathematics algorithms volume-3 math-medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 60

Let $M$ be the table size and let $n$ keys be stored, with load factor $\alpha = \frac{n}{M}.$ A single-hashing scheme assigns to each key $K$ a home address $h(K)\in{0,\dots,M-1}$, and associates wit...
taocp mathematics algorithms volume-3 math-research Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 61

The error in the previous solution is the assumption that column-wise uniformity of the permutations implies optimality of all coefficients $c_k$.
taocp mathematics algorithms volume-3 math-research Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 62

The previous solution incorrectly assumed that the cost functional decomposes as C_y = \frac{1}{M}\sum_K C(K), with each $C(K)$ depending only on the increment sequence assigned to $K$.
taocp mathematics algorithms volume-3 math-research Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 63

Let the hash table have $M$ locations.
taocp mathematics algorithms volume-3 math-medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 64

Let $M$ be the table size and $\alpha=n/M$.
taocp mathematics algorithms volume-3 Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 65

Let a variable-length key $K$ be a finite sequence of MIX characters $K = c_1 c_2 \dots c_\ell,$ where each $c_i$ is an element of a fixed alphabet of radix $r$ (for MIX, typically $r = 64$ or $r = 10...
taocp mathematics algorithms volume-3 Medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 66

Assume an open addressing scheme using Algorithm L or Algorithm D.
taocp mathematics algorithms volume-3 Medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 67

Linear probing with a full table and distinct home addresses is not governed by “cyclic inversion geometry” in the way the previous solution assumed.
taocp mathematics algorithms volume-3 math-project Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 68

Let $S_N = d_1 + d_2 + \cdots + d_N$.
taocp mathematics algorithms volume-3 Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 69

The review identifies three genuine failures: an unjustified symmetry factor, an unsupported intermediate bound, and a mismatch between the run decomposition and the claimed inequality.
taocp mathematics algorithms volume-3 math-medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 70

The key fix is to discard the incorrect “uniform random cycle” model and replace it with a correct symmetry argument for double hashing: the probe sequence is not uniform over all permutations, but it...
taocp mathematics algorithms volume-3 hm-project Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 71

Let $M$ denote the number of hash addresses and let $N$ denote the number of keys stored, with load factor $\alpha = \frac{N}{M}.$ Algorithm C is the separate chaining method described in Section 6.
taocp mathematics algorithms volume-3 project Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 72

Let $H$ be a matrix with $R$ rows and one column for every possible key $K$.
taocp mathematics algorithms volume-3 math-hard Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 73

Let $M$ be the range of hash values $\{0,1,\dots,M-1\}$.
taocp mathematics algorithms volume-3 math-hard Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 74

Let $H$ be a matrix whose rows are hash functions $h : \mathcal{K} \to {0,1,\dots,M-1}$, and whose columns correspond to keys.
taocp mathematics algorithms volume-3 math-hard Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 75

Let ${h_i}_{i=1}^R$ be independent random functions, each mapping the set of keys into ${0,1,\dots,M-1}$, and each value $h_i(K)$ is uniformly distributed over ${0,1,\dots,M-1}$ for every fixed key $K...
taocp mathematics algorithms volume-3 math-hard Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 76

Let a key $K$ be a variable-length sequence $K = (x_0, x_1, \dots, x_{\ell-1}),$ where each $x_i$ is an integer digit in ${0,1,\dots,r-1}$, and $\ell \ge 0$ depends on $K$.
taocp mathematics algorithms volume-3 math-medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 77

We address the two failures in the original argument: 1.
taocp mathematics algorithms volume-3 math-medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 78

Let $w>m>0$, $L=2^{w-m}$, and work modulo $2^w$.
taocp mathematics algorithms volume-3 math-hard Jun 29, 2026