[알고리즘](C언어) 해싱을 이용한 사전의 해시테이블 구현

사전은 위 그림과 같이 리스트, 트리, 해시테이블로 구현할 수 있다. 

그리고 구현 형태에 따라 모든 작업에 있어 필수로 수행되는 탐색 기법 또한 달라진다.

 

사전을 리스트로 구현할 경우,

무순 사전 ADT와 순서 사전 ADT로 구현할 수 있는데, 무순 사전 ADT를 이용해 구현할 경우 선형탐색으로 탐색을 수행할 수 있다. 순서 사전 ADT를 이용해 구현할 경우 이진탐색으로 탐색을 수행할 수 있다. 

 

사전을 트리로 구현할 경우,

탐색 트리로 구현할 수 있다. 이때 트리탐색으로 탐색을 수행할 수 있다. 탐색 트리는 이진탐색트리, AVL 트리 등으로 세분구분된다.

 

사전을 해시테이블로 구현할 경우,

해싱으로 탐색을 수행할 수 있는데, 해당 포스트에서는 그 방법에 대해 알아보자.

 

1. 해시테이블(hash table)

• 해시테이블: 키를 주소에 매핑하여 구현된 사전 ADT
  • ex. 컴파일러의 심볼 테이블, 환경변수들의 레지스트리
• 해시테이블 = 버켓배열 + 해시함수
  • 해시테이블 = 공간(memory) + 로직/알고리즘
  • 항목들의 키를 주소(즉, 배열 index)로 매핑함으로서 1차원 배열에 사전 항목들을 저장
• 성능
  • 탐색, 삽입, 삭제
    • O(n) 최악시간
    • 그러나 O(1) 기대시간

1-1. 버켓 배열(bucket array)

• 해시테이블을 위한 버켓 배열은 크기 M의 배열 A로서
  • A의 각 셀을 버켓(즉, 키-원소 쌍을 담는 그릇)으로 본다 
    • 슬롯(slot)이라고도 함
  • 정수 M은 배열의 용량을 정의
  • 키 k를 가진 원소 e는 버켓 A[k]에 삽입
  • 사전에 존재하지 않는 키에 속하는 버켓 셀들은 NoSuchKey라는 특별한 개체를 담는 것으로 가정(초기값)

버켓 배열 분석

• 키가 중복되지 않는 유일한 정수며 [0,M-1] 범위에 잘 분포되어 있다(골고루)면, 해시테이블에서의  탐색, 삽입, 삭제에 O(1)의 최악시간 소요
• 그러나 위에는 두 가지 중요한 결함이 있다.
  • O(n) 공간을 사용하므로 M이 n에 비해 매우 크다면 공간 낭비
    • (M-n) 개에 해당하는 공간은 사용이 안 되고 NoSuchKey만 저장되어 있을 것
  • 키들이 [0,M-1] 범위 내의 유일한 정수여야 하지만, 이는 비현실적이다.
    • 키가 문자열일 수도 있다.
• 따라서 결함을 메꾸기 위해서 다음과 같은 설계 목표를 세울 수 있다.
  • 해시테이블 데이터구조를 정의할 때는, 키를 [0,M-1] 범위 내의 정수로 매핑하는 좋은 방식과 함께 버켓 배열을 구성해야 한다.
  • 그 좋은 방식을 해시 함수라고 한다.

1-2. 해시 함수(hash function) 및 해시테이블

• 해시함수 h: 주어진 형의 키를 고정 범위 [0,M-1]로 매핑
  • ex. h(x) = x % M
    • x: 학번
    • M: 방 개수
    • h: 정수 키 x에 대한 해시함수
• 정수 h(x): 키 x의 해시값(hash value)
• 주어진 키 형의 헤시테이블은 다음 두 가지로 구성
  • 해시함수 h
  • 크기 M의 배열(테이블/해시테이블 이라 불림)
• 사전을 해시테이블로 구현할 때, 목표는 항목 (k,e)를 첨자 i = h(k)에 저장하는 것

