哈希游戏化：系统开发时哈希表查找算法的实现

哈希表查找算法的实现

首先定义一个散列表的结构以及一些相关的常数。其中，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[i] = 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);如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。