发帖
雷达卡
哈希表查找算法的实现
首先定义一个散列表的结构以及一些相关的常数。其中，HashTables是散列表结构。结构当中的elem为一个动态数组。
#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12 /*定义哈希表长为数组的长度*/
#define NULLKEY -32768
{
int *elem; /*数组元素存储基址，动态分配数组*/
int count; /*当前数据元素的个数*/
}HashTable;
int m = 0;
初始化哈希表
/*初始化哈希表*/
Status InitHashTable(HashTable *H)
{
int i;
m = HASHSIZE;
H->count = m;
H->elem = (int *)malloc(m*sizeof(int));
for(i = 0;i<m;i )
H->elem = NULLKEY;
return OK;
}
定义哈希函数
/*哈希函数*/
int Hash(int key)
{
return key % m; /*除留取余法*/
}
插入操作
/*将关键字插入散列表*/
void InsertHash(HashTable *H,int key)
｛
int addr = Hash(Key); /*求哈希地址*/
while(H->elem[addr] != NULLKEY) /*如果不为空则冲突*/
addr = (addr 1) % m; /*线性探测*/
H->elem[addr] = key; /*直到有空位后插入关键字*/
｝
查找操作
/*查找*/
Status SearchHash(HashTable H,int key,int *addr)
{
*addr = Hash(key); /*求哈希地址*/
while(H.elem[*addr] != key) /*若不为空，则冲突*/
｛
*addr = (*addr 1) % m; /*线性探测*/
if(H.elem[*addr) == NULLKEY || *addr == Hash(key))
{/*如果循环回到原点*/
return UNSUCCESS; /*则说明关键字不存在*/
}
｝
return SUCCESS;
}
7、总结
１、哈希表就是一种以键值对存储数据的结构。
2、哈希表是一个在空间和时间上做出权衡的经典例子。如果没有内存限制，那么可以
直接将键作为数组的索引。那么所查找的时间复杂度为Ｏ(1);如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。
京公网安备 11010802022788号
