如何从hsearch中删除元素

Question

我使用的是由GNU C库提供的hsearch_r函数。

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

有人知道这是为什么吗？

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

我首先使用hsearch_r进行搜索，查找操作如下。然后，我得到一个指向hash_element的指针，然后我释放它。这会工作吗？如果我只能添加元素并搜索它们，那么散列库有什么好处。为什么不提供删除例程？

我试着搜索hsearch的源代码并找不到它。有人可以指出我吗？

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

编辑：

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

Answer 1

source of hsearch_r可以在网上找到。

如果该键是表，函数与检查行动，这意味着将现有的关键行为就像发现它之前找到的条目返回。 （您可以在调用hsearch(ADD)之后覆盖“found”结构的值并覆盖旧值。）

该实现不适合元素删除。它维护一个桶阵列。散列冲突是通过查找另一个空桶来处理的，因此存储区索引不一定等于散列码。当你使用相同的散列码插入两个值时，第二个将得到这样一个散列码不是存储桶索引的存储桶。

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

除了非更新重新增加和缺失的删除选项，还有其他限制hsearch_r。例如，必须预先估计条目的最大值，并且以后不能更改。我认为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的有关销毁的数据，还有当您覆盖现有值时。