열혈 자료구조 - 13.1 빠른 탐색을 보이는 해쉬 테이블

테이블 자료구조

- 데이터가 key-value(data) 구조로 저장된 구조

- key가 데이터의 저장 및 탐색의 도구이기 때문에 key를 이용해 원하는 데이터를 찾을 수 있음

- key는 중복될 수 없고 데이터를 근거로 만들어지기 때문에 의미있는 값을 가짐

- 테이블 자료구조의 탐색 연산은 O(1)의 시간 복잡도를 보이는 장점이 있지만 메모리의 효율성이 낮고 및 적용 범위가 제한점이라는 단점이 있음

- 사전 구조 혹은 map이라고도 함

- 간단한 key-value 구조

typedef struct _empInfo {
    int empNum;		// 사번(key)
    int age;		// 나이(value)
} EmpInfo;

int main()
{
    EmpInfo empArr[1000];
    EmpInfo em;
    em.empNum = 100;
    em.age = 20;
    
    empArr[em.empNum] = em;		// 키를 근거로 데이터 저장
    em = empInfo[100];			// 키를 근거로 데이터 접근
 }

 

해쉬 함수와 충돌 문제

- 위와 같이 배열의 크기를 1000으로 설정하면 유효한 key(사번) 0~999를 가지게 되면 의미를 갖는 사번(2020005)와 같은 사번을 제대로 등록할 수 없음

- 혹은 위와 같은 사번을 사용하기 위해 배열의 크기를 늘리는 것도 비효율적임

- 유효한 key를 0~999 중 하나의 인덱스 값(해쉬)으로 매칭을 시켜주는 해쉬 알고리즘(함수)가 필요

- 간단한 해쉬 함수는 아래와 같이 구성할 수 있음

int GetHashValue(int nEmpNum)
{
    int nResult = nEmpNum % 1000;
    return nResult;
}

- 하지만 위와 같은 방식은 충돌을 일으킬 수 있음

- 각각 다른 사번을 해쉬 함수를 통해 인덱스 값을 얻었지만 같은 값이 추출되어 충돌하는 경우가 있음

- 테이블에서는 이러한 충돌을 처리하는 것이 매우 중요

 

슬롯과 테이블

- key와 value를 저장하는 구조체(공간)

typedef int KEY;
typedef Info* VALUE;
typedef int HashFunc(KEY key);

enum SlotState = {EMPTY, DELETED, INUSE};

typedef struct _Info {
    int nEmpNum;
    int nAge;
} Info;

typedef struct _Slot {
    KEY key;
    VALUE val;
    enum SlotState enState;
} Slot;

typedef struct _table {
    Slot tbl[MAX_TBL];
    HashFunc* hf;		// 등록할 수 있는 해쉬함수
} Table;

- 슬롯의 상태를 비어있는(EMPTY), 이전에 사용되었다가 비어진(DELETED), 사용중인(INUSE)로 구분

- DELETE 상태는 충돌 문제를 해결하기 위한 상태

- 테이블 관련 함수

    -> 초기화 : 모든 슬롯의 상태를 EMPTY로 설정하고 해쉬 함수 등록

void TBLInit(Table * pt, HashFunc * f)
{
    int i;

    for(i=0; i<MAX_TBL; i++) {
        (pt->tbl[i]).status = EMPTY;
    }

    pt->hf = f;
}

    -> 삽입 : 테이블에 키와 값을 저장

void TBLInsert(Table * pt, Key k, Value v)
{
	int hv = pt->hf(k);		// 전달받은 유효한 키를 받아 해쉬를 돌려 인덱스 값을 얻어옴
	pt->tbl[hv].val = v;
	pt->tbl[hv].key = k;	// 해당 슬롯에 key와 value를 저장
	pt->tbl[hv].enState = INUSE;		// 해당 슬롯의 상태를 사용중으로 설정
}

    -> 삭제 : 테이블의 인덱스에 해당하는 슬롯의 상태를 DELETED 상태로 바꾸고 값을 반환

Value TBLDelete(Table * pt, Key k)
{
	int hv = pt->hf(k);

	if((pt->tbl[hv]).enState != INUSE) {
		return NULL;
	}
	else {
		(pt->tbl[hv]).enState = DELETED;
        	Value nValue = (pt->tbl[hv]).val;
		return nValue;
	}
}

    -> 탐색 : 유효한 키를 이용해서 해당 인덱스의 슬롯의 값을 반환

Value TBLSearch(Table * pt, Key k)
{
    int hv = pt->hf(k);

    if((pt->tbl[hv]).enState != INUSE) {
        return NULL;
    }
    else {
        Value nValue = (pt->tbl[hv]).val;
        return nValue;
    }
}

 

좋은 해쉬 함수의 조건

- 좋은 해쉬 함수를 사용한 결과는 데이터의 저장 위치가 몰려있지 않고 적당히 분산되어 있음

- 좋은 해쉬 함수를 만들기 위해서는 유효한 키의 일부분을 참조하지 않고 전체를 참조하여 해쉬 값을 만들어 내는것이 중요