예시

• (전화번호, 이름) 항목들을 저장하는 사전을 위한 해시테이블을 설계하자.
  • 전화번호는 10자리의 양의 정수로 가정
• 설계된 해시테이블은 크기 M=10,000의 배열과 아래 해시함수를 사용
• h(x) = x의 마지막 네 자리 수

• 배열에 골고루 잘 분포되어 있다면 잘 설계된 것

1-3. 해시함수

• 해시함수(hash function)는 보통 두 함수의 복합체로 명세
  • 해시코드맵(hash code map) h1: keys -> integers
    • 키를 정수로 매핑함(즉, 바꿔줌)
  • 압축맵(compression map) h2: integers -> [0,M-1]
    • 얻은 정수를 산술 계산하여 매핑함
• 먼저 해시코드맵을 적용하고 그 결과에 압축맵을 적용
  • 즉, h(k) = h2(h1(k))
• 좋은 해시함수가 되기 위한 조건
  • 키들은 외견상 무작위(random)하게 분산시켜야 한다.
  • 계산이 빠르고 쉬워야 한다.(가능하면 상수시간)

예시

• 학번 -> 마지막 4자리 수 -> 방번호 [0,2]
• 식별자 -> 문자합 -> 심볼 테이블 행번호 [0,27]

1) 해시코드맵의 방법

1. 메모리 주소(memory address)

• 키 개체의 메모리 주소를 정수로 재해석
• 일반적으로 만족스러우나 수치 또는 문자열 키에는 적용 곤란

2. 정수 캐스트(integer cast)

• 키의 비트값을 정수로 재해석
• 정수형에 할당된 비트 수를 초과하지 않는 길이의 키에는 적당

3. 요소합(component sum)

• 키의 비트들을 고정 길이(예: 16 또는 32 bits)의 요소들로 분할한 후 각 요소를 합한다
• 정수형에 할당된 비트 수 이상의 고정길이의 수치 키에 적당
  • ex. Java의 long, double
• 문자의 순서에 의미가 있는 문자열 키에는 부적당
  • ex. temp01-temp10, stop-tops-spt-pots

4. 다항 누적(polynomial accumulation)

• 요소합과 마찬가지로, 키의 비트들을 고정길이(예: 8, 16, 32bits)의 요소들로 분할
  • a0a1 ... a(n-1)
• 고정값 z를 사용하여 각 요소의 위치에 따른 별도 계산을 부과한 다항식 p(z)를 계산
  • p(z) = a_0 + a_1z + a_2z^2 + ... + a_(n-1)z^(n-1)
• 문자열에 특히 적당
  • 예: 고정값 z = 33을 선택할 경우, 50,000개의 영단어에 대해 단지 6회의 충돌 발생
    • 충돌: 같은 자리에 둘이 배정되는 경우

2) 압축맵의 방법

1. 나누기(division)

• h_2(k) = |k| % M
• 해시테이블의 크기 M은 일반적으로 소수(prime)로 선택

2. 승합제(multiply, add and divide, MAD)

• h_2(k) = |ak + b| % M
• a와 b는 음이 아닌 정수로서 a % M != 0
  • 그렇지 않으면, 모든 정수가 동일한 값 b로 매핑됨
• 1의 방법으로 잘 분산이 안 되면 2의 방법 씀

2. 충돌 해결

• 충돌(collision): 두 개 이상의 원소들이 동일한 셀로 매핑
• 즉, 상이한 키 k1과 k2에 대해 h(k1) = h(k2)면 충돌이 일어났다고 말한다.
• 충돌 해결(collision resolution)을 위한 일관된 전략 필요

2-1. 분리연쇄법(separate chaining)

• 분리연쇄법 또는 연쇄법에서는 각 버켓 A[i]는 리스트 Li에 대한 참조(pointer)를 저장
  • Li는 해시함수가 버켓 A[i]로 매핑한 모든 항목들을 저장
  • 무순리스트 또는 기록파일 방식을 사용하여 구현된 미니 사전이라고 볼 수 있다.
