教你从零开始写一个哈希表--哈希冲突

哈希函数把一个无穷大的输入集合映射到一个有限大小的输出集合。

哈希函数把一个无穷大的输入集合映射到一个有限大小的输出集合。不同的关键字可能会被映射到同一个数组下标，如此一来就导致了哈希冲突。哈希表必须实现解决冲突的方法。我们的哈希表将使用开放地址法和再散列法。在桶索引冲突后，再散列法会使用两个哈希函数来计算键值对将要保存的桶索引值。有关其他哈希冲突的解决方法，请查看附录。

再散列法

索引i冲突后应该使用的新的索引位置根据下面的函数给出： index = hash_a(string) + i * hash_b(string) % num_buckets 我们看到，如果没有哈希冲突的发生，i=0。此时，桶索引是字符串的hash_a值。如果发生了冲突，索引将由hash_b进行调整。有种可能是，hash_b返回了0，导致i*hash_b(string)%num_buckets也返回了0。这会使得哈希表不停的向同一个桶中插入键值对。我们可以通过对第二个哈希的结果加一来避免这种情况，以确保第二个项的结果不会是0。 index = (hash_a(string) + i * (hash_b(string) + 1)) % num_buckets

具体实现

1
2
3
4
5
6
7
8


// 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;
}

上一篇:教你从零开始写一个哈希表–哈希函数 下一篇:教你从零开始写一个哈希表–接口

文章目录

再散列法