C语言实现一个简易的Hash table(7)

发布时间:2019-08-06 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了C语言实现一个简易的Hash table(7)脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。

上一章我们讲了如何根据需要动态设置hash表的大小,在第四章中,我们使用了双重哈希来解决hash表的碰撞,其实解决方法有很多,这一章我们来介绍下其他方法。

本章将介绍两种解决hash表碰撞的方法:

  1. 拉链法
  2. 开放地址法

拉链法

使用拉链法,每一个bucket都会包含一个链接表,当发生碰撞时,就会将该记录插入在该位置的链接表后面,步骤如下:

  • 插入时:通过hash函数获取到要插入的位置,如果该位置是空的,就直接插入,如果该位置不是空的,就插入在链接表的后面
  • 搜索时:通过hash函数获取到key对应的位置,遍历链接表,判断key是不是搜索的key,如果是,则返回value,否则返回NULL
  • 删除时:通过hash函数获取到key对应的位置,遍历链接表,找到需要删除的key,如果找到,则将该key对应的记录从链接表中删除,如果链接表中只有一条记录,则将该位置置为NULL

拉链法的优点是实现起来简单,但是空间利用率低。每个记录必须存储指向链接表中下一个记录的指针,如果没有记录,则指向NULL,这种方法会浪费一些空间来存储额外的指针。

开放地址法

开放地址法能解决拉链法空间利用率低的问题,发生碰撞时,碰撞的记录将放置在hash表中的其他bucket中,存放的位置是根据预先确定的规则选择的,以便在搜索记录时可以重复该规则,有如下几种规则:

@H_360_92@线性探查

当发生碰撞时,就会递增索引,将记录插入在下一个可用的索引中,方法如下:

  • 插入时:通过hash函数找到插入的位置的索引,如果这个位置是空的,直接插入,如果不为空,就递增索引,直到找到索引指向的位置是空的为止,然后执行插入
  • 搜索时:通过hash函数找到搜索的记录的索引,每次递增索引,并比较索引指向的值是否是要搜索的值,如果索引指向的是空,则返回NULL
  • 删除时:通过hash函数找到删除的记录的索引,每次递增索引,直到找到要删除的那个key后执行删除

线性探测提供了良好的缓存性能,但是存在碰撞后遍历次数多的问题。将发生碰撞key放入下一个可用的bucket中可能导致后面插入记录也要往后插,就需要多次迭代。

二次探查

二次探查法和先行探查类似,不同的是,发生碰撞后,我们会将记录插入在如下的序列中:i, i + 1, i + 4, i + 9, i + 16, ...i代表通过hash函数获取到的索引,具体步骤如下:

  • 插入时:通过hash函数找到插入的索引,通过遍历上面的序列直到找到一个空的或已被删除的索引位置,执行插入
  • 搜索时:通过hash函数找到key的索引,遍历上面的序列,将序列上的key与搜索的key对比,如果相等,则返回value,否则返回NULL
  • 删除时:因为我们无法判断要删除的项是不是碰撞链上的,所以我们不能直接删除该条记录,只能把它标记为已删除

二次探查法减少发生碰撞后遍历的次数,并且仍然提供了不错的缓存性能。

双重hash

双重hash旨在解决碰撞后遍历次数多的问题。使用两次hash函数为插入的记录选择新的索引,这个索引会均匀的分布在整个表中,该方法虽然解决了上述问题,但也失去了缓存特性,双重hash是实际项目中常见的冲突管理方法,也是我们在本教程中实现的方法。

上一章:设置hash表大小

脚本宝典总结

以上是脚本宝典为你收集整理的C语言实现一个简易的Hash table(7)全部内容,希望文章能够帮你解决C语言实现一个简易的Hash table(7)所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。