你好,游客 登录 注册 搜索
背景:
阅读新闻

开地址哈希表(Hash Table)的接口定义与实现分析

[日期:2018-01-11] 来源:Linux社区  作者:idreamo [字体: ]

开地址哈希函数的接口定义

基本的操作包括:初始化开地址哈希表、销毁开地址哈希表、插入元素、删除元素、查找元素、获取元素个数。

各种操作的定义如下:

ohtbl_init


 int ohtbl_init (OHTbl *htbl, int positions, int (*h1) (const void *key), int (*h2)(const void *key),

                    int (*match)(const void *key1, const void *key2), void (*destroy)(void *data));

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

描述  初始化开地址哈希表htbl。在对哈希表进行其他操作之前,必须首先进行初始化。

参数positions 指定表中的槽位个数。函数指针h1,h2用来指定用户定义的辅助哈希函数以完成双散列过程。函数指针match指向一个用户定义的函数,此函数用于判断两个键是否匹配,它的使用方法与chtbl_init中的match类似。函数指针destroy通过调用ohtbl_destroy来释放动态分配的内存空间,同样它与ohtbl_init中参数的使用方法类似。如果哈希函数表中的数据不需要释放,那么destroy应该指向NULL。

复杂度  O(m),m是哈希表中槽的个数。

ohtbl_destroy


 void ohtbl_destroy (OHTbl *htbl ) ;

返回值  无 。

描述  销毁htbl指定的开地址哈希表。在调用ohtbl_destroy之后不再允许进行其他操作,除非再次初始化。

ohtbl_destroy会删除哈希表中的所有元素,并同时释放ohtbl_init中参数destroy不为NULL的成员所占用的内存空间。

复杂度  O(m),m是哈希表中槽的个数。

ohtbl_insert


 int ohtbl_insert (OHTbl *htbl,const void *data ) ;

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

描述  向htbl指定的开地址哈希表中插入一个元素

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

复杂度  O(1)。

ohtbl_remove


 int ohtbl_remove (OHTbl *htbl,const void **data ) ;

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

描述  从htbl指定的开地址哈希表中删除与data匹配的元素

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

复杂度  O(1)。

ohtbl_lookup


 int ohtbl_lookup (const OHTbl *htbl,const void **data ) ;

返回值  如果在表中找到元素,返回0;否则,返回-1 。

描述  查找htbl指定的开地址哈希表中是否有与data匹配的元素

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

复杂度  O(1)。

ohtbl_size


 int ohtbl_size (const OHTbl *htbl ) ;

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

描述  获取哈希表中元素个数的宏

复杂度  O(1)。

开地址哈希表的实现与分析

实现分为两个文件,一是开地址哈希表的头文件,一是抽象数据类型的实现文件。

示例1:开地址哈希表的头文件

/*ohtbl.h*/
#ifndef OHTBL_H
#define OHTBL_H #include <stdlib.h> /*定义开地址哈希表的数据结构*/ typedef struct OHTbl_ { int positions; /*1指明哈希表中分配的槽位数目*/ void *vacated; /*2指向一个特殊的地址空间,这个特殊的地址上曾经删除过一个元素*/ int (*h1)(const void *key); /*3辅助哈希函数*/ int (*h2)(const void *key); /*4辅助哈希函数*/ int (*match)(const void *key1,const void *key2); /*5判断两个元素是否匹配*/ void (*destroy)(void *data); /*6销毁函数*/ int size; /*7现有的元素数目*/ void **table; /*8存储元素的数组*/ } OHTbl;
/*函数原型声明*/
int ohtbl_init(OHTbl *htbl, int positions, int (*h1)(const void *key), int (*h2)(const void *key),
int (*match)(const void *key1,const void *key2),void (*destroy)(void *data));

void ohtbl_destroy(OHTbl *htbl);

int ohtbl_insert(OHTbl *htbl, const void *data);

int ohtbl_remove(OHTbl *htbl, void **data);

int ohtbl_lookup(const OHTbl *htbl, void **data);

#define ohtbl_size(htbl)((htbl)->size)
#endif // OHTBL_H

 示例2:开地址哈希表抽象数据类型的实现

/*ohtbl.c*/
#include <stdlib.h>
#include <string.h>

