导入
链式散列表：使用链式处理冲突的哈希技术
检查你对哈希表的理解。
哈希表概述
哈希表是一种高效存储大量整数（来自范围 ）的方法，其中要存储的元素数量为 。术语 哈希表 包含一系列数据结构。最常见的两种实现方式是：
- 链式哈希（hashing with chaining）
- 线性探测（linear probing）
在实际应用中，哈希表通常用于存储非整数类型的数据。此时，每个数据项都会关联一个整数形式的 哈希码，并用该哈希码进行哈希操作。生成哈希码的方式有多种。
某些哈希方法需要在特定范围内随机选择整数。在代码示例中，这些“随机”整数被硬编码为常量。这些常量是通过大气噪声生成的随机位得到的。
ChainedHashTable 结构
ChainedHashTable 数据结构使用 链式哈希 方法，将数据存储在一个数组 t 中，该数组的每个元素是一个列表。同时维护一个整数 n，记录所有列表中元素的总数。如下图所示：
...
一个包含 n = 14 个元素、t.length = 16 的 ChainedHashTable 示例。在此例中 hash(x) = 6
初始化 ChainedHashTable 时，使用以下变量：
1class ChainedHashTable(BaseSet): 2 def __init__(self, iterable=[]): 3 self._initialize() 4 self.add_all(iterable) 5 6 def _initialize(self): 7 self.d = 1 8 self.t = self._alloc_table((1<
1
2数据项 x 的哈希值 hash(x) 是一个在 {0,...,t.length−1}\{0,..., \text{t.length}-1\}{0,...,t.length−1} 范围内的整数。所有哈希值为 i 的元素都存储在列表 t[i] 中。为了防止列表过长，我们维护以下不变量：
3n≤t.length\textcolor{Red}{n \leq \text{t.length}}n≤t.length
4从而保证每个列表中的平均元素数量不超过 n/t.length≤1n / \text{t.length} \le 1n/t.length≤1。
5向哈希表中添加元素 x 时，首先检查数组 t 的长度是否需要增加，如果需要则扩容。完成这一步后，计算 x 的哈希值 i（范围为 {0,…,\{0,\ldots,{0,…,t.length−1}-1\}−1}），并将 x 添加到列表 t[i] 中：
6class ChainedHashTable(BaseSet):
7 def __init__(self, iterable=[]):
8 self._initialize()
9 self.add_all(iterable)
10
11 def add(self, x):
12 if self.find(x) is not None: return False
13 if self.n+1 > len(self.t): self._resize()
14 self.t[self._hash(x)].append(x)
15 self.n += 1
16 return True
17必要时的扩容操作包括将数组长度翻倍，并将所有元素重新插入新表中。这种策略与 ArrayStack 的实现方式相同，其摊还成本为常数级：在一系列插入操作中，扩容的总成本是恒定的。
18除了扩容外，向 ChainedHashTable 添加新值 x 所做的其他工作仅包括将 x 追加到列表 t[hash(x)]。对于任何列表实现，这一操作的时间复杂度均为常数。
19从哈希表中删除元素 x 时，需要遍历列表 t[hash(x)]，直到找到 x 并将其移除：
20class ChainedHashTable(BaseSet):
21 def __init__(self, iterable=[]):
22 self._initialize()
23 self.add_all(iterable)
24
25 def remove(self, x):
26 ell = self.t[self._hash(x)]
27 for y in ell:
28 if y == x:
29 ell.remove_value(y)
30 self.n -= 1
31 if 3*self.n < len(self.t): self._resize()
32 return y
33 return None
34该操作的时间复杂度为 O(nhash(x))O(n_{\text{hash(x)}})O(nhash(x))，其中 nin_ini 表示存储在 t[i] 中的列表长度。
35查找元素 x 的过程类似：在列表 t[hash(x)] 上执行线性搜索：
36class ChainedHashTable(BaseSet):
37 def __init__(self, iterable=[]):
38 self._initialize()
39 self.add_all(iterable)
40
41 def find(self, x):
42 for y in self.t[self._hash(x)]:
43 if y == x:
44 return y
45 return None
46同样，该操作的时间复杂度与列表 t[hash(x)] 的长度成正比。
47哈希表的性能高度依赖于哈希函数的选择。一个好的哈希函数能将元素均匀分布到 t.length 个列表中，使得列表 t[hash(x)] 的期望长度为 O(n/t.length)=O(1)O(n / \text{t.length}) = O(1)O(n/t.length)=O(1)。相反，一个差的哈希函数可能将所有值（包括 x）映射到同一个位置，导致列表长度达到 n。下一节将介绍一种优良的哈希函数。
48乘法哈希
49乘法哈希 是一种基于模运算和整数除法的高效哈希值生成方法。它使用 div 操作符，该操作符返回商的整数部分并舍弃余数。形式上，对任意整数 a≥0a \ge 0a≥0 且 b≥1b \ge 1b≥1，有 a div b=⌊a/b⌋a \text{ div }b = \lfloor a/b \rfloora div b=⌊a/b⌋。
50在乘法哈希中，哈希表大小为 2d2^{d}2d（其中 d 称为 维度）。对整数 x∈{0,...,2w−1}x \in \{0,...,2^{w} − 1\}x∈{0,...,2w−1} 的哈希公式为：
51hash(x)=((z⋅x) mod 2w)div 2w−d\text{hash(x)} = ((z · x)\ \text{ mod}\ 2^{w}) \text{div}\ 2^{w-d}hash(x)=((z⋅x) mod 2w)div 2w−d
52其中 z 是从 {1,...,2w−1}\{ 1,...,2^{w} −1\}{1,...,2w−1} 中随机选取的一个奇数。该哈希函数可通过观察到的特性高效实现：默认情况下，整数运算已在模 2w2^{w}2w 下进行（w 为整数的位数）。如下图所示：
53
54注意：大多数编程语言（如 C、C#、C++ 和 Java）均如此。例外情况是 Python 和 Ruby，它们在发生溢出时会将固定长度的 www 位整数运算结果升级为可变长度表示。
55
56当 w = 32 且 d = 8 时，乘法哈希函数的运行过程如下：
57乘法哈希函数
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
872w(4294967296)100000000000000000000000000000000z (4102541685)11110100100001111101000101110101x (42)00000000000000000000000000101010z . x10100000011110010010000101110100110010(z . x) mod 2w00011110010010000101110100110010((z . x) mod 2w) div 2w-d00011110
88此外，整数除以 2w−d2^{w-d}2w−d 等价于在二进制表示中丢弃最右边的 w − d 位（这可以通过右移 w − d 位实现，使用 >>> 操作符）。因此，实现上述公式的代码比公式本身更简洁：
89class ChainedHashTable(BaseSet):
90 def __init__(self, iterable=[]):
91 self._initialize()
92 self.add_all(iterable)
93
94 def _hash(self, x):
95 return ((self.z * hash(x)) % (1<<w)) >> (w-self.d)
96以下引理（证明将在本节稍后给出）表明，乘法哈希能有效避免冲突：
97引理 1：设 xxx 和 yyy 是 {0,...,2w−1}\{0,...,2^{w} − 1\}{0,...,2w−1} 中任意两个不相等的值，则 Pr{hash(x)=hash(y)}≤2/2d\Pr\{\text{hash}(x) = \text{hash}(y)\} \le 2/2^{d}Pr{hash(x)=hash(y)}≤2/2d。
98利用引理 1，可以轻松分析 remove(x) 与 find(x) 的性能：
99引理 2：对于任意数据值 x，列表 t[hash(x)] 的期望长度至多为 nx+2n_{x} + 2nx+2，其中 nxn_{x}nx 是 x 在哈希表中的出现次数。
100证明：令 SSS 为哈希表中所有不等于 x 的元素构成的多重集合。对任意 y∈Sy \in Sy∈S，定义指示变量：
101Iy={1 if hash(x)= hash(y)0 otherwiseI_y =
102\begin{cases}
1031 \text{\ \ \ \ \ if hash$(x) = $ hash$(y)$}\\
1040 \text{\ \ \ \ \ otherwise}
105\end{cases}Iy={1 if hash(x)= hash(y)0 otherwise
106由引理 1 可知，E[Iy]≤2/2d=2/t.lengthE[I_y] \le 2 / 2^{d} = 2 / \text{t.length}E[Iy]≤2/2d=2/t.length。列表 t[hash(x)] 的期望长度为：
107 E[t[hash(x)].size()]=E[nx+∑y∈SIy]=nx+∑y∈SE[Iy]≤nx+∑y∈S2/t.lenght≤nx+∑y∈S2/n≤nx+(n−nx)2/n≤nx+2 \begin{split}
108\text{
109E[t[hash(x)].size()]} & =
110E \left[n_{x} + \sum_{y \in S} I_{y}\right] \\
111
112& = n_{x} + \sum_{y \in S} E[I_{y}] \\
113
114&
115\le n_{x} + \sum_{y \in S} 2/\text{t.lenght} \\
116
117&\le n_{x} + \sum_{y \in S} 2/n \\
118
119&\le n_{x} +(n-n_{x})2/n \\
120
121&\le n_{x} +2\
122\end{split} E[t[hash(x)].size()]=Enx+y∈S∑Iy=nx+y∈S∑E[Iy]≤nx+y∈S∑2/t.lenght≤nx+y∈S∑2/n≤nx+(n−nx)2/n≤nx+2
123结论得证。
124现在我们来证明引理 1，但在此之前需要一个数论结果。在后续证明中，我们使用记号 (br,...,b0)2(b_{r},...,b_{0})_{2}(br,...,b0)2 表示 ∑i=0rbi2i\sum_{i=0} ^{r} b_{i}2^{i}∑i=0rbi2i，其中每个 bib_{i}bi 是 0 或 1。换句话说，(br,...,b0)2(b_{r},...,b_{0})_2(br,...,b0)2 是二进制表示为 br,...,b0b_{r},...,b_{0}br,...,b0 的整数。我们用 ⋆\star⋆ 表示未知值的位。
125引理 3：设 SSS 为 {1,...,2w−1}\{ 1,...,2^{w} − 1 \}{1,...,2w−1} 中所有奇数的集合；设 qqq 和 iii 为 SSS 中任意两个元素。则存在唯一一个 z∈Sz \in Sz∈S，使得 zq mod 2w=izq \text{ mod }2^{w} = izq mod 2w=i。
126证明：由于 zzz 和 iii 的选择数量相同，只需证明满足 zq mod 2w=izq\ \text{mod}\ 2^{w} = izq mod 2w=i 的 z∈Sz \in Sz∈S 至多只有一个。
127假设存在两个这样的值 zzz 和 z′z^{\prime}z′，且 z>z′z > z^{\prime}z>z′。则
128q \ \text{mod}\ 2^{w} = i$$
129
130因此
131
132$$(z − z^{\prime}
133) q \ \text{mod} \ 2^{w} = 0$$
134
135这意味着
136
137\tag{1}(z − z^{\prime}
138) q \ =k2^{w}
139
140对某个整数 $k$ 成立。从二进制角度考虑，有
141
142(z − z^{\prime}) q \ =k \cdot (1,\underbrace{0,...,0}_{w}) \ _{2}
143因此 $(z − z^{\prime})q$ 的二进制表示中，末尾 $w$ 位均为 0。
144
145此外，$k \neq 0$，因为 $q \neq 0$ 且 $z − z^{\prime} \neq$ $0$。由于 `q` 是奇数，其二进制表示末尾没有 0：
146
147q = (\star,...,\star,1) \ _{2}
148
149由于 $|z − z^{\prime} | < 2^{w}$，$z − z^{\prime}$ 的二进制表示中末尾 0 的个数少于 `w` 个：
150
151z − z^{\prime} = (\star,...,\star,1,\underbrace{0,..,0}_{<w}) \ _{2}
152
153因此，乘积 $(z − z^{\prime}
154)q$ 的二进制表示中末尾 0 的个数也少于 `w` 个：
155
156(z − z^{\prime}
157) q \ =( \star,...,\star,1,
158\underbrace{0,...,0}_{<w}) \ _{2}
159
160因此 $(z − z^{\prime}
161)q$ 不可能满足 (1)，产生矛盾，证明完成。
162
163引理 3 的价值在于以下观察：若 $z$ 从 $S$ 中均匀随机选取，则 $zt$ 在 $S$ 上也是均匀分布的。在后续证明中，将 $z$ 的二进制表示视为 $w − 1$ 个随机位后接一个 1 会有所帮助。
164
165**引理 1 的证明**：首先注意到条件 $\text{hash}(x) = \text{hash}(y)$ 等价于“$zx$ mod $2^{w}$ 和 $zy$ mod $2^{w}$ 的最高 $d$ 位相同”。该条件的必要前提是 $z(x − y)$ mod $2^{w}$ 的最高 $d$ 位全为 0 或全为 1。即：
166
167\tag{2}z(x − y) \text{ mod} \ 2^{w}= (\underbrace {0,...,0}{d} , \underbrace {\star,...,\star}{w-d}) \ _{2}
168
169当 $zx$ mod $2^{w} > zy$ mod $2^{w}$ 时，或
170
171\tag{3}z(x − y) \text{ mod} \ 2^{w}= (\underbrace {1,...,1}{d} , \underbrace {\star,...,\star}{w-d}) \ _{2}
172
173当 $zx\ \text{mod} \ 2^{w} < zy \ mod\ 2^{w}$ 时。因此，我们只需限制 $z(x − y)\ \text{mod} \ 2^{w}$ 呈现 (2) 或 (3) 形式的概率。
174
175令 $q$ 为唯一的奇数，使得 $(x−y) \text{mod}\ 2^{w} = q2^{r}$（$r \ge 0$ 为整数）。根据引理 3，$zq\ \text{mod}\ 2^{w}$ 的二进制表示为 $w − 1$ 个随机位后接一个 1：
176
177zq \text{ mod} \ 2^{w}= \underbrace{(b_{w-1} ,...,b_1}_{w-1},1) \ _{2}
178
179因此，$z(x−y) \text{ mod } \ 2^{w} = zq2^{r}\text{ mod } 2^{w}$ 的二进制表示为 $w − r − 1$ 个随机位，后接一个 1，再接 $r$ 个 0：
180
181z(x − y)\ \text{mod} \ 2^{w}= zq2^r\ \text{mod} \ 2^{w} = (\underbrace {b_{w-r-1},...,b_{1}}{w-r-1} \ ,1, \underbrace {0,0,...,0)}{r}\ _2 \
182
183现在完成证明：若 $r > w − d$，则 $z(x − y)\ \text{mod } 2^{w}$ 的最高 $d$ 位中同时包含 0 和 1，因此其呈现 (2) 或 (3) 形式的概率为 0。若 $r = w − d$，则呈现 (2) 的概率为 0，而呈现 (3) 的概率为 $1/2^{d−1} = 2/2^{d}$（因为必须满足 $b_1,...,b_{d−1} = 1,...,1$）。若 $r < w − d$，则必须满足 $b_{w−r−1},...,b_{w−r−d} = 0,...,0$ 或 $b_{w−r−1},...,b_{w−r−d} = 1,...,1$。每种情况的概率为 $1/2^d$，且互斥，因此任一情况发生的概率为 $2/2^d$。证明完成。
184
185## 总结
186
187以下定理总结了 `ChainedHashTable` 数据结构的性能：
188
189**定理**：`ChainedHashTable` 实现了 `USet` 接口。忽略 `grow()` 调用的成本，`ChainedHashTable` 在每次操作 `add(x)`、`remove(x)` 和 `find(x)` 上的期望时间复杂度为 $O(1)$。
190
191此外，从空的 `ChainedHashTable` 开始，任意长度为 $m$ 的 `add(x)` 和 `remove(x)` 操作序列，所有 `grow()` 调用的总耗时为 $O(m)$。
192
193让我们创建一个 `ChainedHashTable` 实例，并使用 `add()` 方法添加一些值。
194
195<pre><code class=language-python>import random
196from utils import new_array
197from arraystack import ArrayStack
198from base import BaseSet
199
200# 位数
201w = 32
202
203class ChainedHashTable(BaseSet):
204 def __init__(self, iterable=[]):
205 self._initialize()
206 self.add_all(iterable)
207 # 初始化函数
208 def _initialize(self):
209 self.d = 1
210 self.t = self._alloc_table((1<<self.d))
211 self.z = self._random_odd_int()
212 self.n = 0
213 # 随机奇数生成器
214 def _random_odd_int(self):
215 return random.randrange(1<<w) | 1
216 # 重置函数
217 def clear(self):
218 self.d = 1
219 self.t = self._alloc_table((1<<self.d))
220 self.n = 0
221 # 创建数组栈的函数
222 def _alloc_table(self, s):
223 return [ArrayStack() for _ in range(s)]
224 # 调整大小的函数
225 def _resize(self):
226 self.d = 1
227 while (1 << self.d) <= self.n: self.d += 1
228 self.n = 0
229 old_t = self.t
230 self.t = self._alloc_table(1<<self.d)
231 for i in range(len(old_t)):
232 for x in old_t[i]:
233 self.add(x)
234 # 哈希中的整数除法函数
235 def _hash(self, x):
236 return ((self.z * hash(x)) % (1<<w)) >> (w-self.d)
237 # 添加值的函数
238 def add(self, x):
239 if self.find(x) is not None: return False
240 if self.n+1 > len(self.t): self._resize()
241 self.t[self._hash(x)].append(x)
242 self.n += 1
243 return True
244 # 删除值的函数
245 def remove(self, x):
246 ell = self.t[self._hash(x)]
247 for y in ell:
248 if y == x:
249 ell.remove_value(y)
250 self.n -= 1
251 if 3*self.n < len(self.t): self._resize()
252 return y
253 return None
254 # 查找值的函数
255 def find(self, x):
256 for y in self.t[self._hash(x)]:
257 if y == x:
258 return y
259 return None
260 # 迭代器函数
261 def __iter__(self):
262 for ell in self.t:
263 for x in ell:
264 yield x
265
266if __name__ == "__main__":
267 # 初始化变量
268 n = 10
269 # 创建对象
270 t = ChainedHashTable()
271 # 添加值
272 print("添加值")
273 for i in range(n):
274 t.add(i*2)
275 print("查找值")
276 for i in range(2*n):
277 x = t.find(i)
278 if i % 2 == 0:
279 assert x == i
280 else:
281 assert x is None
282 print("哈希表中的值：")
283 for x in t:
284 print(x)</code></pre>
285
286**说明**
287
288我们从 `main.py` 文件的 `main()` 函数开始解释：
289
290- **第 74 行**：声明变量 `n`，用于确定添加到哈希表中的元素数量。
291- **第 76 行**：创建 `ChainedHashTable` 的新实例 `t`。
292- **第 79–80 行**：循环使用 `add()` 方法将 `i * 2` 添加到哈希表中。
293- **第 82–83 行**：使用 `find()` 方法在哈希表中查找 `i`。
294- **第 84–87 行**：若 `i` 为偶数，则检查哈希表中的值是否等于 `i`；若 `i` 为奇数，则检查值是否为 `None`。
295- **第 89–90 行**：遍历哈希表并打印每个值。