slot_nr是数组的大小，在散列函数不变的情况下，slot_nr的大小对散列表的性能起决定作用。slot_nr的值越大性能越高，但空间浪费也越大，这又是一个时/空互换的例子。所以这个值也由调用者确定会好一点。很多书都认为这个值应该选择一个素数，我认为这种做法没有什么科学的理论根据，至少没有找到严密的数学证明。
创建散列表（hash_table_create）
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;
}
创建散列表时，我们只是创建了数组，而链表则在第一次使用时再创建。这种延迟处理的手法在加快启动速度时是很常见的，这种做法也会减少一些不必要的开销（因为有些对象可能根本就不会用到）。
插入散列表（hash_table_insert）
Ret hash_table_insert(HashTable* thiz, void* data)
{
size_t index = 0;
return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS);
/*先通过hash值定位到链表。*/
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);
}
先计算元素所在链表，如果链表还没有创建，我们就创建它，然后把元素插入到链表中。怎样？也不过是几行代码而已。
删除散列表（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);
/*先通过hash值定位到链表。*/
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;
}
先计算元素所在的链表，然后从链表中删除元素。
查找散列表的元素（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);
/*先通过hash值定位到链表。*/
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;
}
先计算元素所在的链表，然后从链表中查找元素。
计算元素个数（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;
}
这个麻烦一点，需要累加所有链表中元素个数。
遍历所有元素（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。
销毁散列表（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;
}
销毁所有链表，释放数组和散列表本身。
散列表有以下两种特殊情况。
(1) 散列函数极差：所有元素计算出同一个散列值。则散列表退化成一个链表，查找的时间效率为O(n)。
(2) 散列函数极好：所有元素计算出不同的散列值，而且元素个数为slot_nr。则散列表等同于一个数组，通过索引定位元素，查找的时间效率为O(1)。
