题目：关键字序列为：{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

哈希表（又名为是散列表）
 散列是一个用于唯一标识对象并在一些预先计算的唯一索引（称为“密钥”）存储每个对象的过程。因此，对象以“键值”对的形式存储，这些项的集合被称为“字典”。可以使用该键值搜索每个对象。有多种不同的基于哈希的数据结构，但最常用的数据结构是哈希表。
 
哈希表通常使用数组实现。
 
哈希数据结构的性能取决于以下三个因素：
 
哈希函数
 哈希表的大小
 碰撞处理方法
 下图展示了如何在数组中映射哈希。该数组的索引是通过哈希函数计算的。
 
 今天主要讲一下哈希表平均查找长度ASL计算，也是常见面试题之一
 题目：关键字序列为：{30，25，80，63，52，48}，哈希函数为H(k)=k%7,哈希表的长度为7，用线性探测和链地址法处理冲突，分别计算等概率情况下查找成功的平均查找长度。
 
注：没给哈希表长度，给出装填因子时，可求哈希表长度，
 可根据此公式装填因子=元素个数/表长推：表长=元素个数/装填因子。
 
线性探测法（通过数组保存）
 H(30)=30%7=2
 H(25)=25%7=4
 H(80)=80%7=3,和30冲突，往后移一位：4，又与25冲突，继续后移一位：5
 H(63)=63%7=0
 H(52)=52%7=3，后移三位为6
 H(48)=48%7=6，与52冲突，后移一位为0，再后移一位为1
 结果为：
 30 ——2
 25——4
 80——5
 63——7
 52——6
 48——1
 平均查找长度：查找次数和/数组个数
 （1+1+3+1+4+3）/6=2.2
 
链地址法 (以链表形式存储）
 取模后值相同的在同一个链表中，即
 0——63
 1
 2
 3——30——80——52
 4——25
 5
 6——48
 等概率下查找成功的平均查找长度为：
 ASL=(14+21+3*1)/6=1.5

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct		//元素类型定义
{
	int value;		//元素值
	int hi;			//冲突次数
}DataType;
typedef struct		//哈希表类型定义
{
	DataType *data;
	int length;		//哈希表的长度/
	int num;		//表中元素个数
}HashTable;
void CreateHashTable(HashTable *H,int m,int p,int hash[],int n);
int SearchHash(HashTable H,int k);
void HashASL(HashTable H,int m);
void DisplayHash(HashTable H,int m);
int main()
{
	printf("请输入数据个数：\n");
	int N;
	scanf("%d",&N);
	int hash[N];
	int item;
	printf("请输入数据：\n");
	for(int i=0;i<N;i++){
		scanf("%d",&item);
		hash[i]=item;
	} 
	HashTable H;
	int m,p,n,pos,v;
	printf("请输入哈希表的长度，mod及元素个数:\n"); 
	scanf("%d%d%d",&m,&p,&n);
	CreateHashTable(&H,m,p,hash,n);
	DisplayHash(H,m);
	printf("请输入待查找的元素:\n");
	scanf("%d",&v);
	pos=SearchHash(H,v);
	printf("元素%d在哈希表中的位置:%d\n",v,pos);
	HashASL(H,m);
}
//构造哈希表，并处理冲突
void CreateHashTable(HashTable *H,int m,int p,int hash[],int n)
{ 
	int i,sum,addr,di,k=1;
	//为哈希表分配存储空间
	(*H).data=(DataType*)malloc(m*sizeof(DataType));
	if(!(*H).data)	
		exit(-1); 
	(*H).num=n;			//初始化哈希表的元素个数
    (*H).length=m;		//初始化哈希表的长度
	for(i=0;i<m;i++)	//初始化哈希表
	{
		(*H).data[i].value=-1;
		(*H).data[i].hi=0;
	}
	//构造哈希表并处理冲突
	for(i=0;i<n;i++)
	{
		sum=0;			//sum记录冲突次数
		addr=hash[i]%p;	//利用除留余数法求哈希函数地址
		di=addr;
		if((*H).data[addr].value==-1)	//如果不冲突则将元素存储在表中
		{
			(*H).data[addr].value=hash[i];
			(*H).data[addr].hi=1;
		}
		else			//用线性探测再散列法处理冲突
		{
			do 
			{
				di=(di+k)%m;
				sum+=1;
			} while((*H).data[di].value!=-1);
			(*H).data[di].value=hash[i];
			(*H).data[di].hi=sum+1;
		}
	}
}
int SearchHash(HashTable H,int v)
//在哈希表H中查找值为v的元素
{
	int d,d1,m;
	m=H.length;
	d=d1=v%m;				//求v的哈希地址
	while(H.data[d].value!=-1)
	{
		if(H.data[d].value==v)	//如果找到要查找的元素v，则返回v的位置
			return d;
		else					//如果不是要找的元素，则继续向后查找
			d=(d+1)%m;
		if(d==d1)				//如果找遍了哈希表中的所有位置还没有找到v，则返回0
			return 0;
	}
	return 0;					//该位置不存在元素v
}
//求哈希表的平均查找长度
void HashASL(HashTable H,int m)
{
	float average=0;
	int i;
	for(i=0;i<m;i++)
		average=average+H.data[i].hi;
	average=average/H.num;
	printf("平均查找长度ASL:%.2f",average);
	printf("\n");  
}
//输出哈希表
void DisplayHash(HashTable H,int m)
{
	int i;
	printf("哈希表地址:  ");
	for(i=0;i<m;i++)		//输出哈希表的地址
		printf("%-5d",i);
	printf("\n");
	printf("元素值value: ");
	for(i=0;i<m;i++)		//输出哈希表的元素值
		printf("%-5d",H.data[i].value);
	printf("\n");
	printf("冲突次数:    ");
	for(i=0;i<m;i++)		//冲突次数
		printf("%-5d",H.data[i].hi);
	printf("\n");
}

请输入数据个数：

8

请输入数据：

23 12 14 56 456 27 78 98

请输入哈希表的长度，mod及元素个数:

20 7 8

哈希表地址:  0    1    2    3    4    5    6    7    8    9    10   11   12   13   14   15   16   17   18   19

元素值value: 14   56   23   456  78   12   27   98   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1   -1

冲突次数:    1    2    1    3    4    1    1    8    0    0    0    0    0    0    0    0    0    0    0    0

请输入待查找的元素:

14

元素14在哈希表中的位置:0

平均查找长度ASL:2.63

哈希表查找不成功时的平均查找长度计算和查找成功时的ASL
 

 例如:  关键字集合 
         { 19, 01, 23, 14, 55, 68, 11, 82, 36 }
 
 
 

 设定哈希函数 H(key) = key MOD 11 ( 表长=11 )
 
 

 
 

  
 
 
 
 
 

  
 
 查找成功次数：    1      1    2     1    3    6     2       5     1
 
 

 查找不成功次数：10    9     8    7    6    5     4       3      2    1    1
 

 
 
 

 查找成功时的平均查找长度：ASL=(1+1+2+1+3+6+2+5+1)/9=22/9
 

 查找不成功时的平均查找长度:ASL=(10+9+8+7+6+5+4+3+2+1+1)/11=56/11
 

 说明：
 第n个位置不成功时的比较次数为，第n个位置到第1个没有数据位置的距离。
   如：第0个位置到第1个没有数据位置（9）的距离为10！