算法导论11.3 Exercises 答案

发表于 2023-01-24 更新于 2023-07-03 分类于算法导论阅读次数：本文字数： 3.5k 阅读时长 ≈ 3 分钟

11.3-1

优点在于，如果字符串的哈希值已经预先计算了出来，那么为了判断两个字符串是否相等，可以以$O(1)$的时间复杂度判断哈希值是否相等来完成。如果是为了将字符串插入哈希表，那么就不需要直接以$O(n)$的时间对字符串进行比对，从而可以快速判断两个字符串是否相等。对于哈希表而言，则可以通过哈希值快速定位到槽，而不需要直接为这个字符串划分一个槽。

11.3-2

这个计算哈希值的过程由下面的算法CAL-HASH给出。

CAL-HASH(S, r, m)
  h = 0
  for i = 1 to r
    // 将字符S[i]看成是一个无符号7比特数。
    h = (h * 128 + S[i]) mod m
  return h

变量$h$表示这个字符串的哈希值。由于$S$可以看成是一个$r$位$128$进制数，那么以$i$个字符为前缀的字符串哈希值$h_i$可以由$h_{i-1}$计算出，即$h_i=(128h_{i-1}+S[i])\bmod m$，最终$h_n$是这个字符串的哈希值。

11.3-3

按照题目11.3-2的算法，以$i$个字符为前缀的字符串哈希值$h_i$可以由$h_{i-1}$计算出，即$h_i=(2^p\cdot h_{i-1}+S[i])\bmod (2^p-1)=(h_{i-1}+S[i])\bmod(2^p-1)$。

按照上面的算法，可以得知空字符串的哈希值$h_0=0$。因此$\displaystyle{h_i=\left(\sum_{j=1}^i S[i]\right)\bmod (2^p-1)}$。也就是说，这个哈希算法计算出的哈希值是所有$p$位二进制数之和对$2^p-1$取模的值，失去了对$S$中字符的顺序的特征。因此，如果字符串$x$是字符串$y$的一个置换，那么它们的哈希值相同，因为使用的字母是完全相同的。

例如字符串$x=[245,148,15,159],y=[148,159,245,15],p=8$。两个字符串计算出来的哈希值均为$57$。

11.3-4

$\begin{aligned} h(61)&=\left\lfloor 1000 \cdot\left(61\cdot\dfrac{\sqrt{5}-1}{2}\bmod 1\right)\right\rfloor&=700\\ h(62)&=\left\lfloor 1000 \cdot\left(62\cdot\dfrac{\sqrt{5}-1}{2}\bmod 1\right)\right\rfloor&=318\\ h(63)&=\left\lfloor 1000 \cdot\left(63\cdot\dfrac{\sqrt{5}-1}{2}\bmod 1\right)\right\rfloor&=936\\ h(64)&=\left\lfloor 1000 \cdot\left(64\cdot\dfrac{\sqrt{5}-1}{2}\bmod 1\right)\right\rfloor&=554\\ h(65)&=\left\lfloor 1000 \cdot\left(65\cdot\dfrac{\sqrt{5}-1}{2}\bmod 1\right)\right\rfloor&=172\\ \end{aligned}$

11.3-5

由于函数簇$\mathscr{H}$是$\epsilon$-全域的，因此对于所有$a,b\in U,a< b$，都有$\Pr\{h(a)=h(b)\}\le \epsilon$。

假设$n(a,b),a,b\in U$表示元素$a$和$b$在$\mathscr{H}$中发生的碰撞次数，那么有$\displaystyle{n(a,b) =\sum_{h\in \mathscr{H}}[h(a)=h(b)]\le \epsilon\cdot |\mathscr{H}|}$。其中$[]$为示性函数，如果里面的表达式值为真，那么为$1$，否则为$0$。

那么对于所有不同的元素对$(a,b),a< b$，在$\mathscr{H}$中的总碰撞次数为$C$，那么有

