如何从hsearch中删除元素 [英] How to delete element from hsearch
问题描述
我看到虽然我可以使用hsearch_r将元素添加到HASH表中，并将操作作为ENTER传递，
有人知道为什么会这样吗？
我可以执行以下操作来实现我的删除功能：
我首先使用hsearch_r搜索它，操作为FIND。然后，我得到一个指向hash_element的指针，然后我释放它。这会工作吗？如果我只能添加元素并搜索它们，那么散列库有什么好处。为什么不提供删除例程？
我试着搜索hsearch的源代码并找不到它。有人可以指点我吗？
http://linux.die.net/man/3/hcreate_r
编辑：
我也看到，如果我用动作ADD调用hsearch_r两次，那么它不会抛出错误，也不会用新值更新散列。这很奇怪。这意味着内部hsearch不会执行替换功能，我们必须自己做，即首先执行搜索，然后如果存在，然后删除第一个条目，然后添加一个新条目。但是为了做到这一点，我们需要从哈希中删除一个元素，这是我无法做到的。 hsearch_r 的来源=http://fossies.org/dox/glibc-2.20/hsearch__r_8c_source.html =noreferrer> 。
如果键在表中，那么在检查动作之前，该函数会返回找到的条目，这意味着添加现有的键就像查找它。 （你可以在调用 hsearch（ADD）之后覆盖found结构的值，并覆盖旧值。）
该实现不适合元素删除。它维护一个桶阵列。散列冲突是通过查找另一个空桶来处理的，因此存储区索引不一定等于散列码。当您使用相同的哈希码插入两个值时，第二个会得到这样一个哈希码不是存储区索引的存储桶。
当您现在删除第一个项目然后尝试找到第二个，它将不会被找到，因为只有在散列码为存储区索引的最佳存储区已满时才会考虑其他存储桶。
除了非更新重新添加和缺失删除选项之外，还有其他限制< 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; （hsearch_r（item，ENTER，& pitem，tab））{
pitem-> data =（void *）value;
if
$ b void hdelete（struct hsearch_data * tab，char * key）
{
ENTRY item = {key};
ENTRY * pitem =& item; （hsearch_r（item，FIND，& pitem，tab））{
pitem-> data =（void *）NIL;
if
$ b $ long hfind（struct hsearch_data * tab，char * key）
{
ENTRY item = {key};
ENTRY * pitem =& item; （hsearch_r（item，FIND，& pitem，tab））{
return（long）pitem-> data;
if
}
返回NIL;
}
int main（）
{
char * data [] = {
apple，pear，cherry，猕猴桃，
橙，李，石榴，NULL
};
char ** p = data;
struct hsearch_data tab = {0};
int i;
hcreate_r（10，& tab）; （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 \\\
，* p）;
} else {
printf（％s：％ld\\\
，* p，value）;
}
p ++;
}
hdestroy_r（& tab）;
返回0;
注意：如果您使用ponters作为数据并且哈希表拥有该数据，您必须 free 销毁数据，而且覆盖现有值。
I am using hsearch_r function provided by GNU C library.
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.
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?
I tried googling for the source code of hsearch library and couldnt find it. Can somebody also point me to that?
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.
解决方案 The source of hsearch_r can be found online.
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.)
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.
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.
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.
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:
#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.
这篇关于如何从hsearch中删除元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
