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