脚本宝典收集整理的这篇文章主要介绍了

[译]C语言实现一个简易的Hash table(4)

脚本宝典小编觉得挺不错的,现在分享给大家,也给大家做个参考,希望能帮助你少写一行代码,多一份安全和惬意。

上一章我们解释了Hash table中最重要的hash函数,并用伪代码和C语言实现了一个我们自己的hash函数hash函数碰撞是无法避免的,当发生碰撞时我们改如何有效的处理呢?这章我们就来讲解下。

处理碰撞

hash函数中将无限大的输入映射到有限的输出中,当不同的输入映射到相同的输出时,就会发生碰撞,每个的hash表都会采用不同的方法来处理碰撞

我们的哈希表将使用一种称为开放地址的双重哈希的技术来处理冲突。双重哈希使用两个散列函数来计算在发生碰撞后存储记录的索引。

双重哈希

i发生碰撞后我们使用如下方式来获取索引:

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

当没有发生碰撞时,i=0,所以索引就是hash_a的值,发生碰撞后,hash_a的结果就需要经过一次hash_b的处理。

hash_b可能会返回0,将第二项减少到0,这就导致hash表会将多个记录插入到同一个bucket中,我们可以在hash_b的结果后加1来处理这种情况,确保它永远不会为0

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

算法实现

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

上一章:hash函数
下一章:完成Hash表API

总结

以上是脚本宝典为你收集整理的

[译]C语言实现一个简易的Hash table(4)

全部内容,希望文章能够帮你解决

[译]C语言实现一个简易的Hash table(4)

所遇到的程序开发问题,欢迎加入QQ群277859234一起讨论学习。如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典网站推荐给程序员好友。 本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。

80%的人都看过