如何从hsearch中删除元素

Question

我正在使用GNU C库提供的hsearch_r函数.

我看到虽然我可以使用hsearch_r将元素添加到HASH表中并将操作作为ENTER传递,但是我看不到从HASH表中删除元素或条目的方法.

有人知道为什么会这样吗？

我可以执行以下操作来实现删除功能.

我首先使用hsearch_r搜索它,操作为FIND.然后,一旦我得到一个指向hash_element的指针,然后我释放它.那会有用吗？如果我只能添加元素并搜索它们,那么哈希库有什么用处.为什么不提供删除例程？

我试着谷歌搜索hsearch库的源代码,无法找到它.有人也可以指出我吗？

http://linux.die.net/man/3/hcreate_r

编辑:

我也看到,如果我用动作ADD调用hsearch_r两次,那么它既不会抛出错误,也不会使用新值更新散列.这很奇怪.这意味着内部hsearch不实现替换功能,我们必须自己完成,即首先进行搜索,然后如果存在,则删除第一个条目,然后添加一个新条目.但是要做到这一点,我们需要从哈希中删除一个元素,我无法做到.

Answer 1

该源hsearch_r可以在网上找到.

如果键在表中,则函数在检查操作之前返回找到的条目,这意味着添加现有键的行为就像找到它一样.(您可以在调用hsearch(ADD)并覆盖旧值后覆盖"found"结构的值.)

该实现不适合删除元素.它维护着一系列桶.通过查找另一个空桶来处理散列冲突,以便桶索引不一定等于散列码.当您使用相同的哈希码插入两个值时,第二个将获得这样一个桶,其中哈希码不是桶索引.

当您现在删除第一个项目然后尝试查找第二个项目时,将无法找到它,因为只有当哈希码为存储区索引的"最佳"存储区已满时才会考虑"其他"存储区.

除了不更新的重新添加和丢失的删除选项,还有其他限制hsearch_r.例如,必须事先估计条目的最大nuber,并且以后不能更改.我认为它hsearch_r是一个有限范围的应用程序的快速哈希表.使用另一个更通用的哈希表实现可能会更好.

或者,您可以使用默认数据参数,表示"不存在".类型entry->data是void *,所以NULL是一个明显的选择.以下数据是使用包装函数修改手册页的示例,该函数具有比hsearch_r以下更自然的语法:

#include <stdio.h>
#include <stdlib.h>

#define _GNU_SOURCE
#define __USE_GNU
#include <search.h>

#define NIL (-1L)

void hadd(struct hsearch_data *tab, char *key, long value)
{
    ENTRY item = {key, (void *) value};
    ENTRY *pitem = &item;

    if (hsearch_r(item, ENTER, &pitem, tab)) {
        pitem->data = (void *) value;
    }
}

void hdelete(struct hsearch_data *tab, char *key)
{
    ENTRY item = {key};
    ENTRY *pitem = &item;

    if (hsearch_r(item, FIND, &pitem, tab)) {
        pitem->data = (void *) NIL;
    }
}

long hfind(struct hsearch_data *tab, char *key)
{
    ENTRY item = {key};
    ENTRY *pitem = &item;

    if (hsearch_r(item, FIND, &pitem, tab)) {
        return (long) pitem->data;
    }
    return NIL;
}

int main()
{
    char *data[] = { 
        "apple", "pear", "cherry", "kiwi", 
        "orange", "plum", "pomegranate", NULL
    };
    char **p = data;

    struct hsearch_data tab = {0};
    int i;

    hcreate_r(10, &tab);
    for (i = 0; i < 5; i++) hadd(&tab, data[i], i + 1L);

    hdelete(&tab, "pear");
    hadd(&tab, "cherry", 144);

    while (*p) {
        long value = hfind(&tab, *p);

        if (value == NIL) {
            printf("%s: NIL\n", *p);
        } else {
            printf("%s: %ld\n", *p, value);
        }
        p++;
    }

    hdestroy_r(&tab);

    return 0;
}

注意:如果使用ponters作为数据并且哈希表拥有该数据,则必须free在销毁数据时,以及覆盖现有值时.