C语言的少即是多:
从语言内容来讲,C绝对是足够精炼的,它提供且仅提供了我们工作所必须的编程元素。
从可以实现的功能以及能为我们提供的代码管理和性能支持上来看,它也做的恰到好处。
没有C++的繁琐、比脚本及所谓的OO语言更高效、当然也比汇编更容易理解。
不过对于用惯了Java的HashMap、LinkedHashMap,Python的Dict,以及PHP的Array 的同学来说,C的简洁似乎就有些简陋,甚至是蹩脚了。
最近项目中需要在C语言中使用HashTable来提高按键的查找速度,在网上找了很多现成的实现,发现写的都很随意,都有问题。很多现有的实现版本中都是使用char*作为key,void*作为值,这种做法最简单,但内存效率和计算效率都不高。
这种方案面临一个问题,就是:HashTable是否要申请新的内存空间来保存key和value的值,而不是只记录指针的值。
如果不保存,则指针指向的内存区可能会被其他代码销毁,则内容会丢失,程序会失败。
如果保存,就需要进行频繁的内存申请和销毁,尤其是当键或值是语言内置的基础类型(比如char、int、long、short、float、double)时,存放值的内存大小比存放指针值的内存还小。会导致更多的小块内存的操作和内存碎片。
为了能够让C更好地为我们的工作服务,我决定自己搞一个HashTable。
具体需求:
- 在我的项目中,很多情况下HashTable的key和value都是内置基础类型(如int、double),字符串的情况也比较多,其他的复杂情况极少。即我们的HashTable更多的是处理内置类型数据或者字符串数据。
- 需要支持对key、value按照插入顺序进行遍历。
我们的方案:
- 考虑到内置类型的size最大只有8Byte,而且所有指针本身的大小也是8Byte(64bit 的机器),因此我们只需要一个8Byte的空间来存错所有的基础类型的值,或者指针(一般是char*)。这样当面对基础类型的时候,不需要malloc额外的空间来存储,在遇到字符串类型(char*)的数据时,使用malloc申请内存空间存储字符串内容,并将指针存在这个8Byte的空间中。
- 同时HashTable要维护当前key和value的类型是什么,需要在插入数据和查找数据时根据key和value的类型做对应的类型转换。
- key和value都支持有限的类型:key的类型只支持int、long、char*;value的类型支持char、short、int、long、float、double、char*。
- 至于按照插入顺序进行遍历,则只需要对插入的每个元素维护一个全局的指针域即可,这个可以参考Java中LinkedHashMap的实现。
数据结构设计:
考虑到上述情况,我们对HashTable的结构设计如下:
#define VLEN 8 #define TNLEN 32 typedef unsigned long ulong; typedef unsigned int uint; typedef struct _bucket { ulong h; /* hash value of key, keyvalue if key is a uint or ulong */ char * key; /* the point to key , if key is a string */ char value[VLEN]; /* store a var of builtin type in a 8Byte buffer */ struct _bucket *pListNext; struct _bucket *pListLast; struct _bucket *pNext; struct _bucket *pLast; } Bucket; typedef struct _hashtable{ int nTableSize; int nTableMask; int nNumOfElements; char keyType[TNLEN]; /* can be "int","long","char*" */ char valueType[TNLEN]; /* can be "char","short","int","long","float","double","char*" */ Bucket * pInternalPointer; Bucket * pListHead; Bucket * pListTail; Bucket ** arBuckets; } HashTable;
内存结构:
/*创建HashTable实例*/ HashTable * ht = create_hashtable(100,char*,double); /*key:char*,value:double*/ /*插入元素"xiaoqiang" => 1234.567 */ hash_add("xiaoqiang",1234.567); /*插入元素"helloworld" => 234567.891 */ hash_add("helloworld",234567.891); /*遍历元素*/ char * key = NULL; double value = 0.0; for (reset(ht);isnotend(ht);next(ht)){ key = skey(ht); /*获取当前字符串key*/ value = *(double*)value(ht); /*获取当前double类型的value值,需要做类型转换*/ printf("key: %s, value:%lf\n",key,value); }
接口设计:
为了向用户提供上述访问HashTable内容的方式,我们对HashTable的访问接口设计如下:
#define create_hashtable(size, ...) \ _create_hashtable(size, #__VA_ARGS__) #define hash_add(ht,key,value) \ _hash_add((ht),(key),(value)) #define hash_find(ht,key,value) \ _hash_find((ht),(key),(value)) #define hash_del(ht,key) \ _hash_del((ht),(key)) #define hash_exists(ht,key) \ _hash_exists((ht),(key)) #define reset(ht) ((ht)->pInternalPointer = (ht)->pListHead) #define next(ht) ((ht)->pInternalPointer = (ht)->pInternalPointer->pListNext) #define isnotend(ht) ((ht)->pInternalPointer != NULL) #define nkey(ht) ((ht)->pInternalPointer->h) #define skey(ht) ((ht)->pInternalPointer->key) #define value(ht) ((ht)->pInternalPointer->value) HashTable * _create_hashtable(uint size, const char* s_typename); int _hash_add(HashTable * ht, ...); int _hash_find(HashTable * ht, ...); int _hash_del(HashTable * ht, ...); int _hash_exists(HashTable * ht, ...); int hash_num_elements(HashTable * ht); void hash_free(HashTable * ht);
上述结构设计和接口设计共同构成了我们HashTable的头文件hashtable.h
剩下的就是实现_create_hashtable、_hash_add、_hash_add、_hash_find、_hash_del、_hash_exists、hash_num_elements和hash_free函数了。
具体的实现细节和更多的测试用例,就不在此一一列出。
用户可以访问该项目在googlecode上的地址:https://code.google.com/p/c-hash/
里面有完整的项目代码,并提供动态库libht.so,及静态库libhts.a 的库文件.
最后,欢迎拍砖和提出各种改进意见。
相关推荐
c语言实现hashtable,一个key可以对应多个data,c语言实现
根据KEY从hashtable中获取接点,步骤是先根据KEY计算hash值,然后从hashtable中找到指定的接点或者接点链表
哈希表效率高,众所周知。应用广泛,php中大部分存储使用的都是hashtable,包括变量,数组…如何使用c语言实现hashtable呢,现提供自己的思路,如有不妥之处,敬请赐教
这是一个用c语言实现hashtable的例子, 里面适应折叠法实现散列函数,使用链表法处理冲突;
用c语言实现的hash表,,c程序员数据结构必备。。
这是一个C语言编写的程序,在winTC下调试 用其他的编译程序的话 需要进行少量的修改~!
哈希表 哈希表_使用C语言实现哈希表数据结构_HashTable
根据算法导论上的HashTable, C语言实现
该资源提供一份头文件和实现文件(.h + .c),功能主要包含了哈希表的创建、添加键值、修改键值、统计键值数量、回调自定义、清空哈希表、删除哈希表,基本够用。
哈希表的哈希取余法和链表地址法来实现哈希表的基本操作。。。
18. C语言实现动态数组 100 19. C语言笔试-运算符和表达式 104 20. C语言编程准则之稳定篇 107 21. C语言编程常见问题分析 108 22. C语言编程易犯毛病集合 112 23. C语言缺陷与陷阱(笔记) 119 24. C语言防止缓冲区...
c语言Hashtable表的实现,和部分函数。仅供参考。
使用链表实现了哈希表,定义了节点结构体 struct Node 和哈希表结构体 struct Hashtable。 实现了创建哈希表的函数 createHashtable,哈希函数 hash,插入键值对的函数 insert,查找键对应值的函数 get,删除指定键...
18. C语言实现动态数组 100 19. C语言笔试-运算符和表达式 104 20. C语言编程准则之稳定篇 107 21. C语言编程常见问题分析 108 22. C语言编程易犯毛病集合 112 23. C语言缺陷与陷阱(笔记) 119 24. C语言防止缓冲区...
哈希表结构 struct HashTable:表示哈希表,包含一个存储节点指针的数组。 创建哈希表函数 createHashTable:动态分配哈希表的内存,并初始化哈希表数组为NULL。 哈希函数 hashCode:根据键计算哈希值,采用简单的...
18. C语言实现动态数组 100 19. C语言笔试-运算符和表达式 104 20. C语言编程准则之稳定篇 107 21. C语言编程常见问题分析 108 22. C语言编程易犯毛病集合 112 23. C语言缺陷与陷阱(笔记) 119 24. C语言防止缓冲区...
18. C语言实现动态数组 100 19. C语言笔试-运算符和表达式 104 20. C语言编程准则之稳定篇 107 21. C语言编程常见问题分析 108 22. C语言编程易犯毛病集合 112 23. C语言缺陷与陷阱(笔记) 119 24. C语言防止缓冲区...
18. C语言实现动态数组 100 19. C语言笔试-运算符和表达式 104 20. C语言编程准则之稳定篇 107 21. C语言编程常见问题分析 108 22. C语言编程易犯毛病集合 112 23. C语言缺陷与陷阱(笔记) 119 24. C语言防止缓冲区...