Open Hashing 和 Closed Hashing
2020-10-28 本文已影响0人
我犟不过你
数据结构演示地址：
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
冲突解决技术可以分为两类：
Open Hashing开散列方法, 又叫拉链法
Closed Hashing闭散列方法, 又叫开地址法 （Open Addressing）
这两种方法的不同之处在于：开散列法把发生冲突的关键码存储在散列表主表之外，而闭散列法把发生冲突的关键码存储在表中另一个槽内
Open Hashing
开散列方法的一种简单形式是把散列表中的每个槽定义为一个链表的表头。散列到一个特定槽的所有记录都放到这个槽的链表中。
举个例子：
有一个长度为13的哈希表
image.png
通过key%哈希表长度取余，找到放置key的位置。例如放置30，则30%13 = 4。
image.png
添加相同hash值的key时，放入一个82，结果如下图
image.png
发现存在相同key的hash值时，在数组的该槽位上生成了一个单向链表，用于解除哈希冲突问题。
Closed Hashing
闭散列方法, 又叫开地址法，当发生哈希冲突时，如果该哈希表还没有被填满，那么就把该元素放到哈希表的下一个空闲的位置。
举个例子：
长度为29的哈希表
image.png
通过key%哈希表长度取余，找到放置key的位置。例如放置30，则30%29 = 1。
image.png
再次放置一个余1的key，放置59，59%29 = 1。
image.png
发现相同哈希值的key被放在了下一个空闲的位置。
Closed Hashing，Using Buckets
该方法是在开地址的方法上，做了处理，相当于变相增加了容量。
如下图，分割了11个桶，每个桶内部又分出三个位置，用于存储相同的key的hash值，当三个存满后会将溢出值放入最后的overflow溢出区。
image.png
连续存入4个100，100%11 = 1，存入三个100在1区，最后一个放在溢出区。
image.png
