Day 72:散列表——开放式寻址
18年11月5日 · 史二美—北京理工大学 1620 人阅读
散列表
上次我们学习解决冲突的方法叫做链表链接,这种方法有一些优点和缺点。虽然实现很简单,但是每个条目都需要大量额外的内存,而且其必须支持不同的数据结构。所以这次我们来学习一种全新的方法——开放式寻址。
这个想法非常直观。根据密钥的哈希代码查找存储桶。如果铲斗被占用,只需探测另一个铲斗。如果另一个也被占用,探测另一个直到你找到空闲的插槽。你应该探查哪个桶?这里可以会有各种各样的策略。线性探测迭代搜索[散列(密钥) + I ];对于i = 0.…n .二次探测搜索[散列(密钥) + i * * 2 ];对于I = 0.…n .我们也可以使用二级哈希函数在[哈希(密钥) +哈希2 (密钥,I )处搜索,对于i = 0……n。如果我们试图移除一把钥匙,我们不能简单地移除水桶。相反,桶必须标记为空,这样条目序列的探测不会被破坏。这里我们选择使用实现线性探测,这可能是开放式寻址技术中最糟糕的一种,然而,这是展示其缺点的最佳方法。过一会儿,开放式寻址往往会产生一长串连续的已占用存储桶。这种效应称为聚类,可能会明显降低哈希表的性能。
删除键值对其没有帮助,因为桶仍然被认为是被占用的,只被标记为空的(在图片中标记为o )。摆脱集群的唯一方法是重置表并重新散列所有条目。当然还有其他的一些探测方法来解决这个问题,比如说双重散列或二次探测,这些技术倾向于创建集群。
实现代码
测试
Python3Turtle