#include "ohtbl.h"

/*为空出的元素预留一个特殊的内存地址*/
static char vacated;

/*ohtbl_init 初始化htbl指定的开地址哈希表*/
int ohtbl_init(OHTbl *htbl,int positions, int (*h1)(const void *key), int (*h2)(const void *key),
int (*match)(const void *key1, const void *key2),void (*destroy)(void *data))
{
int i;
/*为空分配空间*/
if((htbl->table = (void **)malloc(positions * sizeof(void *))) == NULL)
return -1;

/*初始化每个槽位,把每个槽位的指针设置为NULL*/
htbl->positions = positions;
for(i=0; i<htbl->positions; i++)
htbl->table[i] = NULL;

  /*将空出的成员设置为为此保留的特殊内存地址*/
    htbl->vacated = &vacated;
   
    /*封装4个函数*/
    htbl->h1 = h1;
    htbl->h2 = h2;
    htbl->match = match;
    htbl->destroy=destroy;
   
    /*初始化元素数量*/
    htbl->size = 0;
   
    return 0;
}

/*ohtbl_destroy 销毁htbl指定的开地址式哈希表*/
void ohtbl_destroy(OHTbl *htbl)
{
int i;

if(htbl->destroy != NULL)
{
for(i=0; i < htbl->positions; i++)
{
if(htbl->table[i] != NULL && htbl->table[i] != htbl->vacated)
htbl->destroy(htbl->table[i]);
}
}
/*释放表空间*/
free(htbl->table);

/*清除数据结构*/
memset(htbl,0,sizeof(OHTbl);

return;
}

/*ohtbl_insert 向表中插入元素*/
int ohtbl_insert(OHTbl *htbl,const void *data)
{
void *temp;
int position,i;

/*因为开地址哈希表有固定的大小,所以在插入之前必须保证有足够的空间放置元素*/
if(htbl->size == htbl->positions)
return -1;

/*相同的键不允许重复插入表中,插入之前调用htbl_lookup检查是否有相同的元素*/
temp = (void *)data;
if(ohtbl_lookup(htbl,temp) == 0)
return 1;

/*满足以上条件,使用双散列法在表中寻找未被占用的槽*/
for(i=0; i< htbl->positions; i++)
{
position = (htbl->h1(data) + (i*htbl->h2(data))) % htbl->positions;

if(htbl->table[position]==NULL || htbl->table[position]==htbl->vacated)
{
/*将元素插入表中*/
htbl->table[position] = (void *)data;
htbl->size++;
return 0;
}
}
/*选用了错误的哈希函数*/
return -1;
}

/*ohtbl_remove 删除htbl指定表中与data相匹配的元素*/
int ohtbl_remove(OHTbl *htbl,void **data)
{
int position,i;

/*通过双散列定位到要删除元素的位置*/
for(i=0; i<htbl->positions; i++)
{
position = (htbl->h1(*data) + (i * h2(*data))) % htbl->positions ;

if(htbl->table[position] == NULL)
{
/*没有找到匹配的数据*/
return -1;
}
else if (htbl->table[position] == htbl->vacated)
{
/*查找到了突出的位置,继续搜索*/
continue;
}
else if (htbl->match(htbl->table[position],*data))
{
/*将data指向正在删除的数据*/
*data = htbl->table[position];
/*将此槽位的地址放到vacated成员中*/
htbl->[position] = htbl->vacated;
htbl->size--;
return 0;
}
}
/*如果没有找到元素,则返回-1*/
return -1;
}

/*ohtbl_lookup 查找htbl指定的表中,与data相匹配的元素*/
int ohtbl_lookup(const OHTbl *htbl,void **data)
{
int position,i;

for(i=0; i<htbl->positions; i++)
{
position = (htbl->h1(*data) + (i * htbl->h2(*data)))% htbl->positions;

if(htbl->table[position] == NULL)
{
/*没有找到数据*/
retun -1;
}
else if(htbl->match(htbl->table[position],*data))
{
/*将data指向找到的数据*/
*data = htbl->table[position];
return 0;
}
}
return -1;
}

本文永久更新链接地址http://www.linuxidc.com/Linux/2018-01/150240.htm

linux
相关资讯       开地址哈希表  Hash Table 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款