哈希表，又称散列表，通过键-值对(key-indexed)的方式将数据存储在一片连续的内存中，注意哈希表的结构是数组结构（连续存储区域）

这里解释一下什么是健和值，健相当于数组中的值，值就是数组的下标index，哈希也就是把数组的值和数组的下标建立起了一定的关系，一般是通过值直接确定下标。

• 那么哈希表是用来做什么的呢？
• 答：最适合解决的问题是 查找与给定值相等的记录，并且可以*快速插入 *

也就是说，我可以通过我知道的这个值，快速的确定这个数组里面有没有这个值，而且这个速度是比二分法查找等算法快得多的，它的算法复杂度一直为O(1).

• 那么是怎么通过数组链的值（健）找到对应的数组下标（值）的呢?
• 答：健和值之间有一个转换函数，叫做哈希函数或者叫散列函数，index = F(key)，输入key,即可算出key在散列表（哈希表）中的索引

散列表查找步骤：

• 存储时，通过哈希函数计算散列地址，并按照此散列地址记录
• 查找记录时，通过同样的散列函数计算散列地址

哈希是一种存储方法，也是一种查找方法

哈希表查找需要注意两个问题：

• 1 散列函数的选取，有很多种选取的方法，本文的例子是最常用的除留余数法，index = key % p (p <= HASHSIZE),p的取值等于或小于哈希表的长度。
  一个好的哈希函数，可以使得不同的数据会产生更多不同的索引，便于存储

• 2 如果不同的数据产生了相同的索引，那就需要采用新的办法来处理这个问题，一般是有三种方法

开放定址法，即f`(key) = (f(key)+d) % HASHSIZE，哈希函数得到的数据索引中已经有值的时候，对这个addr进行上述操作，d取值为1…(HASHSIZE-1)
再散列函数，f(key)=RH(key)(1=1 ,2,…,k),RH为不同的散列函数
链地址法，在当前的位置增加一个链表节点，存储相同索引的不同数据即可

• 散列表的结构，elem是一个动态数组的首地址，count是数据个数

#define HASHSIZE 12
#define NO_DATA -12345
typedef struct HashTable
{
	int *elem;
	int count;
}HashTable,*HashTable_ptr;		// 散列表首地址 + 散列表数据个数

• 初始化散列表

/* 初始化散列表 */
void init_HashTable(HashTable_ptr H)
{
	int i;
	H->elem = malloc(HASHSIZE * sizeof(int));
	for(i=0;i<HASHSIZE;i++)
	{
		H->elem[i] = NO_DATA;
	}
}

• 插入值到散列表,就是上述的第一步操作，按照散列函数的方式将值插入到散列表中，对于冲突问题，这里采取的是开放定址法

/* 插入key到散列表 */
void inset_HashTable(HashTable_ptr H,int key)
{
	int addr = HASH(key);
	while(H->elem[addr] != NO_DATA)	// 如果这一项有值了，往后存储
	{
		addr = (addr+1) % HASHSIZE;	
		// 开放定址法 : 以HASH函数得到的索引为key,产生新的索引
	}
	H->elem[addr] = key;
}

• 查找数据的索引，按照相同的散列函数，得到散列表的索引，如果开放定址法的输出又回到了最初的值，表明散列表的没有这个需要查找的值。

/* 查找关键字的地址 */
int search_HashTable(HashTable_ptr H,int key)
{
	int addr = HASH(key);
	while(H->elem[addr] != key)
	{
		addr = (addr+1) % HASHSIZE;		// 同样的方法查找
		if(addr == HASH(key))		// 查找回到原点，说明数据不存在
		{
			printf("no data \r\n");
			return -1;
		}
	}
	return addr;
}

• 测试代码

int main()
{
	int i;
	int a[] = {12,67,56,16,25,37,22,29,15,47,48,34};
	
	HashTable hash;
	HashTable_ptr H = &hash;
	init_HashTable(H);

	for(i=0;i<HASHSIZE;i++)
	{
		inset_HashTable(H,a[i]);
	}

	printf("插入之后的哈希表为：");
	for(i=0;i<HASHSIZE;i++)
	{
		printf("%d ",H->elem[i]);
	}
	printf("搜索到2的地址为: %d \r\n",search_HashTable(H,2));

}

对于查找类的题，别再盲目的遍历啦，可以先创建一个散列表再进行查找。