如何从hsearch中删除元素

I am using hsearch_r function provided by GNU C library.

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

I see that while i can add elements into the HASH table using hsearch_r and passing the action as ENTER, i see no way to remove an element or an entry from the HASH table.

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

Does anybody know a reason why this is so?

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

Can i do the following to implement my delete function.

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

I first search for it using hsearch_r with the action as FIND. Then once i get a pointer to the hash_element then i free it. Will that work? What good is a hash library if i can only add elements and search for them. Why isnt a delete routine provided?

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

I tried googling for the source code of hsearch library and couldnt find it. Can somebody also point me to that?

我在谷歌上搜索了hsearch库的源代码，但是没有找到。有人能给我指出来吗?

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

EDIT:

编辑:

I also see that if i call the hsearch_r twice with action ADD then it throws neither an error nor does it update the hash with the new value. This is odd. This means that internally hsearch does NOT implement a replace functionality and we will have to do it ourselves i.e. first do a search and then if it exists, then delete the first entry and then add a new one. However to do this we would need to DELETE an element from the hash, which i am unable to.

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

1 个解决方案

#1

The source of hsearch_r can be found online.

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

If the key is in the table, the function returns with the found entry before checking the action, which means that adding an existing key behaves like finding it. (You could overwrite the value of the "found" struct after the call to hsearch(ADD) and overwrite old values.)

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

The implementation isn't suited to element deletion. It maintains an array of buckets. Hash collision is handled by finding another empty bucket, so that the bucket index does not necessarily equal the hash code. When you insert two values with the same hash code, the second will get such a bucket where the hash code is not the bucket index.

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

When you now delete the first item and then try to find the second, it will not be found, because the "other" buckets are only considered when the "optimum" bucket where the hash code is the bucket index is full.

当您现在删除第一个项，然后尝试查找第二个项时，它将不会被找到，因为“其他”项只在哈希代码为bucket索引满时才被考虑。

Besides the non-updating re-additions and the missing deletion option, there are other restrictions to hsearch_r. For example, the maximum nuber of entries must be estimated beforehand and cannot be changed later. I think hsearch_r is intended as a fast hash table for a limited range of applications. You might be better off with another, more general hash table implementation.

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

Alternatively, you could use a default data parameter that means "not present". The type of entry->data is void *, so NULL is an obvious choice. The following data is a modification of the man pages's example with wrapper functions that have a more natural syntax than hsearch_r:

或者，您可以使用一个默认的数据参数，表示“不存在”。输入的类型->数据是void *，所以NULL是一个明显的选择。以下数据是对man页面示例的修改，该示例使用比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;
}

Note: If you use ponters as data and the hash table owns that data, you must free the data on destruction, but also when you overwrite existing values.

注意:如果您使用ponter作为数据，而hash表拥有该数据，则必须在销毁时释放数据，但在重写现有值时也要释放数据。

#1