[科普中国]-线性开型寻址散列

线性开型寻址散列，也称开放寻址法，有的元素都存放在散列表里，每个表项或包含动态集合的一个元素或者NIL。当查找某个元素时，要系统的检查所有表项，直到找到所有的元素或者最终查明元素不在表中。为了使用开放寻址法插入一个元素，需要连续的检查散列表，或称为探查(probe)，直到找到一个空槽来放置待插入的关键字为止。检查的顺序不一定是0,1,2…m的顺序序列，而是依赖于待插入的关键字。

简介散列表也称作哈希表，是根据记录的关键字进行直地址运算，进而进行数据访问的一种数据结构．散列表地址转换的基本思路为：定义一个记录的关键字与地址之间的一种映射关系，通过这个映射关系，根据关键字直接计算出记录的地址．通常，记录关键字用key表示，用h表示关键字和记录地址间的函数关系，即为散列函数，记录的地址用h(key)表示。两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上，该现象称为冲突或碰撞发生冲突的两个关键字称为该散列函数的同义词。线性开型寻址散列是一种处理散列碰撞的方法，当发生碰撞时，线性探测法检查散列表中的下一个位置是否为空。如果为空，就将数据存入该位置；如果不为空，则继续检查下一个位置，直到找到一个空的位置为止1。

该散列方法的思想在于：插入一个关键字k，如果k被占用，则往后一个位置插入， 直到没有空间。与链接法相比，不需要指针，所以可以将指针所占用的空间存放更多的槽。缺点在于：该方法的删除操作，如果删除了某个关键字后，无法检索到以后的关键字了。如果用一个特定的值代替，查找时间就不依赖于转载因子α了。定义一个均匀散列的假设：每个关键字的探查序列等可能的为0，1…,m-1中的m!中排列的一种。

当查找一个元素时，要检查所有的表项，直到找到所需的元素，或者最终发现元素不在表中。不像在链接法中，这里没有链表，也没有元素存放在散列表外。在这里散列表有可能会被填满，但是装载因子（动态集合元素/散列槽数）绝对不会大于1。在开放寻址法中，当要插入一个元素时，可以连续地检查散列表的个各项，直到找到一个空槽来放置这个元素为止。检查顺序可以是线性的，可以是二次的，也可以是再次散列的。

查找关键字和插入关键字的算法基本上是一样的。

在开放寻址法中，对散列表元素的删除操作执行起来比较困难。当我们从槽i中删除关键字时，不能仅将NIL置于其中来标识它为空。因为这样做的话，会导致在插入另外的关键字探查过程中，有可能无法检索某些关键字。这里有一个解决方法，就是在槽i中置一个特定的槽当作空槽，从而可以插入新元素。

1.线性探查给定一个普通的散列函数h’:U->{0,1,2…m-1}(称为辅助散列函数)，线性探查方法采用的散列函数为：h(k,i)=(h’(k)+i) mod m , i=0,1,2,…m-1

给定一个关键字k，第一个探查的槽是T(h’(k)),接下来探查下一个槽，直到T[m-1]。

线性探查方法比较容易实现，但存在一个问题，成为一次群集。随着时间的推移，连续被占用的槽不断增加，平均查找时间也随着不断增加。群集现象很容易出现，这是因为当一个空槽前有i个满的槽时，该空槽为下一个将被占用的槽的概率是(i+1)/m，连续被占用的槽的序列将会变得越来越长，因而平均查找时间也会随之增加。2.二次探查（quadratic probing）采用的形式如下：

h(k,i)=(h’(k)+c1i+c2i^2)modm

其中h’是一个辅助散列函数，c1和c2为辅助常数，i=0,1,…m-1。初始的探查位置为T[h’(k)],后续的探查位置要在此基础上加上一个偏移量，该偏移量是以二次的方式依赖于探查号i的。如果两个关键字的初始探查位置是相同的，那么他们的后续二次探查的序列也是相同的。这种性质会导致一种程度较轻的群集现象，成为二次群集。3.双重散列是用在开放寻址法的最好方法之一，因为它所产生的排列具有随机选择的排列的许多特性。它采用如下形式的散列函数：

