C언어 해시 테이블에서 자료 검색 함수 hsearch()

2020. 3. 14. 06:30 컴퓨터/프로그래밍

C함수 해시 테이블 생성 hcreate()

해시 테이블(hash table)에서 자료를 검색합니다. 검색해서 찾으면 데이터 요소 포인터를 반환하며, 찾지 못하면 두번째 인수에 따라 해시 테이블에 자료를 추가할 수 있습니다.

  • 헤더: search.h
  • 형태: ENTRY *hsearch(ENTRY item, ACTION action)
  • 인수: ENTRY item 검색을 위한 ENTRY
    ACTION action 검색 결과에 따라 어떻게 처리할 지를 지정
  • 반환: ENTRY * 해시 테이블의 데이터 요소 포인터

해시 테이블에서는 자료를 검색하거나 추가하기 위해서 ENTRY 구조체를 이용합니다.

typedef struct entry
  {
    char *key;
    void *data;
  }
ENTRY;

ENTRY의 data는 추가되는 데이터 부분이고 key부분이 분류와 검색에 사용됩니다.

item.key    = "2nd";
item.data   = "www.falinux.com";
hsearch( item, ENTER);

hserarch()에서 item을 이용하여 검색하게 되면 item.key 값으로 "2nd"값을 검색하게 됩니다.

2번째 인수, ACTION에는 FIND와 ENTER 가 있습니다.

typedef enum
  {
    FIND,
    ENTER
  }
ACTION;

FIND는 검색만 수행합니다. 검색에 성공했다면 찾은 데이터 요소의 포인터를 반환합니다. 검색에 실패하면 NULL을 반환합니다.

ENTER은 검색 후에 key에 대한 자료를 찾았다면 요소의 포인터를 반환하고 없다면 테이블에 자료를 추가합니다.

해시 테이블(hash table)이란.

단순한 구조의 데이터 테이블에서는 자료를 입력할 때에는 추가 순서에 따라서 데이터를 추가했다가 필요에 따라 정렬을 다시 하거나 모든 데이터를 비교하는 식으로 검색하게 됩니다.

그러나 해시 테이블은 자료를 테이블에 입력할 때부터 특정 조건에 따라 분류하여 추가하게 함으로써 이후 검색할 때 모든 데이터를 조회할 필요 없이 분류된 자료만 검색하면 되므로 검색이 빠릅니다.

아래는 해시 테이블 관리에 설명된 내용을 간략히 정리하여 올립니다.

예제

#include <stdio.h>
#include <search.h>

int main( void)
{
   ENTRY    item;
   ENTRY    *result;

   hcreate( 2);

   item.key    = "1st";
   item.data   = "jwmx.tistory.com";
   hsearch( item, ENTER);


   item.key    = "2nd";
   item.data   = "badayak.com";
   hsearch( item, ENTER);

   item.key    = "3rd";
   item.data   = "jwmx badayak";
   hsearch( item, ENTER);


   item.key    = "4th";
   item.data   = "Embedded Linux Programming";
   hsearch( item, ENTER);

   item.key    = "5th";
   item.data   = "GCC Compiler";
   hsearch( item, ENTER);

   // 여기서부터는 자료 찾기

   item.key    = "1st";
   if ( NULL != (result = hsearch( item, FIND)) )
      printf( "%s key data is %s\n", result->key, (char *)result->data);

   item.key    = "2nd";
   if ( NULL != (result = hsearch( item, FIND)) )
      printf( "%s key data is %s\n", result->key, (char *)result->data);

   item.key    = "3rd";
   if ( NULL != (result = hsearch( item, FIND)) )
      printf( "%s key data is %s\n", result->key, (char *)result->data);

   item.key    = "4th";
   if ( NULL != (result = hsearch( item, FIND)) )
      printf( "%s key data is %s\n", result->key, (char *)result->data);

   item.key    = "5th";
   if ( NULL != (result = hsearch( item, FIND)) )
      printf( "%s key data is %s\n", result->key, (char *)result->data);

   item.key    = "6th";
   if ( NULL != (result = hsearch( item, FIND)) )
      printf( "%s key data is %s\n", result->key, (char *)result->data);

   item.key    = "7th";
   if ( NULL != (result = hsearch( item, FIND)) )
      printf( "%s key data is %s\n", result->key, (char *)result->data);

   hdestroy();
   return 0;
}

실행 결과

$ ./a.out
1st key data is jwmx.tistory.com
2nd key data is badayak.com
3rd key data is jwmx badayak
]$
이 댓글을 비밀 댓글로