Hash-Table-P04.rst

Part 04 - 处理碰撞

目录

• 4.1 - 双重散列
• 4.2 - 代码实现

哈希函数将无限数量的输入映射到有限数量的输出。 不同的输入键会映射到相同的数组索引， 导致桶冲突。 哈希表必须实现一些处理冲突的方法。

我们的哈希表将使用一种称为双散列开放寻址的技术来处理冲突。 双散列使用两个散列函数来计算在 i 次碰撞后应存储项目的索引。

有关其他类型碰撞解决方案的概述， 请参见 附录。

4.1 - 双重散列

在 i 次碰撞后应该使用的索引由下式给出：

index = hash_a(string) + i * hash_b(string) % num_buckets

我们看到， 如果没有发生冲突， i = 0， 所以索引只是字符串的 hash_a。 如果发生冲突， hash_b 会修改索引。

hash_b 有可能返回 0， 将第二项减少到 0。 这将导致哈希表一遍又一遍地尝试将项目插入到同一个桶中。 我们可以通过将第二个哈希的结果加 1 来缓解这种情况， 确保它永远不会为 0。

index = (hash_a(string) + i * (hash_b(string) + 1)) % num_buckets

4.2 - 代码实现

// hash_table.c
static int ht_get_hash(
    const char* s, const int num_buckets, const int attempt
) {
    const int hash_a = ht_hash(s, HT_PRIME_1, num_buckets);
    const int hash_b = ht_hash(s, HT_PRIME_2, num_buckets);
    return (hash_a + (attempt * (hash_b + 1))) % num_buckets;
}

下一节： 哈希表方法