题目：关键字序列为：{38，25，74，63，52，48}，哈希函数为H(k)=k%7,哈希表的长度为7，用线性探测和链地址法处理冲突，分别计算等概率情况下查找成功的平均查找长度。

注：没给哈希表长度，给出装填因子时，可求哈希表长度， 

可根据此公式装填因子=元素个数/表长推：表长=元素个数/装填因子。

线性探测法



由上构造的哈希表如下： 



等概率下查找成功的平均查找长度为： 

ASL=(1+3+1+1+2+4)/6=2

链地址法 



由上构造的哈希表如下： 



等概率下查找成功的平均查找长度为： 

ASL=(1*4+2*2)/6=1.3

题意：给出哈希表的大小size，若不为素数则一直执行size++直至为素数。

给出n个数，进行哈希表的插入，利用二次探测（仅正增量）进行插入

给出m个数，进行哈希表的查找，利用二次探测（仅正增量）进行查找
#include<bits/stdc++.h>
#define ll long long
using namespace std;
//哈希表查找 平均查找长度 
int size,n,m;
int has[100005];
void insert(int x) //二次探测正增量方式进行插入
{
	for(int i=0;i<=size;i++)
	{
		int pos=(x+i*i)%size;
		if(has[pos]==0) //若此时pos位置为空
		{
			has[pos]=x; //x插入到了下标为pos的位置
			return; 
		} 
	}
	cout<<x<<" cannot be inserted."<<endl;
}
bool su(int x)
{
	if(x==0 || x==1)
		return 0;
	int k=sqrt(x);
	for(int i=2;i<=k;i++)
	{
		if(x%i==0)
			return 0;
	}
	return 1;
}
int main()
{
	int t[100005];
	cin>>size>>n>>m;
	while(!su(size))
		size++;
	for(int i=1;i<=n;i++)
	{
		cin>>t[i];
		insert(t[i]);
	}
	int x,ans=0;
	for(int i=1;i<=m;i++)
	{
		cin>>x;
		for(int j=0;j<=size;j++) //二次探测正增量方式进行查找
		{
			ans++; //代指查找次数 
			int pos=(x+j*j)%size;
			if(has[pos]==0 || has[pos]==x) //查找到为NULL表示查找失败 或者 查找成功 就break 
				break;
		}
	}
	printf("%.1f\n",1.0*ans/m); 
}

哈希表查找不成功时的平均查找长度
哈希表查找不成功时的平均查找长度(zz)哈希表查找不成功怎么计算？解答：先建好表，然后可以算出每个位置不成功时的比较次数之和，再除以表空间个数！

例如：散列函数为hash(x)=x MOD 13，用线性探测，建立了哈希表之后，如何求查找不成功时的平均查找长度！？

     地址： 0   1   2   3   4   5   6   7   8   9   10   11   12
     数据： 39  12  28  15  42  44   6  25  －  －   36   －   38
  成功次数： 1   3   1   2   2   1   1   9           1        1
不成功次数： 9   8   7   6   5   4   3   2   1   1    2   1    10
查找成功时的平均查找长度:ASL=(1+3+1+2+2+1+1+9+1+1)/10 =2.2
查找不成功时的平均查找长度:ASL=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54
说明：
查找成功代表找到KEY所在位置所用的次数
第n个位置不成功时的比较次数为，第n个位置到第1个没有数据位置的距离。
至少要查询多少次才能确认没有这个值。
（1） 查询hash(x)=0,至少要查询9次遇到表值为空的时候，才能确认查询失败。
（2） 查询hash(x)=1,至少要查询8次遇到表值为空的时候，才能确认查询失败。
（3） 查询hash(x)=2,至少要查询7次遇到表值为空的时候，才能确认查询失败。
（4） 查询hash(x)=3,至少要查询6次遇到表值为空的时候，才能确认查询失败。
（5） 查询hash(x)=4,至少要查询5次遇到表值为空的时候，才能确认查询失败。
（6） 查询hash(x)=5,至少要查询4次遇到表值为空的时候，才能确认查询失败。
（7） 查询hash(x)=6,至少要查询3次遇到表值为空的时候，才能确认查询失败。
（8） 查询hash(x)=7,至少要查询2次遇到表值为空的时候，才能确认查询失败。
（9） 查询hash(x)=8,至少要查询1次遇到表值为空的时候，才能确认查询失败。
（10）查询hash(x)=9,至少要查询1次遇到表值为空的时候，才能确认查询失败。
（11）查询hash(x)=10,至少要查询2次遇到表值为空的时候，才能确认查询失败。
（12）查询hash(x)=11,至少要查询1次遇到表值为空的时候，才能确认查询失败。