h(k,i)=(h1(k)+i*h2(k))modm

其中h1和h2是辅助散列函数。初始探查位置为T[h1(k)],后续的探查位置在此基础上加上偏移量h2(k)模m。与线性探查和二次探查不同的是，这里的探查序列以两种方式依赖于k，因为初始探查位置和偏移量都可能发生变化。

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

John Smith和Sandra Dee（都被杂凑映射到了单元873）的冲突，借由把后者放在下一个空闲单元（单元874）而解决

与二次探测和双散列一样，线性探测是一种开放寻址的策略。在这些策略里，散列表的每个单元都存储一对键值对。当散列函数对一个给定值产生一个键，并且这个键指向散列表中某个已经被另一个键值对所占用的单元时，线性探测用于解决此时产生的冲突：查找散列表中离冲突单元最近的空闲单元，并且把新的键插入这个空闲单元。同样的，查找也同插入如出一辙：从散列函数给出的散列值对应的单元开始查找，直到找到与键对应的值或者是找到空单元。正如Thorup和张寅在2012年所写，…“散列表是最常用的普通数据结构，它在硬件上的标准实现中最流行的方法就是使用线性探测。线性探测又快又简单。”线性探测能够提供高性能的原因是因为它的良好的引用局部性，然而它与其他解决散列冲突的策略相比对于散列函数的质量更为敏感。当使用随机散列函数， 5-independent散列函数或tabulation散列函数，其用于搜索，插入或删除的预期时间是常数。不过，借由其他像是私语杂凑的散列函数可以在实作中达到较好的结果。

二次探测是计算机编程中用于解决哈希表中冲突的开放寻址方案- 当传入数据的哈希值表明它应该存储在已占用的槽或桶中时。二次探测通过获取原始哈希索引并添加任意二次多项式的连续值直到找到开放时隙来进行操作。二次探测在封闭散列表中可以是更有效的算法，因为它可以更好地避免线性探测可能发生的聚类问题，尽管它没有免疫力。它还提供了良好的内存缓存，因为它保留了一些引用的位置 ; 然而，线性探测具有更大的局部性，因此具有更好的高速缓存性能。

双散列是一种计算机编程技术，用于散列表中以解决散列冲突，在要搜索的两个不同值产生相同散列键的情况下。它是开放式地址哈希表中一种流行的冲突分辨率技术。双散列在许多流行的库中实现。与线性探测一样，它使用一个哈希值作为起始点，然后重复前进一个间隔，直到找到所需的值，到达空位置，或者搜索整个表格; 但是这个间隔是使用第二个独立的散列函数决定的（因此名称为双重散列）。与线性探测和二次探测不同，间隔取决于数据，因此映射到同一位置的偶数值具有不同的桶序列; 这可以最大限度地减少重复碰撞和聚类的影响。

冲突两个不同的关键字，由于散列函数值相同，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。发生冲突的两个关键字称为该散列函数的同义词(Synonym)。

安全避免冲突的条件

最理想的解决冲突的方法是安全避免冲突。要做到这一点必须满足两个条件：

①其一是|U|≤m

②其二是选择合适的散列函数。

这只适用于|U|较小，且关键字均事先已知的情况，此时经过精心设计散列函数h有可能完全避免冲突。

冲突不可能完全避免

通常情况下，h是一个压缩映像。虽然|K|≤m，但|U|>m，故无论怎样设计h，也不可能完全避免冲突。因此，只能在设计h时尽可能使冲突最少。同时还需要确定解决冲突的方法，使发生冲突的同义词能够存储到表中。

冲突的频繁程度除了与h相关外，还与表的填满程度相关。

设m和n分别表示表长和表中填人的结点数，则将α=n/m定义为散列表的装填因子(Load Factor)。α越大，表越满，冲突的机会也越大。通常取α≤1。对于大多数应用程序来说，装填因子为0.75是比较合理的。

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所