散列查找 ← 线性探测法处理冲突

【算法分析】
散列查找法主要研究以下两方面的问题：
(1) 如何构造散列函数？
实际应用中，有种构造散列函数h()的方法称为除留余数法。因为它计算简单，适用范围非常广，所以成为最常用的构造散列函数的方法。
除留余数法，即假设散列表的表长为m，选择一个不大于m的数p，用p去除关键字，除后所得余数为散列地址，即h(key)=key%p。这个方法的关键是选取适当的p，一般情况下，可以选p为小于表长m的最大质数。例如，表长m=100，可取p=97。
(2) 如何处理冲突？
散列法在实际应用中，很难完全避免发生冲突，所以选择一个有效的处理冲突的方法是散列法的另一个关键。本算法采用线性探测法处理冲突，其基本思想是当某一记录的关键字key的初始散列地址d0=h(key)发生冲突时，以d0为基础，采用下文所述线性探测法的数学递推公式计算得到另一个地址d1，如果d1仍然发生冲突，以d1为基础再求下一个地址d2。依次类推，直至dk不发生冲突为止，则dk为该记录在表中的散列地址。通常把寻找“下一个”空位的过程称为探测。

线性探测法计算“下一个”空位的数学递推描述公式为：

其中，h(k)为散列函数，m为散列表表长。

【算法代码】

#include
using namespace std;
 
const int m=20; //length of hash table
const int NULLKEY=-12345; //null flag
 
bool isPrime(int n) {
	if(n==1) return false;
	for(int i=2; i<=sqrt(n); i++) {
		if(n%i==0) return false;
	}
	return true;
}
 
int getPrime(int n) { //Get largest prime less than n
	for(int i=n-1; i>=2; i--) {
		if(isPrime(i)) {
			return i;
			break;
		}
	}
}
 
int H(int key,int p) { //hash function
	int ans;
	ans=abs(key)%p;
	return ans;
}
 
int hashSearch(vector<int> &a,int key) {
	int p=getPrime(m);
	int d0=H(key,p);
	int di;
	if(a[d0]==NULLKEY) return -1;
	else if(a[d0]==key) return d0;
	else {
		for(int i=1; i
			di=(d0+i)%m; //Linear detection method
			if(a[di]==NULLKEY) return -1;
			else if(a[di]==key) return di;
		}
		return -1;
	}
}
 
int main() {
	vector<int> v;
	int n; //n
	cin>>n;
	for(int i=0; i
		int x;
		cin>>x;
		v.push_back(x);
	}
 
	int key;
	cin>>key;
	int t=hashSearch(v,key);
	if(t==-1) cout<<"Not found"<
	else cout<<"Index is "<
	
	return 0;
}
 
 
/*
in:
16
-7 16 12 68 27 55 -19 20 85 79 10 11 10 -3 -1 7
12
out:
Index is 2
*/