Open Hashing 和 Closed Hashing

数据结构演示地址：
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