• 장단점
  • 단순하고 빠르다는 장점이 있으나, 테이블 외부에 추가적인 저장공간을 요구
    • 테이블 외부에 리스트 L_0, L_1, ..., L_{M-1}을 위한 추가적인 저장공간을 필요로 한다.

예

• M=13
• h(k) = k % M
• 분리연쇄법을 이용하여 해시테이블 만드는 예시

 

• 참고: 리스트에 추가되는 항목들의 위치는, 리스트의 테일 포인터(맨 뒤 노드)를 별도로 유지하지 않는 경우라면 리스트의 맨 앞에 삽입하는 것이 유리
  • 즉, 테일 포인터를 별도로 관리하면 맨 앞에 삽입하지 않아도 된다. 

 

2-2. 개방주소법(open addressing)

• 개방주소법: 충돌 항목을 테이블의 다른 셀에 저장
  • 외부 메모리에 저장하지 않는다.
• 장단점: 분리연쇄법에 비해 공간 사용을 절약하지만, 삭제가 어렵다는 것과 사전 항목들이 연이어 군집화(clustering)되어 사전의 탐색, 삭제, 삽입 ㅇ효율이 떨어짐

삭제가 어려운 이유

 

2-2-1. 선형조사법(linear probing)

• 선형조사법: 충돌 항목을 (원형으로) 바로 다음의 비어있는 테이블셀에 저장함으로써 충돌을 처리 - 즉, 다음 순서에 의해 버켓을 조사
  
  • 원형으로 처리하므로, 맨 끝에서 충돌이 일어나면, 맨 첫 셀에 저장됨
  • 단, 한 방향으로만 이동함

• 검사되는 각 테이블 셀은 조사(probe)라 불린다.
• 충돌 항목들은 군집화되며, 이후의 충돌에 의해 더욱 긴 조사열(probe sequence)로 군집 -> 1차 군집화(primary clustering)
  • 바로 옆 자리로 군집화 됨

2-2-2. 2차 조사법(quadratic probing)

• 해시값이 동일한 키들은 동일한 조사를 수반
• 1차 군집화를 피하지만 나름대로의 군집을 형성 -> 2차 군집화(secondary clustering)
• M이 소수가 아니거나 버켓 배열이 반 이상 차면, 비어있는 버켓이 남아있더라도 찾지 못할 수 있다.
  • M이 약수가 많을수록 안 좋음

2-2-3. 이중해싱(double hashing)

• 이중해싱: 두번째 해시함수 h'를 사용하여 다음 순서에 의해 버켓을 조사
• 동일한 해시값을 가지는 키들도 상이한 조사를 수반할 수 있기 때문에 군집화를 최소화
• h'는 계산 결과가 0이 되면 안 된다
• 최선의 결과를 위해, h'(k)와 M은 서로소(relative prime)여야 한다

• h'(k)의 세 예시
  • h'(k) = q - (k % q)
  • h'(k) = 1 + (k % q)
  • h'(k) = 11 - (k % 11)

 

개방주소법에서의 갱신

• 비활성화 전략
  • 기존 태그
    • empty: 비어있는 셀
    • active: 사용 중인 셀(활성)
  • 추가 태그
    • inactive: 삭제된 셀(비활성)

findElement(k)

1. 셀 h(k)에서 출발하여, 다음 가운데 하나일 때까지 조사

• 비어 있는 셀을 만나면 탐색 실패
• 활성 셀의 항목 (k,e)를 만나면 e를 반환
• M개의 셀을 검사

2. 탐색 실패

insertItem(k,e)

1. 셀 h(k)에서 출발하여, 다음 가운데 하나일 때까지 조사

• 비어 있거나 비활성인 셀을 만나면 항목 (k,e)를 셀에 저장한 후 활성화
• M개의 셀을 검사

2. 테이블 만원 예외를 발령

removeElement(k)

1. 셀 h(k)에서 출발하여 다음 가운데 하나일 때까지 조사

