线性探测的实现
 
目录:
一.线性探测的概念
二.线性探测原理
三.功能性接口
1.构造
2.insert
3.Capacity
4.Swap
5.find
6.erase
  
 

 
目录:
 
一.线性探测的概念
 
 
 
 我们在这里讲到的线性探测是解决哈希冲突中闭散列的一种方式 
 
 
 
 
 闭散列：也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。
 ~
 线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。
 
 
二.线性探测原理
 
 
 
 
 闭散列解决哈希冲突的方法就是将元素后移,存放到为空的位置去. 
 
 
三.功能性接口
 
1.构造
 
enum STATE{		//创建一个枚举

	EXIST,		//存在状态
	DELETE,		//假删除状态
	EMPTY		//空状态
};

template<class K, class V>
struct HashNode{	//创建哈希结构体保存对应的KV键值对,并且将这个表的初始状态变为空

	pair<K, V> _kv;
	STATE _state = EMPTY;
};

//顺序表实现hash
template<class K, class V>
class HashTable{		//hash创建

public:
	typedef HashNode<K, V> Node;		//定义别名

	HashTable(size_t n = 10)		//构造函数构造缺省值为10
		:_hTable(n)
		, _size(0)		//存在元素改为0
	{}
 
2.insert
 
 
 
 步骤:
 1.计算插入元素的哈希位置
 2.判断对应的位置是否有元素存在
 3.有元素则向后遍历找空存放
 4.无元素则直接存放 
 
 
	bool insert(const pair<K, V>& kv){

		//0.判断容量是否够用
		checkCapacity();	//调用函数
		//1.计算哈希位置
		int idx = kv.first%_hTable.size();

		//2.判断key是否存在
		while (_hTable[idx]._state != EMPTY){

			//如果当前位置数据有效,且key相同
			if (_hTable[idx]._state == EXIST
				&&kv.first == _hTable[idx]._kv.first)
			{
				return false;
			}
			//继续搜索
			++idx;
			if (idx == _hTable.size())
				idx = 0;
		}
		//插入
		_hTable[idx]._kv = kv;
		_hTable[idx]._state = EXIST;
		++_size;

		return true;
	}
 
3.Capacity
 
 
	void checkCapacity(){
	
		//负载因子: < 1
		//存在的元素/容量  0.7
		if (_hTable.size() == 0 || _size * 10 / _hTable.size() >= 7){//当内部的元素存储超过7成的时候就开辟新的表

			//开新表
			int newC = _hTable.size() == 0 ? 10 : 2 * _hTable.size();	//创建出对应的二倍的空间
			HashTable<K, V> newHt(newC);

			for (int i = 0; i < _hTable.size(); ++i){		//在for循环内部

				//插入状态为exist的数据
				if (_hTable[i]._state == EXIST)	//将内部存在的元素
				{
					newHt.insert(_hTable[i]._kv);	//依次在新表里面进行插入
				}
			}
			Swap(newHt);	//交换新表和旧表
		}
	}
 
4.Swap
 
	void Swap(HashTable<K, V>& Ht){	//这里的交换就是让新的表指向对应的位置,容量进行交换

		swap(_hTable, Ht._hTable);
		swap(_size, Ht._size);

	}
 
5.find
 
 
 
 步骤:
 1.按照查找位置计算所在的位置
 2.如果对应的kv键值对是完全对应的,则直接输出
 3.如果没有找到,则继续向后进行遍历 
 
 
	Node* find(const K& key){

		//计算对应的位置
		int idx = key%_hTable.size();	//先找出所在元素在哈希表中的位置
		while (_hTable[idx]._state != EMPTY){		//判断对应的位置是否有元素的存在

			if (_hTable[idx]._state == EXIST
				&& key == _hTable[idx]._kv.first)	//如果元素存在且对应的键值相互对应
			{
				return &_hTable[idx];	//则找到,直接输出
			}
			++idx;	//没找到则向后遍历
			if (idx == _hTable.size())	
			//如果遍历到最后一个位置没有找到,则变为0从第一个重新开始查找
			{
				idx = 0;
			}
		}
		return nullptr;	//实在没有找到则直接返回空
	}
 
6.erase
 
 
 
 步骤:
 1.找到对应的元素进行删除
 2.注意这里的删除是假删除,元素还存在,只不过将其置为DELETE状态
 3.这里的假删除是为了在插入的时候可以正常的插入. 
 
 
	bool erase(const K& key){

		Node* node = find(key);
		if (node){

			//假删除
			--_size;
			node->_state = DELETE;
			return true;
		}
		return false;
	}


private:
	vector<Node> _hTable;
	size_t _size;	//有效元素的个数
};
 
 
 
 这就是对于线性探测的实现,主要对于它产生哈希冲突的时候是如何解决的理解. 
 

5.给定一个关键字序列（13，4，18，20，32，15，9，24），哈希表长度为 11，哈希函数为 H(Key)=Key%11，采用线性探测法解决冲突，画出构造的哈希表（8 分），并求出等概率查找时查找成功 的 ASL（成功） （1 分），与查找不成功的 ASL（不成功） （1 分）
 
 
线性探测： H(Key)=Key%11 余数为key所在的位置，如果改位置有值，那么填入下一个位置
 
成功的asl：每一个key填入哈希表所需要查询的次数的次数之和的平均
 