（13）查询hash(x)=12,至少要查询10次遇到表值为空(循环查询顺序表)的时候，才能确认查询失败。
 
http://hi.baidu.com/dfsfsdfwe/item/35f8f1c79e91f26389ad9e53

哈希表：线性探测法和链地址法求查找成功与不成功的平均查找长度
了解ASL的公式
线性探测法求ASL
链地址法求ASL

了解ASL的公式
查找成功时：ASL =$\frac{1}{n}$ $\sum_{i=1}^{n} C_i$

  n 为散列表中记录的个数（ 不是表的长度 ），

  Ci 为查找成功的第 i 个记录所需要的比较次数（ 表中空的记录意味着不成功，是不算在里面滴 ）
查找不成功时：ASL =$\frac{1}{r}$ $\sum_{i=1}^{n} C_i$

  r 为散列函数取值的个数（ 不是表的长度 ）。这个就充分解释了为什么散列函数 H(Key) = (key) MOD 11 在计算查找不成功ASL时，r = 11了，是因为这个散列函数的取值为 0~10，可以取11个值，所以 r = 11。

  Ci 为 散列函数取值为 i 时，查找失败时第 i 个记录所需要的比较次数（ 表中的有些部分，散列函数根本取不到，自然也就不在计算里了 ）
我想只要把这两个公式看懂，查找成功与不成功的ASL也就自然会求了。下面线性探测法和链地址法我各举一个例子。



线性探测法求ASL
将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中，散列函数为H(Key) = (key x 3) MOD 7，处理冲突采用线性探测再散列法，要求装填因子为0.7
装填因子  a = $\frac{表中装入的记录个数}{散列表的长度}$ = 0.7，可以求出散列表表长 = $\frac{7}{0.7}$ = 10

（7x3）mod 7 = 0，因此散列地址为 0

（8x3）mod 7 = 3，因此散列地址为 3

（30x3）mod 7 = 6，因此散列地址为 6

（11x3）mod 7 = 5，因此散列地址为 5

（18x3）mod 7 = 5，此时和11冲突，使用线性探测法（地址+1），又和30冲突，地址再次+1，无冲突，散列地址为 7

（9x3）mod 7 = 6，此时和30冲突，使用线性探测法（地址+1），又和18冲突，地址再次+1，无冲突，散列地址为 8

（14x3）mod 7 = 0，此时和7冲突，使用线性探测法（地址+1），无冲突，散列地址为 1




线性探测法处理冲突构造所得的哈希表如下：




地址
0
1
2
3
4
5
6
7
8
9




key
7
14

8

11
30
18
9



根据公式：查找成功时ASL = $\frac{1}{n}$ $\sum_{i=1}^{n} C_i$ 

如果查找7，则需要查找1次。

如果查找8，则需要查找1次。

如果查找30，则需要查找1次。

如果查找11，则需要查找1次。

如果查找18，则需要查找3次：第一次查找地址5，第二次查找地址6，第三次查找地址7，查找成功。

如果查找9，则需要查找3次：第一次查找地址6，第二次查找地址7，第三次查找地址8，查找成功。

如果查找14，则需要查找2次：第一次查找地址0，第二次查找地址1，查找成功。

所以，查找成功时ASL=（1+2+1+1+1+3+3）/ 7 = 12/ 7
根据公式：查找不成功时ASL = $\frac{1}{r}$ $\sum_{i=1}^{n} C_i$

