如何从 hsearch 中删除元素

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

我发现虽然我可以使用 hsearch_r 将元素添加到哈希表中并将操作作为 ENTER 传递，但我看不出有什么方法可以从哈希表中删除元素或条目。

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

我可以执行以下操作来实现我的删除功能吗？

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

我尝试用谷歌搜索搜索库的源代码，但找不到它。有人也可以指点我吗？

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

EDIT:

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

The 来源hsearch_r可以在网上找到。

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

该实现不适合元素删除。它维护一个存储桶数组。哈希冲突是通过寻找另一个空桶来处理的，因此桶索引不一定等于哈希码。当您插入两个具有相同哈希码的值时，第二个值将得到这样一个桶，其中哈希码不是桶索引。

现在，当您删除第一项，然后尝试查找第二项时，将找不到它，因为只有当哈希码为存储桶索引的“最佳”存储桶已满时，才会考虑“其他”存储桶。

除了不可更新的重新添加和缺失的删除选项外，还有其他限制hsearch_r。例如，必须事先估计最大条目数，并且以后不能更改。我认为hsearch_r旨在作为有限范围应用程序的快速哈希表。您可能会更好地使用另一个更通用的哈希表实现。

或者，您可以使用默认数据参数，表示“不存在”。的类型entry->data is void *, so 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数据会被破坏，而且当您覆盖现有值时也会如此。