数据结构--7.1散列表（哈希表）查找

散列表查找

我们要在a[ ] 中查找key关键字的记录：

——顺序表查找：挨个儿查找

——有序表查找：二分法查找

——散列表查找

记录的存储位置 = f（关键字）

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f（key）。

这里我们把这种对应关系f称为散列函数，又成为哈希（Hash）函数。采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（Hash table）。

散列表的查找步骤：

——当存储记录时，通过散列函数计算出记录的散列地址

——当查找记录时，我们通过同样的是散列函数计算记录的散列地址，并按此散列地址访问该记录

我们可以取关键字的某个线性函数值为散列地址，即：f（key）= a * key + b。

数字分析法

数字分析法通常适合处理关键字位数比较大的情况。

平方取中法

平方取中法是将关键字平方之后取中间若干位数字作为散列地址。

折叠法

折叠法是将关键字从左到右分割成位数相等的几部分，然后将这几部分叠加求和，并按散列表表长取后几位作为散列地址。

除留余数法

此方法为最常见的构造散列函数方法，对于散列表长为m的散列函数计算公式为：

—— f（key） = key mod p（p<=m）

实际上，这个方法不仅可以对关键字直接取模，也可以通过折叠、平方取中后再取模。

随机数法
——选择一个随机数，取关键字的随机函数值为它的散列地址。

即：f（key） = random（key）。

这里的random是随机函数，当关键字的长度不等时，采用这个方法构造散列函数是比较合适的。

处理散列冲突的方法

开放地址法

所谓的开放地址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。

公式：

$fi(key) = (f(key)+di) mod m$

（是mod m ； di = 1，2，3，……，m-1）

再散列函数法

fi（key） = RHi（key）（i= 1,2,3,4,……，k）

#define HASHSIZE 12
#define NULLKEY -32768

typedef struct
{
	int *elem;
	int count;
 }HashTable;
 
int InitHashTable(HashTable *H)
{
	H->count = HASHSIZE;
	H->elem = (int *)malloc(HASHSIZE * sizeof(int));
	if( !H->elem)
	{
		return -1;
	}
	for(i=0;i<HASHSIZE;i++)
	{
		H->elem[i] = NULLKEY;
	}
	return 0;
} 

//除留余数法
int Hash(int key)
{
	return key % HASHSIZE;
 } 

//插入关键字到散列表 
void InsertHash(HashTable *H,int key)
{
	int addr;
	addr = Hash(key);
	while(H->elem[addr] != NULLKEY)   //如果不为空，则冲突出现 
	{
		addr = (addr + 1) % HASHSIZE; //开放地址法的线性探测 
	}
	H->elem[addr] = key;
 } 

//散列表查找关键字
int SearchHash(HashTable H,int key,int *addr)
{
	*addr = Hash(key);
	while(H.elem[*addr] != key)
	{
		*addr = (*addr + i) % HASHSIZE;
		if(H.elem[*addr] == NULLKEY || *addr == Hash(key))
		{
			return -1;
		 } 
	}
	return 0;
 }