举个例子来说吧：

  如果要查找key为9的关键字。根据散列函数可以计算H(key)=H(9)=6。

  此时在会检测地址为6的值，发现key=30，不等于9。这就说明在装填的时候发生了冲突。

  根据冲突处理方法，会继续检测地址为0的值，之所以没有检测地址7，8，9，H(key)的取值取不到这些值。检测地址为0的值，发现key=7，依然不等。

  根据冲突处理方法，会继续检测地址为1的值，发现key=14，依然不等。

  根据冲突处理方法，会继续检测地址为2的值，发现key为空。

   这就说明关键字9从应该出现的地址6，一直查找，找到值为空的地址都没有和9相等的，说明散列表中没有9这个值，因此探测次数为4次 
根据上面的例子

查找地址为0的值所需要的次数为3，

查找地址为1的值所需要的次数为2，

查找地址为2的值所需要的次数为1，

查找地址为3的值所需要的次数为2，

查找地址为4的值所需要的次数为1，

查找地址为5的值所需要的次数为5，

查找地址为6的值所需要的次数为4。

所以，查找不成功ASL=（3+2+1+2+1+5+4）/ 7 = 18/ 7



链地址法求ASL
将关键字序列{1 13 12 34 38 33 27 22} 散列存储到散列表中。散列函数为：H(key)=key mod 11，处理冲突采用链地址法，求在等概率下查找成功和查找不成功的平均查找长度
1mod11=1，因此散列地址为1

13mod11=2，因此散列地址为2

12mod11=1，因此散列地址为1（这个数据是数据1指针的另一个新数据）

34mod11=1，因此散列地址为1（这个数据是数据12指针的另一个新数据）

38mod11=5，因此散列地址为5

33mod11=0，因此散列地址为0

27mod11=5，因此散列地址为5（这个数据是数据38指针的另一个新数据）

22mod11=0，因此散列地址为0（这个数据是数据33指针的另一个新数据）
链地址法处理冲突构造所得的哈希表如下：



根据公式：查找成功时ASL = $\frac{1}{n}$ $\sum_{i=1}^{n} C_i$ 

如果查找1，则需要查找3次。从地址1开始查，第一次查到34，第二次查到12，第三次查到1。

如果查找13，则需要查找1次。

如果查找12，则需要查找2次。从地址1开始查，第一次查到34，第二次查到12。

如果查找34，则需要查找1次。

如果查找38，则需要查找2次。从地址5开始查，第一次查到27，第二次查到38。

如果查找33，则需要查找2次。从地址0开始查，第一次查到22，第二次查到33。

如果查找27，则需要查找1次。

如果查找22，则需要查找1次。

所以，查找成功ASL =（3×1+2×3+1×4）/8 = 13/8
根据公式：查找不成功时ASL = $\frac{1}{r}$ $\sum_{i=1}^{n} C_i$

举个例子来说吧：

如果要查找key为16的关键字。根据散列函数可以计算H(key)=H(16)=5。

  首先从地址5开始查找，第一次查找到的数据是27，和16不相等，继续往后找。

  第二次查找到的数据是38，和16不相等，继续往后找。

  第三次查找到的数据是空，查找结束。 意味着在地址5这一行找不到关键字16，因为如果关键字16在表中存在的话，只可能在地址5这一行，现在在地址5这一行找不到，意味着整个表也找不到。 
如果要查找key为20的关键字。根据散列函数可以计算H(key)=H(20)=9。

  首先从地址9开始查找，第一次查找到的数据是空，查找结束。意味着表中不存在关键字20。 
根据上面的例子

查找地址为0的值所需要的次数为3，

查找地址为1的值所需要的次数为4，

查找地址为2的值所需要的次数为2，

查找地址为3的值所需要的次数为1，

查找地址为4的值所需要的次数为1，

查找地址为5的值所需要的次数为3，

查找地址为6的值所需要的次数为1，

查找地址为7的值所需要的次数为1，

查找地址为8的值所需要的次数为1，

查找地址为9的值所需要的次数为1，

查找地址为10的值所需要的次数为1。

所以，查找不成功ASL = (3+4+2+1+1+3+1+1+1+1+1)/11 = 19/11
其实不管是线性探测法还是链地址法，在求查找不成功ASL时，都是差不多的。首先根据散列函数找到地址，然后从这个地址往后查，一直查到空结束。