哈希表
前面我们已经体会到了组合的威力，用短短几十行代码就搞定了队列和栈。现在轮到哈希表了，在此之前已经有几位读者向我抱怨，哈希表太难写了！其实哈
希表也很简单，前面我们说了队列和栈只不过是链表或者数组的特殊情况而已，哈希表当然不再是链表或者数组的特殊情况了，但是我们同样可以用组合的方式来实
现它。简单点说：
哈希表 = 数组 + 链表
有读者说，老兄，你在玩我吧。不，我是认真的。我说的“加”当然不是简单的叠加起来，组合也是需要技巧的，不同的组合得到的效果不一样，如何去组合也是需要花时间去学习的。
哈希表的基本接口有：
o 创建hash_table_create
o 插入hash_table_insert
o 删除hash_table_delete
o 查找hash_table_find
o 计算元素个数hash_table_length
o 遍历所有元素hash_table_foreach
o 销毁hash_table_destroy
现在看看怎样用数组和链表组合出哈希表：
o 哈希表的数据结构
struct _HashTable
{
DataHashFunc hash;
DList** slots;
size_t slot_nr;
DataDestroyFunc data_destroy;
void* data_destroy_ctx;
};
hash是一个函数指针，用来计算数据的哈希值。哈希函数的好坏基本上决定了哈希表的效率，好的哈希函数计算出的哈希值分布比较均匀。遗憾的是哈希
表的设计者们谁都不知道什么样的哈希函数是最好的，因为哈希函数的好坏只能动态评估，它与数据类型和应用环境密切相关。按照惯例，实现者不知道的事就应该
让调用者去实现，所以把哈希函数设计成回调函数，由调用者提供。
slots是哈希表的主体，它是一个双向链表的指针数组。所以说哈希表 = 数组 + 链表是有道理的。由于这个数组不需要动态增长，所以用最简单的指针数组就好了。
slot_nr是数组的大小，在哈希函数不变的情况下，slot_nr的大小对哈希表的性能起决定作用。slot_nr的值越大性能越高，但空间浪
费也越大，这又是一个时/空互换的例子。所以这个值也由调用者确定会好一点。很多书都认为这个值应该选择一个素数，我认为这没有什么理论根据，至少没有找
到严密的数学证明。
o 创建
HashTable* hash_table_create(DataDestroyFunc data_destroy, void* ctx, DataHashFunc hash, int slot_nr
)
{
HashTable* thiz = NULL;
return_val_if_fail(hash != NULL && slot_nr > 1, NULL);
thiz = (HashTable*)malloc(sizeof(HashTable));
if(thiz != NULL)
{
thiz->hash = hash;
thiz->slot_nr = slot_nr;
thiz->data_destroy_ctx = ctx;
thiz->data_destroy = data_destroy;
if((thiz->slots = (DList**)calloc(sizeof(DList*)*slot_nr, 1)) == NULL)
{
free(thiz);
thiz = NULL;
}
}
return thiz;
}
创建哈希表时，我们只是创建了数组，而链表则在第一次使用时再创建。这种延迟处理的手法在加快起动速度时是很常见的，这种做法也会减少一些不必要的开销(有些对象可能根本就不会用到)。
o 插入hash_table_insert
Ret hash_table_insert(HashTable* thiz, void* data)
{
size_t index = 0;
return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS);
index = thiz->hash(data)%thiz->slot_nr;
if(thiz->slots[index] == NULL)
{
thiz->slots[index] = dlist_create(thiz->data_destroy, thiz->data_destroy_ctx);
}
return dlist_prepend(thiz->slots[index], data);
}
先计算元素所在链表，如果链表还没有创建就创建它，然后把元素插入到链表中。怎样？只是几行代码而已。
o 删除hash_table_delete
Ret hash_table_delete(HashTable* thiz, DataCompareFunc cmp, void* data)
{
int index = 0;
DList* dlist = NULL;
return_val_if_fail(thiz != NULL && cmp != NULL, RET_INVALID_PARAMS);
index = thiz->hash(data)%thiz->slot_nr;
dlist = thiz->slots[index];
if(dlist != NULL)
{
index = dlist_find(dlist, cmp, data);
return dlist_delete(dlist, index);
}
return RET_FAIL;
}
先计算元素所在的链表，然后从链表中删除元素。
o 查找hash_table_find
Ret hash_table_find(HashTable* thiz, DataCompareFunc cmp, void* data, void** ret_data)
{
int index = 0;
DList* dlist = NULL;
return_val_if_fail(thiz != NULL && cmp != NULL && ret_data != NULL, RET_INVALID_PARAMS);
index = thiz->hash(data)%thiz->slot_nr;
dlist = thiz->slots[index];
if(dlist != NULL)
{
index = dlist_find(dlist, cmp, data);
return dlist_get_by_index(dlist, index, ret_data);
}
return RET_FAIL;
}
先计算元素所在的链表，然后从链表中查找元素。
o 计算元素个数hash_table_length
size_t hash_table_length(HashTable* thiz)
{
size_t i = 0;
size_t nr = 0;
return_val_if_fail(thiz != NULL, 0);
for(i = 0; i < thiz->slot_nr; i++)
{
if(thiz->slots[i] != NULL)
{
nr += dlist_length(thiz->slots[i]);
}
}
return nr;
}
这个麻烦一点，需要累加所有链表中元素个数。
o 遍历所有元素hash_table_foreach
Ret hash_table_foreach(HashTable* thiz, DataVisitFunc visit, void* ctx)
{
size_t i = 0;
return_val_if_fail(thiz != NULL && visit != NULL, RET_INVALID_PARAMS);
for(i = 0; i < thiz->slot_nr; i++)
{
if(thiz->slots[i] != NULL)
{
dlist_foreach(thiz->slots[i], visit, ctx);
}
}
return RET_OK;
}
依次调用每个链表的dlist_foreach。
o 销毁hash_table_destroy
void hash_table_destroy(HashTable* thiz)
{
size_t i = 0;
if(thiz != NULL)
{
for(i = 0; i < thiz->slot_nr; i++)
{
if(thiz->slots[i] != NULL)
{
dlist_destroy(thiz->slots[i]);
thiz->slots[i] = NULL;
}
}
free(thiz->slots);
free(thiz);
}
return;
}
销毁所有链表，释放数组和哈希表本身。
哈希表的两种特殊情况：
o 哈希函数极差：所有元素计算出同一个哈希值。则哈希表退化成一个链表，查找的时间效率为O(n)。
o 哈希函数极好：所有元素计算出不同的哈希值，而且元素个数为slot_nr。则哈希表等同于一个数组，通过索引定位元素，查找的时间效率为O(1)。
所以哈希表的查找效率在O(1)到O(n)之间，大部分人选择哈希表时，并没有仔细评估哈希函数的好坏，而又期望得到很高的查找效率，其实这只是一种幻觉。如果查找效率要求比较高，通常我会选择有序数组，用二分查找来做，至少它的查找效率是比较确定的。
本节示例代码请到这里下载。