关于我的 Leetcode 题目解答，代码前往 Github：https://github.com/chenxiangcyr/leetcode-answers
使用场景：快速查找，删除，判重。
Hash 函数的选择
Simple Hash Function：
- Division Method:
h(k) = k mod m（如果 m 取合数，例如 2 的幂，直接求余会导致分布不均匀，容易出现冲突。） - Knuth Variant on Division:
h(k) = k*(k + 3) mod m
注意：bucket 长度 m 应该为素数，且不接近 2 的幂和 10 的幂。
Hash Sequence of Characters 对字符串求哈希：
每个字符 char 可以表示为一个 8 bit 的 int，因此字符串可以表示为 int 数组，即
K = K1 K2 ... Kn n 为字符串长度
- CRC Variant:
令结果 h 为 32 位整数。
// 依次遍历 K1 K2 ... Kn
for earh Ki
highorder = h & 0xf800000; // 取前5位，因为字符虽然是8位的ASCII码，但是主要信息集中在后5位
h = h << 5;
h = h ^ (highorder >> 27)
h = h ^ Ki
- Java String 的 hashCode 实现：
public int hashCode() {
int h = hash;
if (h == 0 && count > 0) {
int off = offset;
char val[] = value;
int len = count;
for (int i = 0; i < len; i++) {
h = 31*h + val[off++];
}
hash = h;
}
return h;
}
可见实际可以看作是一种权重的算法，在前面的字符的权重大。
这样有个明显的好处，就是前缀相同的字符串的hash值都落在邻近的区间。
Hash 碰撞处理
-
Open Hashing 拉链法
- 对每一个哈希地址建立一个单链表
- 搜索时，先计算哈希地址，然后搜索单链表
-
Closed Hashing 开地址法
- 不建立单链表，如果 h(key) 对应的位置已被占用，则查找下一个空的位置，其包括：
- 线性探测法，即
h(key) + 1 - 伪随机法，即
h(key) + 随机值
- 线性探测法，即
- 不建立单链表，如果 h(key) 对应的位置已被占用，则查找下一个空的位置，其包括：
2-left Hashing
将哈希表分成相等的两半，分别指派哈希函数 h1 和 h2。
对一个 key，得到两个地址 h1(key) 和 h2(key)，哪一个位置已存储的 key 比较多，就将新的 key 存储到负载小的位置。
Perfect Hashing 完美哈希
设定义域为 X，n = |X|，值域为 Y，m = |Y|。
- 如果
k1 != k2，则h(k1) != h(k2)，则h为完美哈希，即没有冲突 - 如果在上面的基础上，并且
m == n，则h为最小完美哈希，即一一映射。
