Hash初步

　　Hash主要用于信息安全领域中加密算法，它把一些不同长度的信息转化成杂乱的128位的编码，这些编码值叫做HASH值. 也可以说，Hash就是找到一种数据内容和数据存放地址之间的映射关系。

　　数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。那么我们能不能综合两者的特性，做出一种寻址容易，插入删除也容易的数据结构？答案是肯定的，这就是我们要提起的哈希表，哈希表有多种不同的实现方法，我接下来解释的是最常用的一种方法——拉链法，我们可以理解为“链表的数组”，如图：

先来最简单的hash算法，用数组实现，没有解决冲突问题：

已经加上注释：

#include <stdio.h>
#define N 6    
#define M 6 
//N  hash表的大小   M  插入的个数 
typedef int datatype;//定义数据类型 
typedef struct
{
	datatype key;
}Hretype;//结构体类型 


int LHashsearch(Hretype HT[N], datatype k)//传表和KEY值 
{
	int addr,i=0;
	addr = k % N;//最简单的哈希函数 
	while(i<N && HT[addr].key != -1 && HT[addr].key != k)//如果表是空的，或者其key值的相同的 
	{
		i++;
		addr = (addr+1)%N;//寻找下一个数组元素 
	}
	if(i == N)
		return -1;  //表溢出 
	else
		return addr;//返回地址 
}

int LHinsert(Hretype HT[N], Hretype R)//插入表 
{

	int addr;
	addr = LHashsearch(HT, R.key);//找地址 

	if(addr==-1 || HT[addr].key == R.key)//如果表满了 ，或者元素冲突 
	{
		return 1;
	}
	else
	{
		HT[addr] = R;//否则，插入 
		return 0;
	}
}

int main()
{
	int i; 
	Hretype R[M];//要插入的数 
	Hretype HT[N];//hash表 

	for( i=0;i<N;i++)
		HT[i].key = -1;
	printf("please input %d numbers:",M);
	for(i=0;i<M;i++)
		scanf("%d",&R[i].key);
	for(i=0;i<M;i++)
	{
		int value = LHinsert(HT,R[i]);
		if(value)
			printf("表溢出\n");
		else
		{
			printf("插入成功\n");
		}
	}
	for(i=0;i<M;i++)
	{
		printf("i=%d\n",HT[i].key);
	}
	return 0;
}