最近项目中需要在C语言中使用HashTable来提高按键的查找速度，在网上找了很多现成的实现，发现写的都很随意，都有问题。
很多现有的实现版本中都是使用char*作为key，void*作为值，这种做法最简单，但内存效率和计算效率都不高。
这种方案面临一个问题，就是：HashTable是否要申请新的内存空间来保存key和value的值，而不是只记录指针的值。
如果不保存，则指针指向的内存区可能会被其他代码销毁，则内容会丢失，程序会失败。
如果保存，就需要进行频繁的内存申请和销毁，尤其是当键或值是语言内置的基础类型（比如char、int、long、short、float、double）时，存放值的内存大小比存放指针值的内存还小。会导致更多的小块内存的操作和内存碎片。
项目的需求：
- 在我的项目中，很多情况下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;
内存结构：
按照上述设计方案，假设我们创建一个size（桶数）为6的HashTable，并且尝试插入4个元素，其中第一个元素和第四个元素hash冲突，第二个元素与第三个元素hash冲突。
那么按照设计，该HashTable在内存中的结构如下图所示：
在按键查找时，先通过计算hash值，并计算hash值对应的桶的索引[0,6)，然后按照蓝色箭头pNext（指针）的指向即可找到对应的元素（或者找不到）。在按照插入顺序遍历时，从head指针开始，按照墨色箭头pListNext（指针） 的指向即可完成元素的遍历。
接口需求：
用户需要在创建HashTable的实例时指定key和value的类型，在进行增、删、改、查以及遍历操作时直接使用对应的类型即可。
如：
/*创建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 的库文件.