• 비어 있는 셀을 만나면 탐색 실패
• 활성 셀의 항목 (k,e)를 만나면 비활성화 하고 e를 반환
• M개의 셀을 검사

2. 탐색 실패

3. 적재율(load factor)

• 해시테이블의 적재율, alpha = n/M
  • 즉, 좋은 해시함수를 사용할 경우의 각 버켓의 기대 크기
• 적재율은 낮게 유지되어야 한다(가능하면 1 아래로)
• 적절한 해시함수가 주어졌다면, findElement, insertItem, removeElement 각 작업의 기대실행시간(expected running time): O(alpha)

1. 분리연쇄법

• alpha>1 이면, 작동은 하지만 비효율적
  • 외부에 연결리스트로 저장되므로
• alpha<=1 이면(기왕이면 0.75 미만이면), O(alpha) = O(1)의 기대실행시간 성취 가능

2. 개방주소법

• 항상 alpha<=1
  • 저장공간 내부에 저장되므로
• alpha>0.5면, 선형 및 2차 조사법인 경우 군집화 가능성 농후
• alpha<=0.5면, O(alpha) = O(1) 기대실행시간 

4. 재해싱(rehashing)

• 해시테이블의 적재율을 상수(보통 0.75) 이하로 유지하기 위해서는, 원소를 삽입할 때마다 이 한계를 넘기지 않기 위해 추가적인 작업 필요
• 언제 재해싱을 하는가?
  • 적재율의 최적치를 초과했을 때
  • 삽입이 실패한 경우
  • 너무 많은 비활성 셀들로 포화되어 성능이 저하되었을 때
• 재해싱의 단계

1. 버켓 배열의 크기를 증가시킨다(원래 배열의 대략 두 배 크기로 - 이때 새 배열의 크기를 소수로 설정하는 것에 유의)
2. 새 크기에 대응하도록 압축맵을 수정 -> h2만 수정하면 됨
3. 새 압축맵(h2)을 사용하여, 기존 해시테이블의 모든 원소들을 새 테이블에 삽입

5. 해싱의 성능

• 해시테이블에 대한 탐색, 삽입, 삭제: 최악의 경우 O(n) 시간 소요
  • 최악의 경우: 사전에 삽입된 모든 키가 충돌할 경우
• 적재율은 해시테이블의 성능을 좌우
• 해시값들은 난수(random numbers)와 같다고 가정하면, 개방주소법에 의한 삽입을 위한 기대 조사 횟수는 1/(1-alpha)라고 알려짐
• 해시테이블에서 모든 사전 ADT 작업들의 기대 실행시간: O(1)
• 실전에서, 적재율이 1(즉, 100%)에 가깝지만 않다면 해싱은 매우 빠르다.
• 응용
  • 소규모 데이터베이스
  • 컴파일러
  • 브라우저 캐시

6. 구현

문제 1: 분리연쇄법 해시테이블

크기 M인 해시테이블에 여러 개의 키 값을 입력받아 저장하고, 분리연쇄법을 이용하여 충돌을 처리하는 해시테이블 프로그램을 작성하시오.

 

• 구현 조건
  • 해시테이블은 크기가 M인 배열로 동적 할당한다.
  • 입력 키는 중복이 없는 자연수다.
  • 키 x에 대한 해시함수 h(x) = x % M 을 사용한다.
  • 삽입 시 충돌이 발생하는 경우, 해당 버켓 리스트의 맨 앞에 삽입한다.
• 입력
  • 해시테이블의 크기 M을 입력받는다.
  • 삽입(i), 탐색(s), 삭제(d), 인쇄(p) 명령어를 순서에 상관없이 반복하여 입력받는다.
    • i : 키 x를 해시테이블에 삽입
    • s : 키 x가 해시테이블에 존재하는지 탐색
    • d : 키 x가 해시테이블에 존재하면 삭제
    • p : 해시테이블에 저장된 키들을 순서대로 인쇄(입출력 예시 참조)
    • e : 프로그램 종료 