失败的asl：每一个key与下一个空位的距离之和的平均

 
线性探测法的查找函数
 
题目
答案
思路

 
题目
 

 
 
 
 
 
答案
 
Position Find( HashTable H, ElementType Key )
{
	int i,flag=0;
	i=Hash(Key,H->TableSize);
	while(H->Cells[i].Info!=Empty&&H->Cells[i].Data!=Key)
	{
		if(i==H->TableSize&&flag==0)
		{
			i=0;
			flag=1;
		}
		else if(i==H->TableSize) return ERROR;
		else i++;
	}
	return i;
}
 
思路
 
在通过Hash函数获取Key的第一位置后，在从这个位置遍历Cell数组，如果第一遍没找到，flag变量赋值1，再给它一次机会（因为它有可能是从中间向后遍历，前面的还没遍历），找到了就返回对应的位置，否则返回ERROR

开放寻址——线性探测
 
https://www.cnblogs.com/hongshijie/p/9419387.html
 分离链接散列算法还有一个亟待解决的缺点：需要指针，由于给新单元分配地址需要时间，这就导致了速度减慢，所以不太好。还有，因为链表是次第关联的结构，实现算法的代码自身的复杂程度和出错概率会大大增加。而只要采用这种策略，就很难保证每组冲突的词条在空间上能够彼此毗邻，因为动态分配的节点在内存里不一定是连续的，这样一来会导致一个致命缺陷：对于稍大规模的词条集合，查找中将做大量的I／O操作，无法利用系统预先缓存，导致效率低下。
 
因此或许我们应该放弃这种策略，并反其道而行之，仅仅依靠基本的散列表结构，就地排解冲突反而是更好的选择。也就是采用所谓的开放定址策略，它的特点在于：散列表所占用的空间在物理上始终是地址连续的一块，相应的所有的冲突都在这块连续空间中加以排解。而无需向分离链接那样申请额外的空间。对！所有的散列以及冲突排解都在这样一块封闭的空间内完成。
 
 
因此相应地，这种策略也可以称作为闭散列。如果有冲突发生，就要尝试选择另外的单元，直到找到一个可供存放的空单元。具体存放在哪个单元，是有不同优先级的，优先级最高的是他原本归属的那个单元。从这个单元往后，都按照某种优先级规则排成一个序列，而在查找的时候也是按着这个序列行进，每个词条对应的这个序列被称为探测序列or查找链。
 
抽象来说，就是我们遇到冲突后，会相继尝试h0(x),h1(x),h2(x)这些单元，其中hi(x)= ( Hash( x ) + F ( I ) ) % TableSize，并且约定F(0)=0，F（x）是解决冲突的方法，就是刚才说的那个“优先级规则”。因为所有的数据都要放在这块空间，所以开放定址所需要的表规模比分离链接要大。通常而言开放定址法的装填因子lambda应该低于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 ) ) % TableSize就可以计算出各自不相冲突的地址了。完美！（暂时的）
 
 
我们脑内单步调试一下：第一个冲突在49产生:（49%10+0）%10=9，被89占了，那接着往后试，i=1，（49%10+1）%10=0，空的，放入这个空闲地址，这个地址是开放的。58依次和18,89,49产生冲突，试选三次后才找到一个空单元。对69的冲突也如此解决，一旦冲突，试探紧邻其后的单元，直至找到空单元or抵达散列表末尾。线性探测序列0->1->2->3在物理上保持连贯性的，具有局部性，这样一来系统的缓存作用将得到充分发挥，而对于大规模的数据集，这样一来更是可以减少I/O的次数。只要表足够大，总能找到一个空闲单元，但是这太费时间了。更糟的是——就算一开始空闲区域多，经过多次排解冲突后，数据所占据的单元也会开始形成一些区块，聚集在一起，被称为一次聚集(primary clustering)，但在前面动机篇里说过，散列函数的初衷是避免数据扎堆，所以后面必须改进。
 
那么总体看来散列到区块的任何关键字都需要多次试选单元才能解决冲突，然后被放到对应的那个区块里。下面做一个总结
 
优点：
 
无需附加空间（指针、链表、溢出区）
 探测序列具有局部性，可以利用系统缓存，减少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 delete，仅做一个删除标记，比如里面预留一个del变量，设置为TRUE。
 
 
那么在日后查找中，遇到他之后就应该越过继续往后查找而不是在此返回。在插入时遇到，就把它视作一个空单元，数据覆盖即可。应该说针对开放定址策略，懒惰删除不仅是“不得已而为之”的方法，甚至可以说是针对这种情况的最优方法。因为毕竟在开放定址策略中，每一个桶单元都同时属于多个查找链
 
开放寻址散列的分析：
 定理11.6 ：
 一个装载因子a=n/m<1的开放寻址散列表，在一次不成功的查找中，期望的探查数之多为1/(1-a).假设散列是均匀的。
 推论11.7
 平均情况，向一个装载因子为a的开放寻址散列表中插入一个元素时，至多需要做1/(1-a)次探查。假设采用的是均匀散列。
 定理11.8
 给定一个装载因子为a<1的开放寻址散列表，一次成功查找中的期望探查数之多为(1/a)ln(1/(1-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);//首先先找到该关键字k
	if (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");
}