开放寻址——线性探测

开放寻址——线性探测

分离链接散列算法还有一个亟待解决的缺点：需要指针，由于给新单元分配地址需要时间，这就导致了速度减慢，所以不太好。还有，因为链表是次第关联的结构，实现算法的代码自身的复杂程度和出错概率会大大增加。而只要采用这种策略，就很难保证每组冲突的词条在空间上能够彼此毗邻，因为动态分配的节点在内存里不一定是连续的，这样一来会导致一个致命缺陷：对于稍大规模的词条集合，查找中将做大量的I／O操作，无法利用系统预先缓存，导致效率低下。

因此或许我们应该放弃这种策略，并反其道而行之，仅仅依靠基本的散列表结构，就地排解冲突反而是更好的选择。也就是采用所谓的开放定址策略，它的特点在于：散列表所占用的空间在物理上始终是地址连续的一块，相应的所有的冲突都在这块连续空间中加以排解。而无需向分离链接那样申请额外的空间。对！所有的散列以及冲突排解都在这样一块封闭的空间内完成。

因此相应地，这种策略也可以称作为闭散列。如果有冲突发生，就要尝试选择另外的单元，直到找到一个可供存放的空单元。具体存放在哪个单元，是有不同优先级的，优先级最高的是他原本归属的那个单元。从这个单元往后，都按照某种优先级规则排成一个序列，而在查找的时候也是按着这个序列行进，每个词条对应的这个序列被称为探测序列or查找链。

抽象来说，就是我们遇到冲突后，会相继尝试h0(x),h1(x),h2(x)这些单元，其中hi(x)= ( Hash( x ) + F ( I ) ) % ，并且约定F(0)=0，F（x）是解决冲突的方法，就是刚才说的那个“优先级规则”。因为所有的数据都要放在这块空间，所以开放定址所需要的表规模比分离链接要大。通常而言开放定址法的装填因子应该低于0.5。而根据对不同F(x)的选择，学界划分出三种常用的探测序列：线性探测法、平方探测法、双散列

1.线性探测法

在线性探测法中，函数F是关于i的线性函数，典型的情形是F(i)=i。这相当于逐个探测每个单元（必要时可以绕回）以查找出一个空单元。下面显示了将{89,18,49,58,69}插入到一个散列表中的情况（竖着看），使用了和之前一样的散列函数hash(x)=x%size，他们有冲突怎么办？用F(i)=i这个方法，每次从i=0开始尝试，那么根据hi(x)= ( Hash( x ) + F ( I ) ) % 就可以计算出各自不相冲突的地址了。完美！（暂时的）

我们脑内单步调试一下：第一个冲突在49产生:（49+0）=9，被89占了，那接着往后试，i=1，（49+1）=0，空的，放入这个空闲地址，这个地址是开放的。58依次和18,89,49产生冲突，试选三次后才找到一个空单元。对69的冲突也如此解决，一旦冲突，试探紧邻其后的单元，直至找到空单元or抵达散列表末尾。线性探测序列0->1->2->3在物理上保持连贯性的，具有局部性，这样一来系统的缓存作用将得到充分发挥，而对于大规模的数据集，这样一来更是可以减少I/O的次数。只要表足够大，总能找到一个空闲单元，但是这太费时间了。更糟的是——就算一开始空闲区域多，经过多次排解冲突后，数据所占据的单元也会开始形成一些区块，聚集在一起，被称为一次聚集( )，但在前面动机篇里说过，散列函数的初衷是避免数据扎堆，所以后面必须改进。

那么总体看来散列到区块的任何关键字都需要多次试选单元才能解决冲突，然后被放到对应的那个区块里。下面做一个总结

优点：

无需附加空间（指针、链表、溢出区）

探测序列具有局部性，可以利用系统缓存，减少IO

缺点：

耗费时间>O(1)

冲突增多——以往的冲突会导致后续的连环冲突，发生惨烈的车祸

光看这个图可能没什么感觉，举个例子吧，这样感触更深。我们开一个size=7的散列表，也保证了size是素数。把{0，1，2，3，7}，就按这个顺序依次插入。前四个数都没问题，依次插入没有冲突。

但是为了插入7，我们先试探0发现非空，往后走，依次试探1,2,3都非空，直到4可以放进去。

在这个散列表的生存期里只有1个发生冲突。看似很棒对吧，再来看另一插入次序：{7，0，1，2，3}。