\[C=\sum_{a,b\in U,a<b} n(a,b)\le \epsilon\cdot |\mathscr{H}|\cdot \dfrac{|U|\cdot(|U|-1)}{2}\le\epsilon\cdot |\mathscr{H}|\cdot \dfrac{|U|^2}{2}\qquad(1)\]

令$c(h)$表示在函数$h\in\mathscr{H}$中发生碰撞的元素对数，那么有$\displaystyle{c(h)}=\sum_{a,b\in U,a< b}[h(a)=h(b)]$。根据$C$的定义，同样有$\displaystyle{C=\sum_{h\in\mathscr{H}} c(h)}$。

对于某个哈希函数$h\in \mathscr{H}$，只有当$|U|$个$U$中的键尽量均匀地映射到$Q$时，总碰撞次数才最小。这相当于将$|U|$个元素划分成$|Q|$个集合，并且尽可能均匀的划分。

令$|U|=k\cdot |Q|+b,k\ge 0,b\in\{1,2,3,\dots,|Q|\}$。在最均匀的划分情况下，一共有$b$个集合，这些集合的大小为$k+1$，其余$|Q|-b$个集合，每个大小为$k$。那么不难计算出$c(h)$的下界，有

$\begin{aligned} c(h)&\ge b\cdot \dbinom{k+1}{2}+(|Q|-b)\cdot\dbinom{k}{2}\\ &=\dfrac{(k-1)k}{2}\cdot |Q|+kb\\ &=\dfrac{(|U|-b)(|U|-|Q|+b)}{2} &\qquad(A)\\ &=\dfrac{b(|Q|-b)}{2|Q|}+\left(\dfrac{|U|^2}{2|Q|}-\dfrac{|U|}{2}\right)\\ &\ge \dfrac{|U|^2}{2|Q|}-\dfrac{|U|}{2} \end{aligned}$

其中步骤$(A)$代入了$k=\dfrac{|U|-b}{|Q|}$。根据$c(h)$的值，有

\[C=\sum_{h\in\mathscr{H}} c(h)\ge |\mathscr{H}|\cdot \left(\dfrac{|U|^2}{2|Q|}-\dfrac{|U|}{2}\right)\qquad(2)\]

结合$(1),(2)$两个不等式，得到$|\mathscr{H}|\cdot \left(\dfrac{|U|^2}{2|Q|}-\dfrac{|U|}{2}\right)\le \epsilon\cdot |\mathscr{H}|\cdot \dfrac{|U|^2}{2}$，最终化简得到$\epsilon\ge\dfrac{1}{|Q|}-\dfrac{1}{|U|}$。

那么得到不等式$$

$\star$ 11.3-6

假设这任意不同的两个$d$元组为$a=\langle a_0,a_1,\dots,a_{d-1}\rangle,a'=\langle a_0',a_1',\dots,a_{d-1}'\rangle$，其中，不同是指$\exist i\in[0,d),a_i\neq a_i'$）。令$F(b)=(h_b(a)-h_b(a')) \bmod p$，那么有

\[F(b)=\left(\sum_{i=0}^{d-1}(a_i-a_i')b^i\right)\bmod p\]

可以看出，$F(b)$仍然是一个至多为$d-1$次项的多项式。考虑方程$F(b)=0$的解，根据题目31.4-4的结论，这个方程最多有$d-1$个不同的解。也就是说，最多有$t-1$个不同的$b\in \mathbb{Z}_p$，使得$h_b(a)=h_b(a')$成立。

那么，由于函数簇$\mathscr{H}$一共有$p$个函数，即$b$取遍集合$\mathbb{Z}_p$的值，因此，对于所有不同的$d$元组对$a,a'$，有$\Pr\{h_b(a)=h_b(a')\}\le \dfrac{d-1}{p}$。因此函数簇$\mathscr{H}$是$\dfrac{d-1}{p}$-全域的。

11.3-1

11.3-2

11.3-3

11.3-4

11.3-5

\(\star\) 11.3-6