利用C语言实现HashTable

HashTable是在实际应用中很重要的一个结构,下面讨论一个简单的实现,虽然简单,但是该有的部分都还是有的。

一,访问接口
创建一个hashtable.
hashtable hashtable_new(int size) /其中size表示包含的接点个数。

存入key-value至hashtable中。
void hashtable_put(hashtable h,const char* key,void *val);

根据key从hashtable中取出value值。
void * hashtable_get(hashtable h,const char *key);

释放hashtable。
void hashtable_free(hashtable h);

释放单个hash 接点
void hashtable_delete_node(hashtable h, const char *key);

二,数据结构
hash接点的结构:


代码如下:

typedef struct hashnode_struct{
struct hashnode_struct *next;
const char *key;
void *val;
}*hashnode,_hashnode;

这个结构还是很容易理解的,除了必须的key-value之外,包含一个用于冲突的链表结构。
hashtable的数据结构:


代码如下:

typedef struct hashtable_struct{
pool_t p;
int size;
int count;
struct hashnode_struct *z;
}*hashtable,_hashtable;

对这个结构说明如下:
pool_t:内存池结构管理hashtable使用的内存。结构参考"C语言内存池使用模型"
size:当前hash的接点空间大小。
count:用于表示当前接点空间中可用的hash接点个数
z:用于在接点空间中存储接点。

三,创建hashtable
代码如下:


代码如下:

hashtable hashtable_new(int size)
{
hashtable ht;
pool_t p;
p = _pool_new_heap(sizeof(_hashnode)*size + sizeof(_hashtable));
ht= pool_malloc(p, sizeof(_hashtable));
ht->size = size;
ht->p = p;
ht->z = pool_malloc(p, sizeof(_hashnode)*prime);
return ht;
}

这个函数比较简单,先定义并初始化一个内存池,大小根据size而定,所以在实际使用时,我们的size应该要分配的相对大点,比较好。

四,存入key-value值
在这个操作之前,先要定义一个根据KEY值计算hashcode的函数。


代码如下:

