数据结构中的溢出处理
对于新对（键，元素）已满，主存储桶发生溢出。
我们可能会解决
以某种系统的方式在哈希表中搜索未满的存储桶。
线性探测（线性开放寻址）。
二次探测。
随机探测。
通过允许每个存储桶保留其为本地存储桶的所有对的列表来消除溢出。
数组线性列表。
链。
执行开放寻址以确保所有元素都直接存储在哈希表中，因此它尝试解决冲突以实现各种方法。
通过将数据放入表中的下一个空槽来执行线性探测，以解决冲突。
线性探测的性能
最坏情况的查找/插入/擦除时间是θ(m)，其中m被视为表中的对数。
当所有对都在同一群集中时，会发生这种情况。
线性探测问题
标识符倾向于聚集在一起
邻近集群趋于合并
增加或延长搜索时间
二次探测
线性探测搜索桶（H(x)+i2）％b;H(x)表示x的哈希函数
二次探测将i的二次函数实现为增量
检查铲斗H(x)，（H(x)+i2）％b，（H(x)-i2）％b1==i<=(b-1)/2
b表示为4j+3形式的质数，j是整数
随机探测
随机探测执行随机数合并。
H(x):= (H’(x) + S[i]) % b S[i] is a table along with size b-1 S[i] is indicated as a random permutation of integers [1, b-1].