[科普中国]-线性探测

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

简介与二次探测和双散列一样，线性探测是一种开放寻址的策略。在这些策略里，散列表的每个单元都存储一对键值对。当散列函数对一个给定值产生一个键，并且这个键指向散列表中某个已经被另一个键值对所占用的单元时，线性探测用于解决此时产生的冲突：查找散列表中离冲突单元最近的空闲单元，并且把新的键插入这个空闲单元。同样的，查找也同插入如出一辙：从散列函数给出的散列值对应的单元开始查找，直到找到与键对应的值或者是找到空单元。

正如Thorup和张寅在2012年所写，…“散列表是最常用的普通数据结构，它在硬件上的标准实现中最流行的方法就是使用线性探测。线性探测又快又简单。”线性探测能够提供高性能的原因是因为它的良好的引用局部性，然而它与其他解决散列冲突的策略相比对于散列函数的质量更为敏感。当使用随机散列函数，5-independent散列函数或tabulation散列函数，其用于搜索，插入或删除的预期时间是常数。不过，借由其他像是私语杂凑的散列函数可以在实作中达到较好的结果。1

操作杂凑冲突一般发生于杂凑函数将一个键丢进已经含有另一个不同键的单元中的时候。线性探测是一个用来解决冲突的策略，其将新键丢进最靠近的下一个空单元中。

搜索为了搜索给定的键 x，散列表中由h(x)对应的单元开始的相邻单元h(x) + 1,h(x) + 2, ..., 都将被检查，直到找到了内容为空的单元或是找到了存储给定键为x的单元。其中，h是散列函数。如果找到了存储给定键的单元，搜索将会返回单元中存储的键对应的值。否则，如果搜索遇到了空的单元，键在表中就不存在，因为键应当被存放在所有未被搜索的单元之前。此时，搜索返回表中无此键的结果。2

插入为了在表中插入一对键值对(x,v)（有可能会替换有着相同键的键值对），插入算法也会访问搜索算法访问的同一系列单元，直到找到一个空的单元，或是找到了存储给定键为x的单元。新的键值对将会存储在此单元中。

如果插入将导致表（占用单元的比例）增长高于某个预设的阈值的负载系数，整个表可以通过一个新的表（规模大于本表规模）和一个新的散列函数来代替，如使用动态数组。设置这个的阈值接近于零，并使用表大小的高增长率来带来更快速的哈希表的操作，但相比于接近一个阈值与低增长率，它会带来更高的内存使用情况。一个常见的选择是表规模扩大一倍，当负载系数将超过1/2，导致负载系数保持在1/4和1/2之间。2

删除当一对键值对被删除，可能会有必要将其他的键值对放回到它的单元中，来防止搜索时搜索到空的单元。

散列表应当提供删除键值对的功能。然而，单纯地清空对应的单元是不够的。这会影响到对于储存时间早于该单元、但储存位置在该单元之后的其他键。此单元会造成搜索获得错误的结果，告诉使用者这些键并不存在。

相较于直接清空对应单元i，更好的做法是先清空，然后把它之后所有会造成问题的单元向前移动，来避免搜索出错。重复直到出现空单元，则删除动作安全完成。但是，如果有发现后续有键可以移到这个位置上的话，直接将该键取代欲删除的单元可以加速后续的其他行为，当然，这样也会造成后面多出一个新的空单元。搜索可用来取代的单元的动作会持续到搜索到原本就空白的单元为止。在这个将键移到前面的过程中，所有的键都会被算过一遍。因此，完成这整个过程所需的时间与该储存位置的单元数量呈正比，与杂凑表的其他运算相符。

有一种可行的替代方案是懒惰删除，用指向欲删除键的特殊的标志值（flag value）取代原本的键值配对。不过，这些标志值在搜索上会当作非空。因此，如果一个阵列中有过多的被删除键，那么就需要清除所有的标志值并且重新杂凑整个表。2

本词条内容贡献者为:

王慧维 - 副研究员 - 西南大学