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

上一章中，我们使用了双重Hash的技术来处理碰撞，并用了C语言实现，贲张我们将实现Hash表中的插入、搜索和删除接口。实现接口我们的hash函数将会实现如下的接口：// hash_table.hvoid 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.cstatic 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.cvoid 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.cvoid 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表大小