Hash 哈希表（链地址法处理冲突,c++）

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;
}

请多指教