散列函数
字符串散列函数通常基于字符串中的字符计算出一个整数，然后按照取模得到散列值。
int hash1(const std::string& key) {
int hash = 0;
for (auto c: key) {
hash += c;
}
return hash;
}
函数 hash1 的缺点是不够均匀。字符的 ASCII 码在 65 到 95 之间。假设键由 8 个字母组成，hash1 生成的散列码在 520 到 760 之间。如果散列表长度超过 1000，这个散列码太集中了，碰撞的概率较大。如果散列表长度小于 100，hash1 还是一个不错的选择。
一个更好的方式是将字符作为多项式系数。
class String implements Serializable, Comparable {
// ...
public int hashCode() {
int h = 0;
for (int i = 0; i < len; i++) {
h = 31 * h + charAt(i);
}
return h;
}
}
long hash(char* key) {
long h = 0;
while (*key != '\0') {
h = (h << 4) + *(key++);
long g = h & 0xF0000000L;
if (g != 0) {
h ^= g >>> 24;
}
h &= ~g;
}
return h;
}
处理碰撞的方法：
- 线性探测（linear probing）。
- 双散列法（double hashing）。
- 随机散列（random hashing）。
- seperate chaining。
线性探测法插入：
- 假设散列表的长度为M。计算索引 index = H(K)。
- 如果 table[index] 包含键 K，结束。
- 如果 table[index] 空闲，插入键，结束。
- 如果发生碰撞，令 index = (index + 1) % M。如果 index == H(K)，散列表满，抛出异常。否则跳转到步骤 2。
线性探测法查找：
- 计算索引 index = H(K)。
- 如果 table[index] 包含键 K，返回 FOUND。
- 如果 table[index] 空闲，返回 NOT-FOUND。
- 令 index = (index + 1) % M。如果 index == H(K)，返回 NOT-FOUND。否则跳转到步骤 2。
线性探测法会导致散列码相同的多个键聚集在一起。为了避免这种情况，可以采用双散列法。双散列法引入了第 2 个散列函数 H2(K)。H2(K) 的值域是 [1,M-1]。当发生冲突是，通过 H2(K) 计算下次探测的位置。如果将 H2(K) 的值始终为 1，这时算法退化为线性探测。
双散列法查找：
- 计算索引 index = H(K)。
- 如果 table[index] 包含键 K，结束。
- 如果 table[index] 空闲，插入键，结束。
- 如果发生碰撞，令 offset = H2(K)，令 index = (index + offset) % M。如果 index == H(K)，散列表满，抛出异常。否则跳转到步骤 2。
如果 M 是素数，H2(K) 可以定义为 H2(K) = 1 + ((K / M) mod (M - 1))。对于 M 是素数的情况，双散列法表现良好。
随机散列使用伪随机数生成器（pseudorandom number generator）计算散列码。对于相同的种子，伪随机数生成器会生成同样的伪随机数序列。随机散列使用键K作为种子进行初始化，根据生成的伪随机数作为下一个探测地址。
随机散列查找：
- 使用键K初始化伪随机数生成器 RNG。计算索引 index = RNG.next() % M。
- 如果 table[index] 包含键 K，结束。
- 如果 table[index] 空闲，插入键，结束。
- 如果发生碰撞，令 index = RNG.next() % M。如果所有地址都探测过，抛出异常。否则跳转到步骤 2。
随机散列的缺点在于生成伪随机数的成本较高，因此使用得不多。
重读一遍。 http://cseweb.ucsd.edu/~kube/cls/100/Lectures/lec16/lec16-27.html http://cseweb.ucsd.edu/~kube/cls/100/Lectures/ 参考资料 http://cseweb.ucsd.edu/~kube/cls/100/Lectures/lec16/lec16-12.html
大于20000000的最小素数：200000033。 大于2000000的最小素数：2000003。