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

栏目: C · 发布时间: 5年前

内容简介:上一章中,我们使用了我们的

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

上一章中,我们使用了 双重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表 的大小加 1hash表 中的 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函数

searchinsert 有点相似,但是在 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_insertht_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)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Perl语言入门 第六版(中文版)

Perl语言入门 第六版(中文版)

Randal L.Schwartz、brian d foy、Tom Phoenix / 盛春 / 东南大学出版社 / 2012-3 / 62.00元

《Perl语言入门(第6版)(中文版)》根据作者施瓦茨、福瓦、菲尼克斯从1991年开始的教学经验积累汇聚而成,多年来十分畅销。此次第六版涵盖了最新的Perl5.14版本的变化。《Perl语言入门(第6版)(中文版)》每章都包含若干习题,帮助你巩固消化刚学到的知识。也许其他书籍只是想着灌输Perl编程的条条框框,但《Perl语言入门(第6版)(中文版)》不同,我们希望把你培养成一名真正的Perl程序......一起来看看 《Perl语言入门 第六版(中文版)》 这本书的介绍吧!

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

URL 编码/解码
URL 编码/解码

URL 编码/解码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换