• 출력
  • 키를 삽입하였을 때 아무 출력을 하지 않는다.
  • 탐색 또는 삭제할 때, 키가 존재하면 리스트에서 해당 키가 저장된 순위(1부터 시작)를 인쇄하고 없다면 0을 인쇄한다(해시테이블의 주소가 아닌 리스트에서의 순위를 인쇄함에 유의).
  • 해시테이블을 인쇄할 때, 0번 주소부터 마지막 주소까지 순회하면서 저장된 키들을 방문하는 순으로 인쇄한다.

#include <stdio.h>
#include <stdlib.h>
#pragma warning (disable:4996)

typedef struct _Node
{
	int value;
	struct _Node* next;

} Node;

void initBucketArray(Node* table, int size);
int hash(int n, int size);
void insertItem(Node* table, int size, int x);
void search(Node* table, int size, int x);
void deleteItem(Node* table, int size, int x);
void printTable(Node* table, int size, int x);
void freeTable(Node* table, int size);

/*
ex 1)

13
i 34
i 23
i 26
i 21
s 36
s 26
s 34
s 21
p
d 21
s 34
d 8
e


*/

// 분리연쇄법 해시테이블
int main() {

	int size, x;
	char type;
	Node* table;

	scanf("%d", &size);
	getchar();

	table = (Node*)malloc(sizeof(Node)*size);

	initBucketArray(table, size);

	while (1)
	{
		scanf("%c", &type);

		if (type == 'e')
			break;
		switch (type)
		{
		case 'i':
			scanf("%d", &x);
			insertItem(table, size, x);
			break;
		case 's':
			scanf("%d", &x);
			search(table, size, x);
			break;
		case 'd':
			scanf("%d", &x);
			deleteItem(table, size, x);
			break;
		case 'p':
			printTable(table, size, x);
			break;
		}
	}

	freeTable(table, size);

	return 0;
}


// BucketArray 초기화
// 각 cell에 첫 번째는 포인터가 저장되며 값은 저장 안 됨
void initBucketArray(Node* table, int size)
{
	for (int i = 0; i < size; i++)
	{
		table[i].value = NULL;
		table[i].next = NULL;
	}
	return;
}


// 키 x에 대한 해시함수
int hash(int x, int size)
{
	return x % size;
}

void insertItem(Node* table, int size, int x)
{
	int v = hash(x, size);

	Node* p = table + v;
	Node* newNode = (Node*)malloc(sizeof(Node));

	newNode->value = x;
	newNode->next = NULL;

	if (p->next == NULL) // bucket array의 셀이 비어있으면 바로 저장
	{
		p->next = newNode;
	}
	else // bucket array가 이미 차있으면, 연결리스트로 맨 앞에 매달아줌
	{
		newNode->next = p->next;
		p->next = newNode;
	}
}


// 해당하는 셀로 이동하고
// 셀이 비어있지 않을 때까지 탐색 반복
// 만약 리스트에 value가 존재하면 리스트에서 해당 키가 저장된 순위 인쇄
void search(Node* table, int size, int x)
{
	int v = hash(x, size);
	int count = 0;

	Node* p = (table + v)->next;

	while (p != NULL)
	{
		count++;
		if (p->value == x)
		{
			printf("%d\n", count);
			return;
		}
		p = p->next;
	}
	printf("0\n");
}


void deleteItem(Node* table, int size, int x)
{
	int v = hash(x, size);
	int count = 0;

	Node* p = (table + v)->next;
	Node* temp = (table + v); // 지운 키의 다음 노드를 연결해주기 위한 임시 노드

	while (p != NULL)
	{
		count++;
		if (p->value == x)
		{
			while (temp->next != p)
				temp = temp->next;
			temp->next = p->next;
			printf("%d\n", count);
			return;
		}
		p = p->next;
	}
	printf("0\n");
}


