[译]C语言实现一个简易的Hash table(5)

45次阅读

共计 2376 个字符,预计需要花费 6 分钟才能阅读完成。

上一章中,我们使用了双重 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 表大小

正文完
 0