如何從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的有關銷燬的數據，還有當您覆蓋現有值時。