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