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