1012: 哈希表（链地址法处理冲突）

题目描述
采用除留余数法（H（key）=key %n）建立长度为n的哈希表，处理冲突用链地址法。建立链表的时候采用尾插法。
输入
第一行为哈西表的长度m；
第二行为关键字的个数n；
第三行为关键字集合；
第四行为要查找的数据。
输出
如果查找成功，输出该关键字所在哈希表中的地址和比较次数；如果查找不成功，输出-1。
样例输入
13
13
16 74 60 43 54 90 46 31 29 88 77 78 79
16
样例输出
3,1

思路：
哈希表（以下内容重在理解）

1. 哈希表的基本概念： 哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

• （tips:我对哈希表的浅显理解是将他比作图书馆书架，我们以后处理的数据的量少则十几万多则上亿，这个时候就用类似图书馆里的分类方法，分类后将数据存放在我们的电脑里，这样就会使得数据的查找较为简单。）

2. 哈希表的构建方法：
   ① 直接定址法:（了解就好）
   是以关键字 k 本身或关键字加上某个常量c 作为哈希地址的方法。直接定 址法的哈希函数 h(k)为: h(h)=k+c 例如,图 9. 30 所示的哈希表就是采用了这种方法。 这种方法的特点是哈希函数计算简单。当关键字的分布基本连续时， 可用直接定址法的哈希函数；否则,若关键字的分布不连续将造成内存单 视频讲解 元的大量浪费。

   ②除留取余法：（重点）
   是用关键字k除以某个不大于哈希表长度m的整数p所得的余数作为哈 希地址。除留余数法的哈希函数 h(k)通常为： h(h)= k mod p（mod 为求余运算,p≤m) 除留余数法的计算比较简单,适用范围广,是最经常使用的一种哈希函数。这种方法的 关键是选好 p,使得元素集合中的每一个关键字通过该函数转换后映射到哈希表范围内的 任意地址上的概率相等,从而尽可能减少发生冲突的可能性。例如,p 取奇数就比取偶数 好。理论研究表明,p 取不大于m的素数时效果最好。

   ③数字分析法：（了解就好）
   该方法是提取关键字中取值较均匀的数字作为哈希地址，它适用于所有关键字值都已知的情况，并需要对关键字中每一位的分布情况进行分析。

