哈希表查找算法的实现

首先定义一个散列表的结构以及一些相关的常数。其中，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;     /*除留取余法*/
1
}

插入操作

/将关键字插入散列表/

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
2
3
直接将键作为数组的索引。那么所查找的时间复杂度为Ｏ(1);如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。