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