线性探测法

线性探测是计算机程序解决散列表冲突时所采取的一种策略。散列表这种数据结构用于保存键值对，并且能通过给出的键来查找表中对应的值。线性探测这种策略是在1954年由Gene Amdahl, Elaine M. McGraw,和 Arthur Samuel 所发明，并且最早于1963年由Donald Knuth对其进行分析。

接下来说点实际的吧，线性探测法是哈希函数的一种，用来增删改查相关的数据。这里进行举例说明，见下图：

这里是一个长度为9的队列，假设要放入是数字10、13、6、19。
对第一个数字10进行取模运算，10mode9 ，他的下标为1，就把10 放到1那个地方。
接下来第二个数字13,13mode9 得到的结果是4，那么就把13放到下标为4的地方。
第三个数字为6， 6mode9得到的是6，就把6放到下标为6那个地方。
最后一个数字为19， 19mod9为1，但是下标1的地方已经由内容了，就往后挪一个下标，也就是2这个地方。下标为2的地方没有存储值，就把19放到2这里。

如果下标超过队列长度，那么从头开始，直到队列填满

上述过程就是线性探测法的计算过程，按照这个思路转换到代码当中，在符合场景的情况下写出对应的逻辑代码。

当队列没有可插入的地址之后需要新增比现有的队列长度要长的队列，当哈希表数据存储量超过百分之七十的时候简历新的哈希表，新表通常是旧表的二倍以上，最好是一个质数，然后把之前就得数据再次通过哈希计算搬到新的表格当中。

关于在此队列进行删除的部分请看下文，摘选自百度百科：

删除
当一对键值对被删除，可能会有必要将其他的键值对放回到它的单元中，来防止搜索时搜索到空的单元。
散列表应当提供删除键值对的功能。然而，单纯地清空对应的单元是不够的。这会影响到对于储存时间早于该单元、但储存位置在该单元之后的其他键。此单元会造成搜索获得错误的结果，告诉使用者这些键并不存在。
相较于直接清空对应单元i，更好的做法是先清空，然后把它之后所有会造成问题的单元向前移动，来避免搜索出错。重复直到出现空单元，则删除动作安全完成。但是，如果有发现后续有键可以移到这个位置上的话，直接将该键取代欲删除的单元可以加速后续的其他行为，当然，这样也会造成后面多出一个新的空单元。搜索可用来取代的单元的动作会持续到搜索到原本就空白的单元为止。在这个将键移到前面的过程中，所有的键都会被算过一遍。因此，完成这整个过程所需的时间与该储存位置的单元数量呈正比，与杂凑表的其他运算相符。
有一种可行的替代方案是懒惰删除，用指向欲删除键的特殊的标志值（flag value）取代原本的键值配对。不过，这些标志值在搜索上会当作非空。因此，如果一个阵列中有过多的被删除键，那么就需要清除所有的标志值并且重新杂凑整个表。

这篇好文章是转载于：学新通技术网