哈希（Hash）查找算法详解之C语言版-Toy模板网

这篇具有很好参考价值的文章主要介绍了哈希（Hash）查找算法详解之C语言版。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一、哈希查找算法原理

哈希查找是一种快速查找算法，该算法不需要对关键字进行比较，而是以关键字为自变量，以该关键字在存储空间中的地址为因变量，建立某种函数关系，称为哈希函数，这样在查找某一关键字的时候，就可以通过哈希函数直接得到其地址，有效的提高了查找效率。
选取哈希函数及基本原则主要有：计算函数所需时间、关键字的长度、哈希表长度（哈希地址范围）、关键字分布情况、记录的查找频率等。
哈希函数的构造有多种，常见的有“直接定址法”、“数字分析法”、“平方取中法”、“折叠法”、“除留余数法”、“随机数法”等。
哈希函数构造的一个基本原则就是尽量避免冲突，也就是尽量避免因变量地址的冲突。一旦发生冲突，就需要重新定址。常见的处理地址冲突的方法有：“开放定址法”、“再哈希法”、“链地址法”、“建立公共溢出区”等。

二、创建哈希查找及哈希插值表示例

假设有数据{ 10, 8, 14, 15, 20, 31 }，创建哈希表以进行哈希查找。
1.创建哈希表
以除留余数法构造哈希函数，以线性探测法作为处理冲突的方法，取哈希表长度为7，建立哈希表过程如下：
H(10) = 10 % 7 = 3
H(8) = 8 % 7 = 1
H(14) = 14 % 7 = 0
H(15) = 15 % 7 = 1 此时冲突，重新定址：H(15) = (H(15)+1) % 7 = 2
H(20) = 20 % 7 = 6
H(31) = 31 % 7 = 3 此时冲突，重新定址：H(31) = (H(31)+1) % 7 = 4
哈希表如下：
哈希查找,算法与数据结构,哈希算法,算法,c语言,数据结构,散列表
2.哈希查找
当查找某一元素的时候，首先通过哈希函数计算其哈希地址，然后比较该地址的值是否等于目标值，如果相等则查找结束，否则利用处理冲突的方法确定新的地址，再进行比较。如果哈希地址为空，则查找失败。
利用哈希函数计算元素15的地址是1，此时表里的元素不等于15，因此使用线性探测法更新哈希地址，得到新地址是2，此时查找成功。

三、哈希查找算法的C程序

以“除留余数法”作为哈希函数，以“线性探测法”作为处理冲突的方法，给出创建哈希表和哈希查找算法的C程序。
1.哈希表的结构：
可以根据实际需要调整成员列表中的成员。

typedef struct HashTable
{
	int key;      //关键字 
	int EmptyFlag;//占用（冲突）标志，0表示没被占用，1表示被占用 
}HashTable;

2. 创建哈希表

//tbl：哈希表
//data：已知的数组
//m：数组的长度
//p：哈希表的长度 
void CreateHashTable( HashTable *tbl, int *data, int m, int p )
{
	int i, addr, k;
	for( i=0; i<p; i++ ) //把哈希表被占用标志置为0 
	{
		tbl[i].EmptyFlag = 0;
	}
	for( i=0; i<m; i++ )
	{
		addr = data[i] % p;//计算哈希地址 
		k = 0;//记录冲突次数 
		while( k++ < p )
		{
			if( tbl[addr].EmptyFlag == 0 )
			{
				tbl[addr].EmptyFlag = 1;//表示该位置已经被占用 
				tbl[addr].key   = data[i];
				break;
			}
			else
			{
				addr =  ( addr + 1 ) % p; //处理冲突 
			}
		}	
	}
}

3.哈希查找

int SearchHashTable( HashTable *tbl, int key, int p )
{
	int addr, k, loc;//loc表示查找位置下标，如果为0则表示查找失败 
	addr = key % P;//计算Hash地址 
	loc = -1; 
	k = 0;//记录冲突次数 
	while( k++ < p )
	{
		if( tbl[addr].key == key )
		{
			loc = addr;
			break;
		}
		else
		{
			addr =  ( addr + 1 ) % p; //处理冲突 
		}	
	}
	return loc;
}

3.完成的测试代码

#include"stdio.h"
#define M 6
#define P (M+1)
typedef struct HashTable
{
	int key;      //关键字 
	int EmptyFlag;//占用（冲突）标志，0表示没被占用，1表示被占用 
}HashTable;

void CreateHashTable( HashTable *tbl, int *data, int m, int p );
int SearchHashTable( HashTable *tbl, int key, int p );

int main()
{
	HashTable HashTbl[P];
	int data[M] = { 10, 8, 14, 15, 20, 31 };
	int i, loc;
	printf( "初始数据：\n" );
	for( i=0; i<M; i++ )
	{
		printf( "data[%d] = %5d\n", i, data[i] );
	}
	printf( "\n" );
	CreateHashTable( HashTbl, data, M, P );
	printf( "哈希表：  \n" );
	for( i=0; i<M; i++ )
	{
		printf( "tbl[%d] = %5d\n", i, HashTbl[i].key );
	}
	printf( "\n" );
	for( i=0; i<M; i++ )
	{
		loc = SearchHashTable( HashTbl, data[i], P );
		printf( "%5d 's loc = %5d\n", data[i], loc );
	}
	
	return 0;
}
void CreateHashTable( HashTable *tbl, int *data, int m, int p )
{
	int i, addr, k;
	for( i=0; i<p; i++ ) //把哈希表被占用标志置为0 
	{
		tbl[i].EmptyFlag = 0;
	}
	for( i=0; i<m; i++ )
	{
		addr = data[i] % p;//计算哈希地址 
		k = 0;//记录冲突次数 
		while( k++ < p )
		{
			if( tbl[addr].EmptyFlag == 0 )
			{
				tbl[addr].EmptyFlag = 1;//表示该位置已经被占用 
				tbl[addr].key   = data[i];
				break;
			}
			else
			{
				addr =  ( addr + 1 ) % p; //处理冲突 
			}
		}	
	}
}

int SearchHashTable( HashTable *tbl, int key, int p )
{
	int addr, k, loc;//loc表示查找位置下标，如果为0则表示查找失败 
	addr = key % P;//计算Hash地址 
	loc = -1; 
	k = 0;//记录冲突次数 
	while( k++ < p )
	{
		if( tbl[addr].key == key )
		{
			loc = addr;
			break;
		}
		else
		{
			addr =  ( addr + 1 ) % p; //处理冲突 
		}	
	}
	return loc;
}