void printTable(Node* table, int size, int x)
{
	Node* p;

	for (int i = 0; i < size; i++)
	{
		p = table + i;
		if (p->next != NULL)
		{
			p = p->next;
			printf(" %d", p->value);
			while (p->next != NULL)
			{
				p = p->next;
				printf(" %d", p->value);
			}
		}
	}
	printf("\n");
}


void freeTable(Node* table, int size)
{
	Node* p, *q;
	for (int i = 0; i < size; i++)
	{
		if ((table + i)->next != NULL)
		{
			p = (table + i)->next;
			q = p;
			while (q->next != NULL)
			{
				p = p->next;
				free(q);
				q = p;
			}
		}
	}
	free(table);
}

 

 

문제 2: 개방주소법 해시테이블 - 선형조사법

크기 M인 해시테이블에 n개의 키 값을 입력받아 저장하고, 개방주소법 중 선형조사법을 이용하여 충돌을 처리하는 해시테이블 프로그램을 작성하시오.

 

• 구현 조건
  • 해시테이블은 크기가 M인 배열로 동적 할당한다.
  • n은 M보다 작은 자연수로 최대 삽입 개수다.
  • 입력 키는 중복이 없는 6자리 또는 8자리의 임의의 자연수(학번)다.
  • 키 x에 대한 해시함수 h(x) = x % M 을 사용한다.
  • 저장된 키 값이 없는 빈 버켓은 0으로 처리한다. 
• 입력
  • 해시테이블의 크기 M과 입력 데이터의 크기 n을 입력받는다.
  • 삽입(i), 탐색(s) 명령어를 순서에 상관없이 반복하여 입력받는다.
    • i : 키 x를 해시테이블에 삽입
    • s : 키 x가 해시테이블에 존재하는지 탐색
    • e : 프로그램 종료
• 출력
  • 키를 삽입하였을 때, 저장된 주소(배열 인덱스)를 인쇄한다.
  • 삽입할 때 충돌이 일어나면 선형조사법에 의해 다음 셀로 이동하여 충돌 검사를 계속한다. 충돌 횟수만큼 C를 인쇄한 후, 삽입에 성공한 주소를 인쇄한다.
  • 탐색한 키가 테이블에 존재할 경우, 키가 저장된 주소와 값을 인쇄한다(없을 경우 –1을 인쇄한다).

code

문제 3: 개방주소법 해시테이블 - 이중해싱

문제 2에서 충돌처리 방법을 이중해싱으로 변경하시오.

• 구현 조건
  • 해시테이블은 크기가 M인 배열로 동적 할당한다(종료 시 해제).
  • n은 M보다 작은 자연수로 최대 삽입 개수다.
  • 입력 키는 중복이 없는 2자리 이상의 자연수다.
  • 키 x에 대한 첫 번째 해시함수 h(x) = x % M, 두 번째 해시함수 h‘(x) = q – (x % q) 를 사용한다. q는 M보다 조금 작은 소수로 입력으로 주어진다.
  • 저장된 키가 없는 빈 버켓은 0으로 처리한다.
• 입력
  • M, n, q를 입력받는다.
  • 삽입(i), 탐색(s), 출력(p) 명령어를 순서에 상관없이 반복하여 입력받는다.
    • i <x> : 키 x를 입력받아 해시테이블에 삽입
    • s <x> : 키 x가 해시테이블에 존재하는지 탐색
    • p : 현재의 해시테이블 인쇄
    • e : 해시테이블 인쇄 후 프로그램 종료 
• 출력
  • 키를 삽입하였을 때, 저장된 주소(배열 인덱스)를 인쇄한다. 
  • 삽입할 때 충돌이 일어나면 두 번째 해시함수로부터 얻은 셀로 이동하여 충돌 검사를 계속한다. 충돌 횟수만큼 C를 인쇄한 후, 삽입에 성공한 주소를 인쇄한다.
  • 탐색한 키가 테이블에 존재할 경우, 키가 저장된 주소와 값을 인쇄한다(없을 경우 –1을 인쇄한다).

code