哈希表学习笔记

Tags:

• Algorithm
• Blog

解决冲突的两种方法

分离连接法

散列表的装填因子（load factor）为散列表中元素的个数与散列表大小的比值。表的大小并不重要，装填因子才是最重要的。 分离连接散列的一般法则是使得表的大小尽量与预料的元素个数差不多（换句话说，装填因子 ≈ 1）

开放定址法

在开放定址散列算法系统中，如果有冲突发生，那么就要尝试选择另外的单元。h0(x), h1(x), … 逐个尝试

其中 hi(x) = (hash(x) + F(i)) mod tableSize，其中F(i)是解决冲突的方法。一般来说，开放定址法的散列算法其装填因子 lambda <= 0.5

定理证明

将乘法运算转换成位运算

令 $F(0) = 0$ 且 $F(i) = F(i - 1) + 2 \cdot i - 1$ ，则 $F(i) = i ^ 2$ 。

证明过程:

$$F(0) = 0$$

$$F(1) = F(0) + (2 \cdot 1) - 1$$

$$F(0) + F(1) + F(2) + ... + F(i) = 0 + F(0) + (2 \cdot 1) - 1 + (2 \cdot 2) - 1 + ... + F(i-1) + (2 \cdot i) - 1$$

$$F(i) = (2 \cdot 1) - 1 + (2 \cdot 2) - 1 + ... + (2 \cdot i) - 1$$

$$F(i) = 1 + 3 + 5 + ... + 2 \cdot i - 1$$

$$F(i) = \frac{1+2 \cdot i-1}{2} = i^2$$

这样就将一个乘法运算转换成了一个位移运算，提高了效率。

平方探测法总可向空间大于1/2的哈希表中插入元素

相关定理：

• $(a+b) \mod n = (a \mod n + b \mod n) \mod n$
• $(a \mod n) \mod n = a \mod n$

定理说明

如果使用平方探测，且表的大小是素数，那么当表至少有一半为空的时候，总能够插入一个新的元素

证明

• 前提说明

哈希表大小为ts，我们向其中插入了两个冲突的元素x和y。这两个元素冲突重试的次数分别是i和j。其中：

$$0 < i, j < \frac{ts}{2}$$

（小于 $\frac{ts}{2}$ 意味着表中还有多余一半的空间可以使用）

$$P_x = (Hash(x) + i^2) \mod ts$$

（$x$ 位置）

$$P_y = (Hash(y) + j^2) \mod ts$$

（$y$ 位置）

$$Hash(x) \mod {ts} = Hash(y) \mod {ts} => (Hash(x) - Hash(y)) \mod ts = 0$$

其中 $ts$ 是素数。

试证明，如果$i \neq j$ ，那么$P_x \neq P_y$

• 证明过程

假设上述定理是不成立的，则$i \neq j$ 时，$P_x = P_y$

$$P_x = P_y$$

$$(Hash(x) + i^2) \mod ts = (Hash(y) + j^2) \mod ts$$

$$(Hash(x) + i^2) \mod ts - (Hash(y) + j^2) \mod ts = 0 \mod ts$$

$$(Hash(x) + i^2 - Hash(y) - j^2) \mod ts = 0$$

$$[(Hash(x) - Hash(y)) \mod ts + (i^2 - j^2) \mod ts] \mod ts = 0$$

$$(i^2 - j^2) \mod ts = 0$$

• 因为$i, j < \frac{ts}{2}$ ，所以$(i^2 - j^2) <= \frac{(ts-1)^2}{4} - \frac{(ts-2)^2}{4} <= \frac{ts}{2} - \frac{3}{4} < ts$

• 因为ts是素数，所以$(i^2 - j^2) = 0$ ，可得$i=\pm j$

• 因为$0 < i, j$ ，所以$i = j$

与已知矛盾，故可得当$i \neq j$ 时，$P_x \neq P_y$ 。

可证明 如果使用平方探测，且表的大小是素数，那么当表至少有一半为空的时候，总能够插入一个新的元素

• 额外说明

根据 $K^2 \cdot [(ts - 1)^2 - (ts - 2)^2] < ts$ 可得$K < \frac{\sqrt{3} \cdot ts}{3}$ ，i, j更精确的范围是$0 < i, j < \frac{\sqrt{3} \cdot ts}{3}$ 。