static int hash_str(char *key)
{
int hash = 0;
char *cur = key;
while(*(cur++) != '\0') {
hash += *cur;
}
return hash;
}
// 使用这个宏来求得key在哈希表中的索引
#define HASH_INDEX(ht, key) (hash_str((key)) % (ht)->size)
这个哈希算法比较简单，它的效果并不好，在实际场景下不会使用这种哈希算法， 例如PHP中使用的是称为DJBX33A算法， 这里列举了Mysql，OpenSSL等开源软件使用的哈希算法， 有兴趣的读者可以前往参考。
操作接口的实现
为了操作哈希表，实现了如下几个操作函数：
复制代码 代码如下:
int hash_init(HashTable *ht); // 初始化哈希表
int hash_lookup(HashTable *ht, char *key, void **result); // 根据key查找内容
int hash_insert(HashTable *ht, char *key, void *value); // 将内容插入到哈希表中
int hash_remove(HashTable *ht, char *key); // 删除key所指向的内容
int hash_destroy(HashTable *ht);
下面以插入和获取操作函数为例：
复制代码 代码如下:
int hash_insert(HashTable *ht, char *key, void *value)
{
// check if we need to resize the hashtable
resize_hash_table_if_needed(ht); // 哈希表不固定大小，当插入的内容快占满哈表的存储空间
// 将对哈希表进行扩容， 以便容纳所有的元素
int index = HASH_INDEX(ht, key); // 找到key所映射到的索引
Bucket *org_bucket = ht->buckets[index];
Bucket *bucket = (Bucket *)malloc(sizeof(Bucket)); // 为新元素申请空间
bucket->key = strdup(key);
// 将值内容保存进来， 这里只是简单的将指针指向要存储的内容，而没有将内容复制。
bucket->value = value;
LOG_MSG("Insert data p: %p\n", value);
ht->elem_num += 1; // 记录一下现在哈希表中的元素个数
if(org_bucket != NULL) { // 发生了碰撞，将新元素放置在链表的头部
LOG_MSG("Index collision found with org hashtable: %p\n", org_bucket);
bucket->next = org_bucket;
}
ht->buckets[index]= bucket;
LOG_MSG("Element inserted at index %i, now we have: %i elements\n",
index, ht->elem_num);
return SUCCESS;
}
上面这个哈希表的插入操作比较简单，简单的以key做哈希，找到元素应该存储的位置，并检查该位置是否已经有了内容， 如果发生碰撞则将新元素链接到原有元素链表头部。在查找时也按照同样的策略，找到元素所在的位置，如果存在元素， 则将该链表的所有元素的key和要查找的key依次对比， 直到找到一致的元素，否则说明该值没有匹配的内容。
复制代码 代码如下:
int hash_lookup(HashTable *ht, char *key, void **result)
{
int index = HASH_INDEX(ht, key);
Bucket *bucket = ht->buckets[index];
if(bucket == NULL) return FAILED;
// 查找这个链表以便找到正确的元素，通常这个链表应该是只有一个元素的，也就不用多次
// 循环。要保证这一点需要有一个合适的哈希算法，见前面相关哈希函数的链接。
while(bucket)
{
if(strcmp(bucket->key, key) == 0)
{
LOG_MSG("HashTable found key in index: %i with key: %s value: %p\n",
index, key, bucket->value);
*result = bucket->value;
return SUCCESS;
}
bucket = bucket->next;
}
LOG_MSG("HashTable lookup missed the key: %s\n", key);
return FAILED;
}
PHP中数组是基于哈希表实现的，依次给数组添加元素时，元素之间是有先后顺序的，而这里的哈希表在物理位置上显然是接近平均分布的， 这样是无法根据插入的先后顺序获取到这些元素的，在PHP的实现中Bucket结构体还维护了另一个指针字段来维护元素之间的关系。 具体内容在后一小节PHP中的HashTable中进行详细说明。上面的例子就是PHP中实现的一个精简版。
您可能感兴趣的文章: