线性探测 线性探测是计算机程序解决散列表冲突时所采取的一种策略散列表这种数据结构用于保存键值对并且能通过给出的键来查找表中对应的值线性探测这种策略是在年由Gene Amdahl Elaine M McGraw英语Elaine M McGraw和 亞瑟李塞謬爾 所发明并且最早于年由Donald Knuth对其进行分析 与二次探测英语Quadratic probing和双散列一样线性探测是一种开放寻址英语Open addressing的策略在这些策略里散列表的每个单元都存储一对键值对当散列函数对一个给定值产生一个键并且这个键指向散列表中某个已经被另一个键值对所占用的单元时线性探测用于解决此时产生的冲突查找散列表中离冲突单元最近的空闲单元并且把新的键插入这个空闲单元同样的查找也同插入如出一辙从散列函数给出的散列值对应的单元开始查找直到找到与键对应的值或者是找到空单元 正如Thorup和張寅在年所写散列表是最常用的普通数据结构它在硬件上的标准实现中最流行的方法就是使用线性探测线性探测又快又简单线性探测能够提供高性能的原因是因为它的良好的引用局部性然而它与其他解决散列冲突的策略相比对于散列函数的质量更为敏感当使用随机散列函数 independent散列函数英语Kindependent hashing或tabulation散列函数英语Tabulation hashing其用于搜索插入或删除的预期时间是常数不過藉由其他像是私語雜湊的散列函數可以在實作中達到較好的結果