内容简介:上一章中,我们使用了我们的
上一章中,我们使用了 双重Hash
的技术来处理 碰撞
,并用了 C语言
实现,贲张我们将实现 Hash表
中的 插入
、 搜索
和 删除
接口。
实现接口
我们的 hash函数
将会实现如下的接口:
// hash_table.h void ht_insert(ht_hash_table* ht, const char* key, const char* value); char* ht_search(ht_hash_table* ht, const char* key); void ht_delete(ht_hash_table* ht, const char* key);
Insert函数
在 hash表
中插入一条记录时,我们需要遍历整个 hash表
知道找到一个空的位置,然后执行插入并将 hash表
的大小加 1
。 hash表
中的 count
属性代表 hash表
的大小,在下一章 缩放hash表大小
中很有用:
void ht_insert(ht_hash_table* ht, const char* key, const char* value) { ht_item* item = ht_new_item(key, value); int index = ht_get_hash(item->key, ht->size, 0); ht_item* cur_item = ht->items[index]; int i = 1; while(cur_item != NULL) { index = ht_get_hash(item->key, ht->size, i); cur_item = ht->items[index]; ++i; } ht->items[index] = item; ht->count++; }
Search函数
search
和 insert
有点相似,但是在 while
循环中,我们会检查记录的 key
是否与我们正在搜索的 key
匹配。如果匹配,就会返回这条记录的 value
,没有匹配到就会返回 NULL
:
char* ht_search(ht_hash_table* ht, const char* key) { int index = ht_get_hash(key, ht->size, 0); ht_item* item = ht->items[index]; int i = 1; while (item != NULL) { if (strcmp(item->key, key) == 0) { return item->value; } index = ht_get_hash(key, ht->size, i); item = ht->items[index]; i++; } return NULL; }
delete函数
从开放的地址 hash表
中删除比插入或搜索更复杂,因为存在 碰撞
,我们希望删除的记录可能是碰撞链的一部分。从表中删除它会破坏该链,并且无法在链的尾部找到记录。要解决此问题,我们只需将其标记为已删除,而不是真的删除该记录。
我们将记录替换为指向全局哨兵的指针,再将其标记为已删除,该全局哨兵表示包含已删除的记录的 bucket
:
// hash_table.c static ht_item HT_DELETED_ITEM = {NULL, NULL}; void ht_delete(ht_hash_table* ht, const char* key) { int index = ht_get_hash(key, ht->size, 0); ht_item* item = ht->items[index]; int i = 1; while (item != NULL) { if (item != &HT_DELETED_ITEM) { if (strcmp(item->key, key) == 0) { ht_del_item(item); ht->items[index] = &HT_DELETED_ITEM; } } index = ht_get_hash(key, ht->size, i); item = ht->items[index]; i++; } ht->count--; }
删除后,我们需要将 hash表
的 count
属性减 1
。
我们也需要修改下 ht_insert
和 ht_search
函数,当搜索时,我们需要忽略并跳过已删除的项,在已删除项的位置我们可以插入新的记录:
// hash_table.c void ht_insert(ht_hash_table* ht, const char* key, const char* value) { // ... while (cur_item != NULL && cur_item != &HT_DELETED_ITEM) { // ... } // ... } char* ht_search(ht_hash_table* ht, const char* key) { // ... while (item != NULL) { if (item != &HT_DELETED_ITEM) { if (strcmp(item->key, key) == 0) { return item->value; } } // ... } // ... }
修改一下
我们的 hash表
现在还不支持更新 key
的值,如果我们插入两条相同 key
的记录, key
将会冲突,第二条记录就会插入到下一个可用的位置,当使用 key
搜索时,我们会找到第一条记录,第二条记录就永远不会被找到,现在我们修改下 ht_insert
函数,在插入多条相同 key
的记录时,会删除之前的记录再插入新的记录:
// hash_table.c void ht_insert(ht_hash_table* ht, const char* key, const char* value) { // ... while (cur_item != NULL) { if (cur_item != &HT_DELETED_ITEM) { if (strcmp(cur_item->key, key) == 0) { ht_del_item(cur_item); ht->items[index] = item; return; } } // ... } // ... }
上一章:处理碰撞
下一章:缩放Hash表大小
以上所述就是小编给大家介绍的《[译]C语言实现一个简易的Hash table(5)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- GO语言学习笔记(五)GO语言函数的简易计算
- C语言实现一个简易的Hash table(6)
- C语言实现一个简易的Hash table(7)
- 木兰语言 0.0.17.2 实现简易网页浏览器,又一次碰到语法歧义
- 简易RPC框架实现
- Gin 简易实践
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。