hsearch에서 요소를 삭제하는 방법

Question

GNU C 라이브러리에서 제공하는 hsearch_r 함수를 사용하고 있습니다.

나는 hsearch_r을 사용하여 해시 테이블에 요소를 추가하고 ENTER로 동작을 전달할 수 있지만 해시 테이블에서 요소 나 항목을 제거 할 수있는 방법이 없다는 것을 알았습니다.

아무도 이유가 무엇인지 알고 있습니까?

내 삭제 기능을 구현하려면 다음을 수행 할 수 있습니까?

먼저 FIND와 같은 작업으로 hsearch_r을 사용하여 검색합니다. 그런 다음 hash_element에 대한 포인터를 얻은 다음 해방하십시오. 그게 효과가 있니? 요소를 추가하고 검색 만 할 수 있다면 해시 라이브러리는 좋은 것입니다. 왜 삭제 루틴이 제공되지 않습니까?

나는 hsearch 라이브러리의 소스 코드에 대한 인터넷 검색을 시도하고 그것을 찾을 수 없습니다. 누군가 나에게도 가르쳐 줄 수 있습니까?

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

편집 :

나는 또한 내가 다음 액션 ADD와 두 번 hsearch_r를 호출하는 경우이 오류도를 throw 않으며이 새 값으로 해시를 업데이트 않는 것을 알 수있다. 이것은 이상합니다. 이것은 내부적으로 hsearch가 대체 기능을 구현하지 않고 직접 검색을 수행해야한다는 것을 의미합니다. 즉, 먼저 검색을 수행 한 다음 검색이 존재하면 첫 번째 항목을 삭제 한 다음 새 항목을 추가하십시오. 그러나 이렇게하려면 우리가 해쉬로부터 엘리먼트를 삭제해야 할 필요가있다.

Answer 1

source of hsearch_r은 온라인으로 찾을 수 있습니다.

키가 테이블에 있으면 작업을 확인하기 전에 발견 된 항목과 함께 함수가 반환되므로 기존 키를 추가하면 찾은 것처럼 작동합니다. (찾은 구조체의 값을 hsearch(ADD)으로 호출 한 후 덮어 쓸 수 있고 이전 값을 덮어 쓸 수 있습니다.)

구현은 요소 삭제에 적합하지 않습니다. 버킷 배열을 유지 관리합니다. 해시 충돌은 다른 빈 버킷을 찾아 처리하므로 버킷 인덱스가 해시 코드와 반드시 같지는 않습니다. 동일한 해시 코드로 두 개의 값을 삽입하면 두 번째 값은 해시 코드가 버킷 인덱스가 아닌 곳에 버킷을 가져옵니다.

이제 첫 번째 항목을 삭제 한 다음 두 번째 항목을 찾으려고하면 "다른"버킷은 해시 코드가 버킷 색인 인 "최적"버킷이 가득 찬 경우에만 고려되므로 찾을 수 없습니다. .

업데이트되지 않은 다시 추가 및 누락 된 삭제 옵션 외에도 hsearch_r에 대한 다른 제한 사항이 있습니다. 예를 들어, 항목의 최대 누벨은 사전에 추정되어야하며 나중에 변경할 수 없습니다. 나는 hsearch_r이 제한된 범위의 응용 프로그램을위한 빠른 해시 테이블로 의도되었다고 생각합니다. 좀 더 일반적인 해시 테이블 구현으로 더 나아질 수 있습니다.

또는 "없음"을 의미하는 기본 데이터 매개 변수를 사용할 수 있습니다. entry->data 유형은 void *입니다. 따라서 NULL은 확실한 선택입니다.

#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; 
} 

참고 : 다음과 같은 데이터는 hsearch_r보다 더 자연스러운 구문이 래퍼 함수와 맨 페이지의 예 수정 당신이 데이터로 ponters를 사용하여 해시 테이블은 데이터를 소유하고 있다면, 당신은을 free합니다 파괴에 대한 데이터뿐만 아니라 기존 값을 덮어 쓸 때도 마찬가지입니다.