100字范文 > 数据结构链式哈希表（Hash Table）的接口定义与实现分析（完整代码）

数据结构链式哈希表（Hash Table）的接口定义与实现分析（完整代码）

时间：2018-07-01 21:47:01

链式哈希表的接口定义

关于哈希表与链式哈希表的描述可以参阅：/idreamo/p/7990860.html

链式哈希表的操作与属性有：初始化、销毁、插入元素、删除元素、查找元素、获取哈希表中无数的个数。

chtbl_init

int cltbl_init(CHTbl *htbl, int buckts, int (*h)(const void *key), int (*match)(const void *key1,const void *key2), void (*destroy)(void *data));

返回值：如果哈希表初始化成功，返回0，否则返回-1。

描述：初始化htbl指定的链式哈希表。

在对链式哈希表执行其他操作之前，必须要先初始化。哈希表中所分配的“桶”的个数将由buckets指定。函数指针h指向一个用户定义的哈希函数，此函数会将键进行散列。函数指针match指向一个用户定义的函数，此函数用于判断两个键是否匹配。如果key1等于key2，返回1；否则返回其他值。参数destroy是一个函数指针，通过调用chtbl_destroy来释放动态分配的内存空间。如果哈希表中的数据不需要释放，那么destroy应该指向NULL。

复杂度： O(m)，m是哈希表中“桶”的个数。

chtbl_destroy

void cltbl_destroy(CHTbl *htbl);

返回值：无。

描述：销毁htbl指定的链式哈希表。

在调用chtbl_destroy之后不再允许进行其他操作，除非再次调用chtbl_init。chtbl_destroy会删除哈希表中的所有元素，并同时释放chtbl_init中参数destroy不为NULL的成员所占用的内存空间。

复杂度： O(m)，m是哈希表中“桶”的个数。

chtbl_insert

int cltbl_insert(CHTbl *htbl,const void *data);

返回值：如果插入元素成功则返回0；如果哈希表中已经包含此元素，返回1；否则返回-1。

描述：向htbl指定的链式哈希表中插入一个元素。

新元素包含一个指向data的指针，只要元素仍然存在于哈希表中，此指针就一直有效。与data相关的内存空间将由函数的调用者来管理。

复杂度： O(m)，m是哈希表中“桶”的个数。

chtbl_remove

int cltbl_remove(CHTbl *htbl,const void **data);

返回值：如果删除元素成功则返回0；否则返回-1。

描述：从htbl指定的链式哈希表中删除与data匹配的元素。

返回时data指向已经删除元素中存储的数据。与data相关的内存空间将由函数的调用者来管理。

复杂度： O(1)

chtbl_lookup

int cltbl_lookup(const CHTbl *htbl,const void **data);

返回值：如果在哈希表中找到元素则返回0；否则返回-1。

描述：查找htbl指定的链式哈希表中与data相匹配的元素。

如果找到，在函数返回时，data将指向哈希表中相匹配元素中的数据。

复杂度： O(1)

chtbl_size

int cltbl_size(CHTbl *htbl);

返回值：哈希表中的元素个数。

描述：获取htbl指定的链式哈希表的元素个数的宏。

复杂度： O(1)

链式哈希表的实现与分析

示例：链式哈希表抽象数据类型的头文件

#ifndef CHTBL_H#define CHTBL_H#include <stdlib.h>#include "list.h"/*为哈希表定义一个数据结构*/typedef struct CHTbl_{int buckets; /*1、表中分配的“桶”的个数*/int (*h)(const void *key);/*2、指向哈希函数*/int (*match)(const void *key1, const void *key2); /*3、指向match函数*/int (*destroy)(void *data); /*4、指向销毁函数*/int size; /*5、表中元素的数量*/List *table; /*6、存储“桶”的数组*/}CHTbl;/*公用接口*/int chtbl_init(CHTbl *htbl, int buckets, int(*h)(void *key), int (*match)(const void *key1, const void *key2), void(*destroy)(void *data));int chtbl_destroy(CHTbl *htbl);int chtbl_insert(CHTbl *htbl, const void *data);int chtbl_remove(CHTbl *htbl,void **data);int chtbl_lookup(const CHTbl *htbl,void **data);#define chtbl_size(htbl)((htbl)->size)#endif // CHTBL_H

示例：链式哈希表的实现

#include <stdlib.h>#include <string.h>#include "list.h"#include "chtbl.h"/*chtbl_init 初始化链式哈希表*/int chtbl_init(CHTbl *htbl, int buckets, int (*h)(const void *key),int (*match)(const void *key1,const void *key2),void (*destroy)(void *data)){int i;/*首先，为“桶”分配空间*/if((htbl->table = (List *)malloc(buckets*sizeof(List)))==NULL)return -1;/*然后，调用list_init初始化这些桶*/htbl->buckets = buckets;for(i=0;i<htbl->buckets;i++)list_init(&htbl->table[i],destroy);/*接着，封装h,match,destroy函数*/htbl->h = h;htbl->match = match;htbl->destroy = destroy;/*最后，将size值设置为0*/htbl->size = 0;return 0;}/*chtbl_destroy 销毁链式哈希表*/void chtbl_destroy(CHTbl *htbl){int i;/*首先，删除每个“桶”中的元素*/for(i=0;i<htbl->buckets;i++){list_destroy(&htbl->table[i]);}/*然后，释放由chtbl_init分配的内存空间*/free(htbl->table);/*最后，哈希表不再允许任何操作，清除这一结构作为错误预防*/memset(htbl,0,sizeof(CHTbl));return ;}/*chtbl_insert 向链式哈希表中插入元素*/int chtbl_insert(CHTbl *htbl,const void *data){void *temp;int bucket,retval;/*首先，调用chtbl_lookup检查哈希表中是否已经存有该元素*/temp = (void *)data;if(chtbl->lookup(htbl,&temp)==0)return 1;/*如果未存有该元素，接着将新元素的键散列*/bucket = htbl->h(data) % htbl->buckets;/*然后，根据哈希编码将新元素插入哈希表中相应位置的“桶”中*/if((retval = list_ins_next(&htbl->table[bucket],NULL,data))==0)htbl->size++;return retval;}

/*chtbl_remove 删除表中的元素*/

int chtbl_remove(CHTbl *htbl,void **data)

{

ListElmt *element,*prev;

int bucket;

/*首先，哈希(散列)元素的键*/

bucket = htbl->h(*data)%htbl->buckets;

/*接着，查找与元素的键相匹配的桶*/

prev = NULL;

for(element = list_head(&htbl->table[bucket]);element != NULL; element = list_next(element))

{

if(htbl->match(*data,list_data(element)))