3. 哈希表的冲突解决
   ①开放地址法
   开放定址法（open adresing 就是在出现哈希冲突时在哈希表中找一个新的空刚位！ 存放元素。例如要存放关键字为A的元素,d=k(k），而地址为d的单元已经被其他元占用了,那么就在d地址的前后找空闲位置。

• 就像某个人买了一张电影票，他晚到了电影院,他的位置被其他人占了,他就在周围找一个空座位坐下来。那么怎么找空闲单元呢？据开放定址法找空闲单元的方式又分为线性探测法和平方探测法等。

a.线性探测法
是从发生冲突的地址(设为 d)开始,依次探测 d,的下一个地 址(当到达下标为m-1的哈希表表尾时,下一个探测地址是表首地址 O),直到找到一个空闲 单元为止(当m>n时一定能够找到一个空闲单元)。

• 以前面的看电影为例,假设 电影院座位只有一排(共 20 个座位),他的座位是 8(被其他人占了),线性探测法就是依次 查看 9.10.…,20 的座位是否为空的,有空就坐下,否则再查看 1,2,…,7 的座位是否为空 的,如此这样,他总可以找到一个空座位坐下。
  

b.平方探测法
设发生冲突的地址为 d,平方探测法(square probing)的探测序列为 d+1, d一1, d十2^1 , d一2^1,…。平方探测法的数学描述公式为： d,= h(k) d,=(d,±i) mod m (1≤i≤m-1)

• 仍以前面的看电影为例,平方探测法就是在他被占用的座位前后来回找空座位。 前后一个没找到就前后两个，找到为止。

②拉链法：
把具有相同散列地址的关键字(同义词)值放在同一个单链表中，称为同义词链表。有m个散列地址就有m个链表，同时用指针数组T[0…m-1]存放各个链表的头指针，凡是散列地址为i的记录都以结点方式插入到以T[i]为指针的单链表中。T中各分量的初值应为空指针。

• 看似复杂的拉链法，其实就是用一个“数组”把几个链表串起来罢了。

【例】原本应该放在a[2]的数据a发现a[2]被占了，他就在a[2]接一个链表成为a[2]的“小弟”，后面相同类型的数据a1也是如此，他发现a[2]被占了，还发现的a[2]的“第一小弟”被占了，那就在“第一小弟数据a”后面接一个链表成为“a[2]的第二小弟”，注：xxxx为空。

4. 【拓展】哈希表的优缺点

   优点：
   无论数据有多少，处理起来都特别的快
   能够快速地进行 插入修改元素 、删除元素 、查找元素 等操作
   代码简单（其实只需要把哈希函数写好，之后的代码就很简单了）
   缺点：
   哈希表中的数据是没有顺序的
   数据不允许重复

法一、拉链法
采用除留余数法（H（key）=key %n）建立长度为n的哈希表，处理冲突用链地址法。建立链表的时候采用尾插法。

#include<bits/stdc++.h>
using namespace std;
struct HTNode//储存值和下一个结点的结构体 
{
	int key;
	struct HTNode *next;
};
struct HashTable//储存头结点的结构体 
{
	struct HTNode *head;
};
void InstHT(HashTable ha[],int n)
{
	for(int i=0;i<n;i++)
	{
		ha[i].head=NULL;
	}
}
void CreateHT(HashTable ha[],int n,int data)//创建哈希表 
{
	int t=data%n;//计算哈希地址序号 
	if(ha[t].head==NULL)//如果该序号的头结点为空 
	{
		HTNode *p;
		p=(struct HTNode*)malloc(sizeof(struct HTNode));//p=new HTNode ();
		p->key=data;//储存数据 
		p->next=NULL;//将下一个结点设置为空 
		ha[t].head=p;//赋值给头结点 
	}
	else//如果头结点不为空，则从头结点一直往后找到最后一个结点 
	{
		HTNode *p,*q;
		p=ha[t].head;
		while(p->next!=NULL) p=p->next;//查找到最后一个结点 
		q=(struct HTNode*)malloc(sizeof(struct HTNode));//q=new();
		q->key=data;
		q->next=NULL;
		p->next=q;//将新的结点接到最后 
	}
}
void SearchHT(HashTable ha[],int n,int data)//查找哈希表 
{
	int t=data%n;//计算哈希地址序号 
	HTNode *p;
	p=ha[t].head;
	for(int i=0; ;i++)//查找对应序号的链表 
	{
		if(p==NULL)//如果为空，则没有，输出-1
		{
			printf("-1");//cout<<"-1";
			break;
		}
		else if(p->key==data)//如果有，则输出答案，并且跳出循环 
		{
			printf("%d,%d",t,i+1);//cout<<t<<i+1;
			break;
		}
		else p=p->next;//否则继续向后查找 
	}
}
int main()
{
	int n,k,data;
	scanf("%d",&n);//cin>>n;
	scanf("%d",&k);//cin>>k;
	HashTable ha[n];
	InstHT(ha,n);
	for(int i=0;i<k;i++)
	{
		scanf("%d",&data);//cin>>data;
		CreateHT(ha,n,data);
	}
	scanf("%d",&data);//cin>>data;
	SearchHT(ha,n,data);
}
 

（代码出自孤雪胜悲鸣）

法二、奇淫技巧之二维数组

#include<bits/stdc++.h>
using namespace std;
int main()
{
 int i,j=0,a[50][10]={0},m,n,key,b[50]={0};    //m为哈希表长度，n为关键字的个数
 scanf("%d %d",&m,&n);//cin >> m >>n;
 for(i=0;i<n;i++)
 {
  scanf("%d",&key);//cin>>key;
  a[key%m][b[key%m]++]=key;               //将同一类型关键字放入同一行。
 }
 scanf("%d",&key);//cin>>key;
 for(i=0;i<n;i++)
 {
  if(a[key%m][i]==key){
   printf("%d,%d",key%m,i+1);  //cout << key%m <<i+1;                   //查找对应的关键字时直接遍历该行数，并输出在二维数组中所在位置与查找次数
   j++;
   break;
  }
 }
 if(j==0) printf("-1"); //cout << "-1";                          //如果没有找到，则输出-1
 return 0;
}

以上方法仅供参考，欢迎互联网的广大朋友们提出指正。

题目描述
采用除留余数法（H（key）=key %n）建立长度为n的哈希表，处理冲突用链地址法。建立链表的时候采用尾插法。

输入
第一行为哈西表的长度m；
第二行为关键字的个数n；
第三行为关键字集合；
第四行为要查找的数据。

输出
如果查找成功，输出该关键字所在哈希表中的地址和比较次数；如果查找不成功，输出-1。

样例输入

13
13
16 74 60 43 54 90 46 31 29 88 77 78 79
16

样例输出

3,1

题目给的样例输出好像不对，应该是3，2

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define MaxSize 1000
typedef struct node
{
    int key;
    struct node *next;
}NodeType;
typedef struct
{
    NodeType*first;
}HashTable;
HashTable ha[MaxSize];//哈希表
int keys[MaxSize];//存键值
void Insert(HashTable ha[],int m,int key)
{
    int adr;
    adr=key%m;//关键字%哈希表长度
    NodeType *q;
    q=(NodeType*)malloc(sizeof(NodeType));
    q->key=key;
    q->next=NULL;
    //通过链接形成某地址的哈希表
    if(ha[adr].first==NULL)
    {
        ha[adr].first=q;
    }else//头插法
    {
        q->next=ha[adr].first;
        ha[adr].first=q;
    }
}
void Seek(HashTable ha[],int m,int k)
{
    int i=0,adr;
    adr=k%m;
    //判断是哪一个地址的哈希表
    NodeType *q;
    q=ha[adr].first;
    //q为当前地址的哈希表的头指针
    while(q!=NULL)
    {
        i++;
        if(q->key==k) break;
        q=q->next;
    }
    if(q!=NULL)
    printf("%d,%d",adr,i);
    else
    printf("-1");
}
int main()
{
    int m,n,k;
    scanf("%d",&m);//哈希表长度
    scanf("%d",&n);//关键字个数
    for(int i=0;i<n;i++)
    {
        scanf("%d",&keys[i]);//关键字集合
    }
    for(int i=0;i<m;i++)
    {
        ha[i].first=NULL;
    }
    for(int i=0;i<n;i++)
    {
        Insert(ha,m,keys[i]);///插入哈希表
    }
    scanf("%d",&k);
    Seek(ha,m,k);
}

Hash (链地址法处理冲突）

Hash，一般翻译做散列、杂凑，或音译为哈希，是把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。(百度百科)

HashTable通过key来查找信息，极大提高了时间效率，但不同的信息可能拥有相同的key值，这就是冲突，这里用链地址法来解决冲突，即有冲突的信息具有相同的key值，将它们按顺序链接在同一地址下（尾插法）。

（百度图片）

这里还有：Hash 哈希表 （开放地址法解决冲突）

代码如下：

in:
13
13
16 74 60 43 54 90 46 31 29 88 77 78 79
16
out:
3,1

#include"bits/stdc++.h"
using namespace std;

#define MAX 24
#define INIFINITE 201201//定义无限大 
typedef char DataType;//定义数据类型 
typedef int KeyType;//定义关键字类型 
typedef struct node{
	int key;//储存关键字信息 
	struct node *next; 
}HashListNode; 
typedef struct{
	DataType data; 
	KeyType key;
	HashListNode *firstare;//指向的第一片区域 
}HashTable[MAX],Hash;

int H(int key,int n){//除留余数 
	return key%n;
}
void Init(Hash test[],int n){//初始化 
	for(int i=0;i<n;i++){
		test[i].key=INIFINITE;
		test[i].firstare=NULL;//注意这的初始化 
	}
}
void CreatHashList(HashListNode *&link,int key){//创建链地址 （尾插法） 
	HashListNode *p;
	p=new HashListNode;
	p->key=key;
	p->next=NULL;
	if(!link){
		link=p;
	}
	else{
		while(link->next){
			
			link=link->next;
		}
		link->next=p;
	}
		
}
void CreateHash(Hash test[],int num,int n){//创建哈希表 
	bool flag[MAX]={false};//冲突标记 
	for(int i=0;i<num;i++){
		int temp,k;
		cin>>temp;//关键字信息 
		k=H(temp,n);
		if(!flag[k]){//若未冲突 
			test[k].key=temp;
			flag[k]=true; 
		}
		else{//处理冲突 
			CreatHashList(test[k].firstare,temp);
		}
	}
} 
void SearchNode(Hash test[],int n){//查找结点，查找失败输出-1
	int aim,count=0;
	cin>>aim;//目标 
	int k=H(aim,n);
	bool flag=false;//查找到的标记 
	if(test[k].key==INIFINITE){
		cout<<"-1";
		return;
	}
	
	if(test[k].key==aim){
		flag=true;
		count++;
	}
	else{
		count++;//下面直接从下一片区域找起  这要加一次   
		while(test[k].firstare){
			count++;
			if(test[k].firstare->key==aim){
				flag=true;
				break;
			}
			test[k].firstare=test[k].firstare->next;
		}
	}
	if(!count||!flag){
		cout<<"-1";
	}
	else{
		cout<<k<<","<<count;
	}
	
}
int main(){
	HashTable test;
	int n,num;
	cin>>n>>num;
	Init(test,n);
	CreateHash(test,num,n);
	SearchNode(test,n);
	
	return 0;
}

请多指教