static int hashcode(const char *s, int len)
{
const unsigned char *name = (const unsigned char *)s;
unsigned long h = 0, g;
int i;
for(i=0;i
{
h = (h 《 4) + (unsigned long)(name[i]); //hash左移4位,当前字符ASCII存入hash
if ((g = (h & 0xF0000000UL))!=0)
h ^= (g 》 24);
h &= ~g; //清空28-31位。
}
return (int)h;
}

这个函数采用精典的ELF hash函数。
代码如下:


代码如下:

void hashtable_put(hashtable h, const char *key, void *val)
{
if(h == NULL || key == NULL)
return;
int len = strlen(key);
int index = hashcode(key,len);
hashtable node;
h->dirty++;
if((node = hashtable_node_get(h, key,len, index)) != NULL) //如果已经存在,就替换成现在的值,因为现在的比较新。
{
n->key = key;
n->val = val;
return;
}
node = hashnode_node_new(h, index); // 新建一个HASH NODE接点。
node->key = key;
node->val = val;
}
hashtable_node_get用于查找该KEY是否在HASH中已经存在,实现很简单,如下:
static hashnode hashtable_node_get(hashtable h, const char *key, int len, int index)
{
hashnode node;
int i = index % h->size;
for(node = &h->z[i]; node != NULL; node = node->next) // 在index值 [HASH值] 所对应的HASH桶上遍历寻找
if(node->key != NULL && (strlen(node->key)==len) && (strncmp(key, node->key, len) == 0))
return node;
return NULL;
}

新建一个HASH NODE接点如下:


代码如下:

static hashnode hashnode_node_new(hashtable h, int index)
{
hashnode node;
int i = index % h->size;
h->count++;
for(node = &h->z[i]; node != NULL; node = node->next)
if(node->key == NULL) //这里的处理是:如果在HASH桶中存在某个值,KEY是空的,表明这个值已经没有用了,就用它来替换为现在准备写入的新接点。
return node;
node = pool_malloc(h->p, sizeof(_hashnode)); // 新建一个接点
node->next = h->z[i].next; // 加入到桶中,就是加到链表的第一个接点。
h->z[i].next = node;
return node;
}

五,从HASHTABLE中获取接点
根据KEY从hashtable中获取接点,步骤是先根据KEY计算hash值,然后从hashtable中找到指定的接点或者接点链表。如下:


代码如下:

void *hashtable_get(hashtable h, const char *key)
{
if(h == NULL || key == NULL)
return NULL;
hashnode node;
int len = strlen(key);
if(h == NULL || key == NULL || len <= 0 || (node = hashtable_node_get(h, key, len, hashcode(key,len))) == NULL)
{
return NULL;
}
return node->val;
}

这个函数就很容易理解了。

六,释放HASHTABLE
hashtable的释放就比较简单了,因为我们所有的内存申请都在内存池上完成的,就只需要释放内存池,如下:


代码如下:

void hashtable_free(hashtable h)
{
if(h != NULL)
pool_free(h->p);
}

七,释放单个hash接点
代码如下:


代码如下:

void hashtable_delete_node(hashtable h, const char *key)
{
if(h == NULL || key == NULL)
return;
hashnode node;
int len = strlen(key);
if(h == NULL || key == NULL || (node = hashtable_node_get(h, key, len, hashcode(key,len))) == NULL) //没有这个接点
return;
node->key = NULL;
node->val = NULL;
h->count--;
}

这个就实现了一个简单的HASHTABLE结构,当然后还是有不足的,比如遍历HASHTABLE,如果用数组的方式来遍历,效率肯定很低,下面讨论一种实现方案,用于遍历hashtable.

八,hashtable的遍历讨论
直接用数组,就是hashtable中的struct hashnode_struct数组是可以遍历,但如果只包含一个接点,也要遍历所有的数组,如下遍历:


代码如下:

void hashtable_traverse(hashtable h)
{
int i;
hashnode node;
if(h == NULL)
return;
for(i = 0; i < h->prime; i++)
for(node = &h->z[i]; node != NULL; node = node->next)
if(node->key != NULL && node->val != NULL)
XXXXXXXXXXXXXXXXX // 这里是一些操作。
}

这样效率很低,其实在接点中包含了next域,可以用这个来实现遍历。
需要对前面hashtable数据结构做简单的改动,增加两个域:


代码如下:

typedef struct hashtable_struct{
pool_t p;
int size;
int count;
struct hashnode_struct *z;
int bucket;
hashnode node;
}*hashtable,_hashtable;

就是增加了bucket和node两个域,加这两个域的思路是这样的:
node表示当前遍历的游标,在遍历过程中,不断的移动这个接点所指向的接点。
bucket是和node相关联的,用于记录当前的node在哪个桶上。
首先建立连接,就是将所有的接点都连接起来,按照惯例,也采用XXX_iter_first函数,先初始化,如下:


代码如下:

int hashtable_iter_first(hashtable h) {
if(h == NULL)
return 0;
h->bucket = -1;
h->node = NULL;
return hashtable_iter_next(h);
}
hashtable_iter_next用于获取下一个接点,如果这时游标已经确定,那下一个接点就会被很快的被确定,定义如下:
int xhash_iter_next(xht h) {
if(h == NULL) return 0;
while(h->node != NULL) {
h->node = h->node->next; // 移向下一个接点,如果接点合法,返回成功
if(h->node != NULL && h->node->key != NULL && h->node->val != NULL)
return 1;
}
for(h->bucket++; h->bucket < h->prime; h->bucket++) {
h->node = &h->z[h->bucket];
while(h->node != NULL) {
if(h->node->key != NULL && h->node->val != NULL)
return 1;
h->node = h->node->next;
}
}
h->bucket = -1; // 不存在下一个接点。
h->node = NULL;
return 0;
}

有了上面两个方法之后,遍历操作如下:


代码如下:

hashtable ht
if(hashtable_iter_first(ht)) //取第一个接点。
do{
// 此时可以处理ht->node,表示当前的接点。
}while(hashtable_iter_next(ht)); //取下一个接点

这样处理的话, 是不是高效多了。当然在第一遍的时候,还是需要遍历整个数组和数组下的桶中接点。不过这样操作之后,在删除一个结点的时候,就需要做一些操作。删除一个接点时,需要考虑当前的h->node是不是当前被删除的接点,如果是,就把h->node称至下一个接点。就是删除之后,要作如下处理,假如删除了。

假如被删除的接点为node,需要如下处理:
if(h->node == n)
hashtable_iter_next(h);
将h->node移动到下一个接点。

(0)

相关推荐

  • javascript 哈希表(hashtable)的简单实现

    首先简单的介绍关于属性的一些方法: 属性的枚举: for/in循环是遍历对象属性的方法.如 复制代码 代码如下: var obj = { name : 'obj1', age : 20, height : '176cm' } var str = ''; for(var name in obj) { str += name + ':' + obj[name] + '\n'; } alert(str); 输出为:name:obj1 age:20 height:176cm 检查属性是否存在: in运算

  • c语言实现的hashtable分享

    头文件 hashtable.h 复制代码 代码如下: typedef struct _Bucket{    char *key;    void *value;    struct _Bucket *next;} Bucket; typedef struct _HashTable{    int size;    int total;    struct _Bucket *buckets;} HashTable; int hash_init(HashTable **ht);int hash_fi

  • 浅析java中ArrayList与Vector的区别以及HashMap与Hashtable的区别

    就ArrayList与Vector主要从二方面来说.一.同步性:Vector是线程安全的,也就是说是同步的,而ArrayList是线程序不安全的,不是同步的 二.数据增长:当需要增长时,Vector默认增长为原来一培,而ArrayList却是原来的一半 就HashMap与HashTable主要从三方面来说.一.历史原因:Hashtable是基于陈旧的Dictionary类的,HashMap是Java 1.2引进的Map接口的一个实现 二.同步性:Hashtable是线程安全的,也就是说是同步的,

  • javascript hashtable实现代码

    复制代码 代码如下: var arr = new Array(); arr['item1'] = 'the value of item 1 '; arr['item2'] = 'the value of item 2 '; alert(arr['item1']); alert(arr['item2']); 但上述功能,不符我们的实际要求,另外查询遍历也不方便,我们需要在Array的基础上进行扩展, 下面我们可以用js中的数组来实现类似的hashtable的功能, 复制代码 代码如下: funct

  • java中vector与hashtable操作实例分享

    众所周知,java中vector与hashtable是线程安全的,主要是java对两者的操作都加上了synchronized,也就是上锁了.因此 在vector与hashtable的操作是不会出现问题.但是有一种情况:就是将一个hashtable copy到另一个hashtable时,假如使用putAll方法的花,会抛出一个 java.util.ConcurrentModificationException异常.先上代码: TestSync.java 复制代码 代码如下: public clas

  • javascript hashtable 修正版 下载

    修正hashtableobj.set("length","0") bug 可以设置key忽略大小写 可以clone hashtable对象 可以 使用obj.valueOf("key","defalutvalue") 设置默认值等等 欢迎修正bug 复制代码 代码如下: <html> <head> <script type="text/javascript"> // Au

  • 详解C#中HashTable的用法

    一,哈希表(Hashtable)简述 在.NET Framework中,Hashtable是System.Collections命名空间提供的一个容器,用于处理和表现类似keyvalue的键值对,其中key通常可用来快速查找,同时key是区分大小写:value用于存储对应于key的值.Hashtable中keyvalue键值对均为object类型,所以Hashtable可以支持任何类型的keyvalue键值对. 二,哈希表的简单操作 在哈希表中添加一个keyvalue键值对:HashtableO

  • JAVASCRIPT HashTable

    function Hashtable() {     this._hash        = new Object();     this.add        = function(key,value){                         if(typeof(key)!="undefined"){                             if(this.contains(key)==false){                             

  • 利用C语言实现HashTable

    HashTable是在实际应用中很重要的一个结构,下面讨论一个简单的实现,虽然简单,但是该有的部分都还是有的. 一,访问接口 创建一个hashtable. hashtable hashtable_new(int size) /其中size表示包含的接点个数. 存入key-value至hashtable中. void hashtable_put(hashtable h,const char* key,void *val): 根据key从hashtable中取出value值. void * hash

  • 利用Go语言追加内容到文件末尾

    前言 我研究了file库,终于让我找到了利用Go语言追加内容到文件末尾的办法 主要的2个函数: func (f *File) Seek(offset int64, whence int) (ret int64, err error) func (f *File) WriteAt(b []byte, off int64) (n int, err error) Seek()查到文件末尾的偏移量 WriteAt()则从偏移量开始写入 以下是例子: // fileName:文件名字(带全路径) // c

  • 利用C语言编辑画图程序的实现方法(推荐)

    不知道大家在进行开发县级电网调度自动化系统的时候,是否都会遇到一个问题就是:要绘制一个电力系统一次接线图.大家都应该知道其实电力系统的一次接线图是较为复杂的,如果想要使用一般的编程方法来进行绘制的话,基本上就是行不通的.那么我们应该怎样才可以更加的高效直接呢?今天小编就会给大家介绍一个方法,那就是:利用C语言编辑画图程序的实现方法.希望这篇教程对于大家有所帮助. 一.实现方法 在教程开始之前,小编先为大家介绍一下在编程程序里面早已定义了几个特殊按钮.为什么小编要为大家介绍这几个特殊按钮呢?那是因

  • 利用C语言替换文件中某一行的方法

    文件中存贮的内容如下所示: 11 1122 0 1122 * * 0 0 22 222 0 222 * * 0 0 33 333 0 333 * * 0 0 通过使用下面的几个函数,fopen,fprintf,fscanf,fseek,ftell . 具体的函数函数原型如下所示: FILE*fopen(const char*filename,const char *mode); int fprintf(FILE*stream,const char *format,...) int fscanf(

  • 利用 Go 语言编写一个简单的 WebSocket 推送服务

    本文中代码可以在 github.com/alfred-zhong/wserver获取. 背景 最近拿到需求要在网页上展示报警信息.以往报警信息都是通过短信,微信和 App 推送给用户的,现在要让登录用户在网页端也能实时接收到报警推送. 依稀记得以前工作的时候遇到过类似的需求.因为以前的浏览器标准比较陈旧,并且那时用 Java 较多,所以那时候解决这个问题就用了 Comet4J.具体的原理就是长轮询,长链接.但现在毕竟 html5 流行开来了,IE 都被 Edge 接替了,再用以前这种技术就显得过

  • 利用C语言编写“剪刀石头布”小游戏

    前言 大家好~ 我是一名C语言初学者,学了C语言基础后,我制作了一个小游戏:剪刀石头布. 希望大家能对我的思路和代码提出小Tips(eg.更简便的方法与程序) 我也会虚心接受大家的建议~ 一.游戏原理 "剪刀石头布"这个游戏,想必大家都很熟悉了. 两个人在玩游戏时,事先都不知道对方将要出什么,这中间存在着一种随机性. 而这种随机性相当于C语言里stdlib.h库中rand()函数,rand()函数用来产生随机数,因为rand是根据提供给srand()的种子值返回一个随机数,所以要使每次

  • 利用C语言如何实现一些简单图形的打印

    1#define_CRT_SECURE_NO_WARNINGS 1 因为笔者采用的是VS的编译环境所以有了上面的这一句话 我们都知道平面图形是由一条条线段构成,所以我们就先实现线段的打印 //打印自定义长度的线段 #include<stdio.h> int main() { int i = 0; int n; while (~scanf("%d", &n)) { for (i = 0; i < n; i++) printf("* "); p

  • Linux中利用c语言删除某个目录下的文件

    利用c语言删除目录下文件 最近这段时间工作内容是关于Linux下的简单文件操作,以前对于Linux系统下的文件操作函数都不是太熟悉,经过这次实践,对这些函数使用有了一定的了解 如何创建文件,读写文件,这些简单的我想大家应该是比较熟悉的,我所介绍的是如何遍历某个目录,并且删除该目录下的文件(可以指定后缀名),并且也可以指定 文件的修改时间范围(多少小时以前的旧文件可以删除),下面就是简单的函数实现,仅供初学者参考(毕竟我也是初学者\(^o^)/~) #include <stdio.h> #inc

  • 教你利用R语言测试电脑的性能

    利用R语言测试电脑的性能如何 同事新配了一个电脑,想用R语言编写一个程序,看一下电脑性能如何,让我写个代码测试一下. 我能怎么样,我也不懂如何测试电脑啊,那就计算一下矩阵的运算吧.因为我理解的电脑运行性能就是矩阵计算了. 编写代码 rm(list=ls()) set.seed(123) # 设置矩阵的行数 n = 10000 # 生成一个矩阵 value = rnorm(n*n, 10,3) mat = matrix(value,n,n) # 测试电脑性能 system.time({ # 矩阵求

  • 如何利用C语言位运算解决只出现一次的数字

    解题所需要的C语言基础知识 hello!从现在开始就进入本题解的正式内容了.首先给大家用图解的方式介绍3个C语言位运算的基本操作符 & | ^ 这些知识对下面的解题都非常重要,一定要熟练掌握,不然等会会有一种"我在哪,我是谁我在干什么"的感觉. 只出现一次的数字I 题目描述 只出现一次的数字 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次.找出那个只出现了一次的元素. 说明: 你的算法应该具有线性时间复杂度. 你可以不使用额外空间来实现吗? 示例 1:

随机推荐