插入7没问题，但插入0的时候就有冲突了，实际上自此之后每一个数插入都会遇到冲突，前后对比可以看出，第二种插入顺序发生的很多冲突本来是可以避免的。这个时候想必我们改进这种策略的意愿就十分迫切了。

要支持词条的删除则需要格外的小心，现在我们来做一探讨。按照线性探测的规则，先后插入彼此冲突的一组词条都将存放在同一个查找序列中，而更确切的讲：它们应该按照逻辑次序构成整个查找链的一个前缀，其中不得有任何的空桶缝隙。因此词条的删除操作需要做额外的一些处理，如果我们不做一些事先准备，直接将词条删除（就类似对于链表，删除节点的时候不做链条调整，而直接free那个单元，那不直接凉了），就会造成查找链断裂，后续词条丢失——明明存在但访问不到。

对于这种连续空间的单元删除，一个直观的构想是：将后续词条悉数取出，再重新插入。但这太特么慢了，时间复杂度爆炸。其实对于这个问题有一种典型的处理手法：lazy ，仅做一个删除标记，比如里面预留一个del变量，设置为TRUE。

那么在日后查找中，遇到他之后就应该越过继续往后查找而不是在此返回。在插入时遇到，就把它视作一个空单元，数据覆盖即可。应该说针对开放定址策略，懒惰删除不仅是“不得已而为之”的方法，甚至可以说是针对这种情况的最优方法。因为毕竟在开放定址策略中，每一个桶单元都同时属于多个查找链

开放寻址散列的分析：

定理11.6 ：

一个装载因子a=n/m 推论11.7

平均情况，向一个装载因子为a的开放寻址散列表中插入一个元素时，至多需要做1/(1-a)次探查。假设采用的是均匀散列。

定理11.8

给定一个装载因子为a

#include "iostream"
#include "math.h"
#define Null -1
#define DELETED -2
using namespace std;//散列函数（全域散列在“全域散列解决哈希冲突中已讲”）
int Hash_div(int val, int m)//除法求余。val值，m为槽的个数(是一个不为2的幂的质数)
{return val % m;
}int Hash_multi(int val, int m)//乘法散列。m一般为2的某次幂
{double A = (sqrt(5) - 1) / 2;return ((val*A - int(val*A)) * m);
}//开放寻址方法：线性探查、二次探查、双重探查
int Line_Prob(int val, int m, int i) //m为槽的个数(是一个不为2的幂的质数),m越大查找次数就越少
{return (Hash_div(val, m) + i) % m;
}int Twice_Prob(int val, int m,int i)
{int c1 = 1, c2 = 3;return (Hash_div(val, m) + c1 * i + c2 * i*i) % m; //其中常数c1,c2,m的值的选择是受限制的
}
int Double_Probe(int val, int m, int i)
{return (Hash_div(val, m) + i * (1 + Hash_div(val, m-1))) % m; //其中m为质数，还可以选择m为2的幂,并设置一个总产生奇数的hash_div2
}
int hash_insert1(int T[], int m, int k)
{int i = 0;do{int j = Line_Prob(k, m, i);//这里可以替换成二次，双重探查。插入，查找，删除函数同时被替换if (T[j] == Null || T[j] == DELETED){T[j] = k;return j;}else i++;} while (i != m);cerr << "hash table overflow" << endl;
}
int hash_search(int T[], int m, int k)
{int i = 0, j = 0;do{j = Line_Prob(k, m, i);//这里可以替换成二次，双重探查。插入，查找，删除函数同时被替换if (T[j] == k){return j;}else i++;} while (T[j] != Null || i != m);return Null;
}
void hash_delete(int T[], int m, int k)
{int j = hash_search(T, m, k);//首先先找到该关键字kif (j != Null){T[j] = DELETED;//如果找到了，那么设置其为空。cout << "删除成功！" << endl;}else cout << "待删除的数据不在表中！" << endl;
}
void Display(int T[],int m)
{cout << "散列表信息显示:"  ;for (int i = 0; i < m; i++){cout << T[i] << " ";}cout << endl;
}
void main()
{int a[9] = { 10,22,31,4,15,28,17,88,59 };int T[19] = { 0 };for (int i = 0; i<19; i++){T[i] = Null;}for (int i = 0; i<9; i++){hash_insert1(T, 19, a[i]);}Display(T,19);hash_delete(T, 19, 10);Display(T, 19);system("pause");
}