테이블(Table)과 해쉬(Hash)

빠른 탐색을 보이는 해쉬 테이블

AVL 트리는 탐색과 관련하여 매우 만족스러운 성능을 보였다. 하지만 탐색 키의 비교 과정을 거치면서 찾는 대상에 가까워지는 방식이기 때문에, 원하는 바를 단번에 찾아내는 방식이라고 말하기는 어렵다. 이럴 때 도입을 검토할 수 있는 자료구조가 바로 테이블이다.

AVL 트리의 탐색 연산 :  O(log2 n)의 시간복잡도

테이블의 시간 복잡도 : O(1)

 

해쉬 함수 : 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할

충돌 : 서론 다른 두 개의 키가 해쉬 함수를 통과하였는데 그 결과가 같은 경우

좋은 해쉬 함수의 조건 : 데이터가 전체 영역에 고루 분포되어 있는 경우

ex)

Person.h

#ifndef __PERSON_H__
#define __PERSON_H__

#define STR_LEN    50

typedef struct _person
{
	int ssn;    // 주민등록번호 
	char name[STR_LEN];    // 이름
	char addr[STR_LEN];    // 주소
} Person;


int GetSSN(Person * p);

void ShowPerInfo(Person * p);

Person * MakePersonData(int ssn, char * name, char * addr);

#endif

Person.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Person.h"

int GetSSN(Person * p)
{
	return p->ssn;
}

void ShowPerInfo(Person * p)
{
	printf("주민등록번호: %d \n", p->ssn);
	printf("이름: %s \n", p->name);
	printf("주소: %s \n\n", p->addr);
}

Person * MakePersonData(int ssn, char * name, char * addr)
{
	Person * newP = (Person*)malloc(sizeof(Person));

	newP->ssn = ssn;
	strcpy(newP->name, name);
	strcpy(newP->addr, addr);
	return newP;
}

Slot.h

#ifndef __SLOT_H__
#define __SLOT_H__

#include "Person.h"

typedef int Key;
typedef Person * Value;

enum SlotStatus {EMPTY, DELETED, INUSE};

typedef struct _slot
{
	Key key;
	Value val;
	enum SlotStatus status;
}Slot;

// Slot과 관련해서는 별도의 함수를 정의하지 않는다.
#endif

Table.h

#ifndef __TABLE_H__
#define __TABLE_H__

#include "Slot.h" 

#define MAX_TBL     100

typedef int HashFunc(Key k);

typedef struct _table
{
	Slot tbl[MAX_TBL];
	HashFunc * hf;
}Table;


// 테이블의 초기화 
void TBLInit(Table * pt, HashFunc * f);

// 테이블에 키와 값을 저장
void TBLInsert(Table * pt, Key k, Value v);

// 키를 근거로 테이블에서 데이터 삭제
Value TBLDelete(Table * pt, Key k);

// 키를 근거로 테이블에서 데이터 탐색
Value TBLSearch(Table * pt, Key k);

#endif

Table.c

#include <stdio.h>
#include <stdlib.h>
#include "Table.h"

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;
	pt->tbl[hv].status = INUSE;
}

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

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

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

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

SimpleHashMain.c

#include <stdio.h>
#include <stdlib.h>
#include "Person.h"
#include "Table.h"

int MyHashFunc(int k)
{
	return k % 100;    // 키를 부분적으로만 사용한 별로 좋지 않은 해쉬의 예!!!
}

int main(void)
{
	Table myTbl;
	Person * np;
	Person * sp;
	Person * rp;

	TBLInit(&myTbl, MyHashFunc);

	// 데이터 입력
	np = MakePersonData(20120003, "Lee", "Seoul");
	TBLInsert(&myTbl, GetSSN(np), np);

	np = MakePersonData(20130012, "KIM", "Jeju");
	TBLInsert(&myTbl, GetSSN(np), np);

	np = MakePersonData(20170049, "HAN", "Kangwon");
	TBLInsert(&myTbl, GetSSN(np), np);

	// 데이터 검색
	sp = TBLSearch(&myTbl, 20120003);
	if(sp != NULL)
		ShowPerInfo(sp);

	sp = TBLSearch(&myTbl, 20130012);
	if(sp != NULL)
		ShowPerInfo(sp);

	sp = TBLSearch(&myTbl, 20170049);
	if(sp != NULL)
		ShowPerInfo(sp);

	// 데이터 삭제
	rp = TBLDelete(&myTbl, 20120003);
	if(rp != NULL)
		free(rp);

	rp = TBLDelete(&myTbl, 20130012);
	if(rp != NULL)
		free(rp);

	rp = TBLDelete(&myTbl, 20170049);
	if(rp != NULL)
		free(rp);

	return 0;
}

 

충돌 문제의 해결책

선형 조사법(Linear Probing) : 충돌이 발생했을 때 인덱스 옆 자리를 살피는 것

f(k)+1  ->  f(k)+2  ->  f(k)+3  ->  ....

문제점 : 충돌의 횟수가 증가함에 따라서 클러스터 현상(특정 영역에 데이터가 집중적으로 몰리는 현상)이 발생

=> 좀 멀리서 빈 공간을 찾자

이차 조사법(Quadratic Probing) : n^2칸 옆의 슬롯을 검사

f(k)+1^2  ->  f(k)+2^2  ->  ...

====> 앞에서 DELETED를 만든 이유 : 충돌이 발생한 해쉬값 하나를 삭제하면 옆 자리를 살피지 않기 때문

=> 이차 조사법도 너무 규칙적이야

이중 해쉬 : 두 개의 해쉬 함수를 사용

1차 해쉬 함수 : 키를 근거로 저장 위치를 결정하기 위한 것

h1(k)=k%15

2차 해쉬 함수 : 충돌 발생시 몇 칸 뒤를 살필지 결정하기 위한 것

h2(k)=1+(k%c)  (c는 15보다 작은 소수)

 

체이닝(Chaning)

열린 어드레싱 방법 : 앞서 소개한 유형의 방법. 충돌이 발생하면 다른 자리에 대신 저장한다. 

닫힌 어드레싱 방법 : 무슨 일이 있어도 자신의 자리에 저장을 한다.

2차원 배열을 이용하는 방법. 충돌이 발생하지 않을 경우 메모리 낭비가 심하고 충돌의 최대 횟수를 결정

체이닝 : 연결 리스트를 이용해서 슬롯을 연결하는 방법