[C] 해시 테이블 (Hash Table) 개념 및 구현

개념

해시 함수를 이용하여 키(key)를 index로 만들어 배열의 해당 index에 데이터를 보관하는 자료구조

 

보통 키(key)로 값(value)을 맵핑하는 식으로 사용한다.

 

C++ STL의 unordered_map, unordered_set, 그리고 여러 언어들의 Dictionary나 HashMap, HashSet 등이 포함된다.

 

 

특징

- 배열의 각 요소는 키와 값 등으로 이루어진 구조체(및 클래스)로 이루어져 있다.

 

- key를 index로 변환시키는 다양한 해시 함수가 존재하며, 이의 성능에 따라 더욱 성능이 좋아질 수 있다.

 

- 특정 요소 삽입, 삭제, 탐색이 O(1)이며, 최악의 경우 O(N)이다.

 

 

장점

특정 요소를 탐색할 때 O(1)으로 굉장히 빠르다.

 

 

단점

1. 충돌 가능성을 줄이기 위해 데이터 개수보다 큰 크기의 배열을 할당하여, 배열보다 상대적으로 메모리를 많이 사용한다.

 

2. index의 충돌이 일어날 경우 O(N)까지 느려질 수 있어서 좋은 해시 함수 사용과 적절한 충돌 대처를 해두어야 한다.

 

 

상세 설명

해시 테이블에서는 여러 수학적, 암호학적 개념이나 증명이 많이 필요하나,

본 포스팅에서는 그런 부분은 깊게 파헤치지 않고 자료 구조에 중점을 두려고 한다.

 

 

위의 그림과 같이 apple이라는 키를 해시 함수에 넘겨주고, 반환되는 정수 값을 index로 만들어 삽입하는 구조다.

 

해시 함수는 정말 간단한 것부터 수백 줄 이상 되는 것까지 다양한데,

키가 정수일 경우, 제일 간단한 방법은 간단하게 키를 배열의 크기로 나머지 연산을 하는 것이다.

 

키가 문자열일 경우의 예시

예를 들어 키가 8이고, 배열의 크기가 7일 때, 8 % 7 의 결과는 1이므로 배열의 index 1에 키와 값을 넣어두는 것이다.  

이후 8이라는 키로 찾으면, 삽입할 때 쓰였던 방법과 똑같이 8 % 7의 결과인 1의 index에 접근하여 값을 가져오면 된다.

 

하지만 이후 15라는 키로 데이터를 삽입하려고 하면 어떻게 될까?

15 % 7은 결과가 1이고, 아까 8이라는 데이터를 담아두었기 때문에 충돌이 일어나게 된다.

 

충돌 관리

 

이럴 때 대표적으로 두 가지 방법이 존재한다.

 

1. Separate Chaining 방식

  : 배열의 각 요소를 연결 리스트나 이진 탐색 트리로 만들어 계속 해당 index에 데이터를 추가한다.

 

 

위의 그림과 같이 계속해서 그 뒤를 이어 노드를 추가하는 방식이다.

 

데이터를 탐색할 때는 해당 index에 있는 연결 리스트 혹은 이진 탐색 트리를 쭉 탐색하면 된다.

 

 

2. Open Addressing 방식

  : 해당 index부터 시작해서 빈 곳이 나올 때까지 다음 index로 넘어가서 데이터를 삽입한다.

    index를 넘기는 방법은 대표적으로 다음과 같이 세 가지가 있다.

 

    (1) 선형 프로빙 (Linear probing) : 간격을 고정하여 증가

    (2) 이차 프로빙 (Quadratic probing) : 임의의 2차 다항식의 연속적인 값을 추가하여 증가

    (3) 이중 해싱 (Double Hashing) : 간격이 보조 해시 함수에 의해 계산

 

 

데이터를 탐색할 때도 들어온 키와 저장 돼있는 키를 비교하며 계속 다음 index로 넘어가며 탐색하면 된다.

 

그렇기 때문에 Open Addressing의 경우는 요소를 삭제할 때 주의해야 할 점이 있다.

 

 

똑같은 hash 결과 값으로 충돌이 일어난 세가지 데이터가 담겨져 있다.

 

그런데 중간의 데이터인 " hello "가 지워지고 EMPTY state가 된 상태라고 치다.

 

 

" banana " 를 찾으려고 할 때, EMPTY state가 아닐 때까지 배열의 모든 요소를 순회해야 하는데

방금 전 중간 값을 지워버려서 " banana "를 찾을 수 없게 되었다.

 

 

지워진 곳은 dummy 데이터를 두거나, 이처럼 state를 하나 추가하여 관리해야 해시 테이블의 구조를 유지할 수 있다.

 

배열 크기 재조정

해시 테이블에서는 부하율이라는 개념도 중요하다.

부하율이란, 데이터의 개수를 배열의 크기로 나눈 것이다.

 

특정 부하율이 넘어간다면 크기를 재조정 하는 것도 중요한 포인트이다.

 

크기를 재조정하면서, 기존의 해시 값들을 늘어난 배열의 크기로 나머지 연산을 수행하게 되면,

기존에 충돌했던 데이터들도 다시 배치되며 충돌되지 않게 삽입될 가능성이 있다.

 

 

위의 그림과 같이 기존 데이터들의 해싱 값들을 저장해두고,

resize를 진행할 때 나머지 연산만 다시 수행해주며 데이터를 재배치 해주는 것이다.

 

기존 데이터들의 해싱 값을 꼭 저장할 필요는 없지만,

resize를 진행할 때 다시 해시 함수를 거쳐야 한다는 점을 고려해야한다.

 

 

구현

필자는 Open Addressing의 linear probing 방식으로 구현했다.

 

일단 본격적으로 들어가기 전에 필자는 키, 값 쌍으로 된 데이터를 다룰 것이기 때문에 이에 대한 코드부터 소개하겠다.

 

typedef struct pair
{
	char* key;
	int value;
} pair;

pair* make_pair(char* key, int value)
{
	pair* new_pair = (pair*)malloc(sizeof(pair));

	new_pair->key = strdup(key);
	new_pair->value = value;

	return new_pair;
}

 

C++의 STL의 pair를 참고하여 만든 pair 구조체다. key와 value를 감싸고 있으며, key는 문자열이다.

 

설명에 앞서 참고해야할 사항 몇 가지

 

우선 해시 테이블의 할당과 해제는 프로그래머에게 맡긴다.

따라서 해시 테이블은 이미 할당되어 있다는 가정을 한다.

 

또한 다음과 같은 사항은 코드의 가독성 문제 등으로 염려에 두지 않았다.
  1. 함수의 해시 테이블(hash) 매개변수가 NULL pointer일 경우
  2. malloc() 이 실패한 경우
  3. free() 후 댕글링 포인터

  4. size와 capacity의 overflow

 

구조체

typedef enum state
{
	EMPTY,
	USED,
	DELETED
} state;

typedef struct node
{
	pair* data;
	unsigned int hash_value;
	state state;
} node;

typedef struct hash
{
	node* bucket;
	int size;
	int capacity;
} hash;

각 노드(node)는 pair형 data와 해시 함수를 거쳐 나온 해시값(hash_value), 열거형 state를 가지고 있다.

초기화

void initialize(hash* hash)
{
	hash->bucket = NULL;
	hash->capacity = 0;
	hash->size = 0;
}

해시 테이블의 할당은 프로그래머에게 맡기므로 각 데이터를 NULL과 0으로만 초기화 시켜준다.

 

해시 함수

static unsigned int hasing(unsigned char *str)
{
	unsigned int hash = 5381;

	while (*str != '\0')
	{
		hash = hash * 33 + *str;
		++str;
	}
	return hash;
}

문자열 해싱 알고리즘 중에 간단하고도 강력하다는 djb2 알고리즘으로 진행했다.

 

등장하는 매직넘버(상수) 5381과 33은 홀수이며 소수이고 결함수(?) 등의 특징을 가지고 있고,

문자열들의 강력한 암호화에 도움이 된다고 한다.

 

출처 : http://www.cse.yorku.ca/~oz/hash.html

 

데이터 삽입

#define MAX_LOAD_FACTOR 0.5

void insert(hash* hash, pair* data)
{
	if (hash->capacity == 0
		|| (double)hash->size / hash->capacity > MAX_LOAD_FACTOR)
		re_allocate(hash, hash->capacity * 2);
	
	unsigned int hash_value = hasing((unsigned char*)data->key);
	unsigned int idx = hash_value;

	while (hash->bucket[idx % hash->capacity].state == USED)
	{
		if (strcmp(hash->bucket[idx % hash->capacity].data->key, data->key) == 0)
			return;
		++idx;
	}

	hash->bucket[idx % hash->capacity] = (node){data, hash_value, USED};
	++hash->size;
}

먼저, hash의 capacity가 0이거나, 적재율이 정해진 값보다 클 때 resize를 진행한다.

re_allocate는 마지막에 설명하도록 하겠다.

 

해시 함수로 받은 값은 데이터에 같이 넣을 예정이므로 보존해두고 index용 변수를 따로 만들어 준다.

 

이후 넣으려는 node의 state가 EMPTY나 DELETED인 경우는 바로 삽입하고,

USED인 경우 strcmp()로 키 중복 검사를 진행한 후, 중복이 아니면 빈 곳을 찾을 때까지 index를 증가시킨다.

 

데이터 삭제

static int find_idx(hash* hash, char* key)
{
	unsigned int hash_value = hasing((unsigned char*)key);
	unsigned int idx = hash_value;

	for (int i = 0; i < hash->capacity; ++i, ++idx)
	{
		if (hash->bucket[idx % hash->capacity].state == EMPTY)
			break;
		if (hash->bucket[idx % hash->capacity].state == DELETED)
			continue;
		if (strcmp(hash->bucket[idx % hash->capacity].data->key, key) == 0)
			return idx % hash->capacity;
	}
	return -1;
}

void erase(hash* hash, char* key)
{
	int idx = find_idx(hash, key);
	if (idx == -1)
		return;
	
	free(hash->bucket[idx].data->key);
	free(hash->bucket[idx].data);
	hash->bucket[idx].state = DELETED;
	--hash->size;
}

find_idx() 함수는 데이터를 찾는 과정에서도 사용할 수 있도록 함수화를 진행했다.

 

데이터 삽입 과정에서와 같이 들어온 키를 해시 함수에 넣어 탐색을 진행한다.

 

이번엔 특정 요소를 탐색는 과정이기 때문에 EMPTY를 만났거나 배열을 모두 돌았다면 못 찾은 것으로 -1을 내보낸다.

 

strcmp()로 똑같은 키를 찾았다면 해당 index를 반환해준다.

 

이후 erase()에서는 받은 index에 있는 data를 free해주고 state를 DELETED로 바꿔준다.

 

데이터 탐색

pair* find(hash* hash, char* key)
{
	int idx = find_idx(hash, key);
	if (idx == -1)
		return NULL;
	
	return hash->bucket[idx].data;
}

데이터 삭제와 똑같이 받은 index의 data를 반환해준다.

 

데이터를 찾지 못했다면 NULL pointer를 반환해준다.

 

소수 구하기

static int get_next_prime(int num)
{
	while (true)
	{
		bool is_prime = true;

		for (long long i = 2; i * i <= num; ++i)
		{
			if (num % i == 0)
			{
				is_prime = false;
				break;
			}
		}
		if (is_prime)
			return (num);
		++num;
	}
}

위는 인자로 들어온 정수의 바로 다음에 있는 소수를 구하는 간단한 함수다.

 

배열의 총 크기는 소수로 정하는 것이 나머지 연산을 진행하여 해싱을 진행할 때 더욱 효과적이라고 한다.

 

배열 재할당

#define INITIAL_CAPACITY 7

static void re_allocate(hash* hash, int size)
{
	int prev_capacity = hash->capacity;

	if (size == 0)
		hash->capacity = INITIAL_CAPACITY;
	else
		hash->capacity = get_next_prime(size);

	node* new_bucket = (node*)malloc(hash->capacity * sizeof(node));
	for (int i = 0; i < hash->capacity; ++i)
		new_bucket[i].state = EMPTY;

	for (int i = 0; i < prev_capacity; ++i)
	{
		if (hash->bucket[i].state != USED)
			continue;
		unsigned int idx = hash->bucket[i].hash_value;

		while (new_bucket[idx % hash->capacity].state == USED)
		{
			if (strcmp(new_bucket[idx % hash->capacity].data->key, hash->bucket[i].data->key) == 0)
				return;
			++idx;
		}

		new_bucket[idx % hash->capacity] =
			(node){hash->bucket[i].data, hash->bucket[i].hash_value, USED};
	}
	free(hash->bucket);
	hash->bucket = new_bucket;
}

 

먼저 hash의 capacity가 0인 경우, 기본 초기화 값을 주고, 아닐 경우 인자로 받은 size 바로 다음 소수를 구해준다.

 

그렇게 얻은 capacity 만큼 할당해주고, 모든 state를 EMPTY로 초기화 시켜준다.

 

이후 기존 배열(bucket)에 있던 모든 데이터들을 새로운 배열에 재배치 시켜주는 작업을 해준다.

위에서 설명한대로 배열의 각 node는 해싱을 통해 얻은 값을 저장하고 있으며,

이를 새 배열의 크기로 나머지 연산만 해주어 index를 구하고, 새 배열의 얻은 index에 넣어주기만 하면 된다.

 

기존 배열의 DELETED node는 유지시킬 필요가 없으므로 USED인 상태의 node만 수행한다.

 

이후 기존 배열을 free해주고 새 배열의 주소를 복사해주면 끝이다.

 

모든 데이터 삭제

void clear(hash* hash)
{
	for (int i = 0; i < hash->capacity; ++i)
	{
		if (hash->bucket[i].state == USED)
		{
			free(hash->bucket[i].data->key);
			free(hash->bucket[i].data);
		}
	}
	free(hash->bucket);
	initialize(hash);
}

배열을 순회하며 data를 모두 free해주고나서 배열도 free해준다.

 

이후 구현해두었던 초기화 함수로 다시 hash를 초기화해준다.

 

테스트

리눅스 환경에서 여러 컴파일 옵션을 줘서 테스트했고

메모리 누수 포함 에러가 (아직은) 없는 것을 확인했다.

이번 테스트는 안타깝게도 출력 내용이 길어서 결과도 상당히 길다.

 

↓ 테스트 결과

 

 

 

 

 

 

↓ 테스트 코드 확인하기

 

#include "Hash.h"
#include <stdio.h>

void print_hash(hash* hash)
{
	printf("size: %d, cap: %d\n", hash->size, hash->capacity);
	for (int i = 0 ; i < hash->capacity; ++i)
	{
		switch (hash->bucket[i].state)
		{
		case 0:
			printf("[%d] EMPTY   , - : - [-]\n", i);
			break;
		case 1:
			printf("[%d] USED    , %s : %d [%u]\n", i, hash->bucket[i].data->key, hash->bucket[i].data->value, hash->bucket[i].hash_value % hash->capacity);
			break;
		case 2:
			printf("[%d] DELETED , - : - [-]\n", i);
			break;
		}
	}
	printf("\n");
}

void print_hash_find(pair* result)
{
	if (result == NULL)
		printf("key not found\n");
	else
		printf("%d\n", result->value);
}

int main()
{
	hash hash;
	
	printf("----- initialize -----\n");
	initialize(&hash);
	print_hash(&hash);

	printf("----- insert -----\n");
	insert(&hash, make_pair("hello", 1));
	print_hash(&hash);

	insert(&hash, make_pair("world", 2));
	print_hash(&hash);

	insert(&hash, make_pair("my name", 3));
	print_hash(&hash);

	insert(&hash, make_pair("is sikpang", 4));
	print_hash(&hash);

	insert(&hash, make_pair("nice", 5));
	print_hash(&hash);

	insert(&hash, make_pair("to meet you", 6));
	print_hash(&hash);

	insert(&hash, make_pair("this is", 7));
	print_hash(&hash);

	insert(&hash, make_pair("hash_table", 8));
	print_hash(&hash);

	insert(&hash, make_pair("thank you", 9));
	print_hash(&hash);

	printf("\n----- find -----\n");
	print_hash_find(find(&hash, "hash_table"));
	print_hash_find(find(&hash, "thank you!"));
	print_hash_find(find(&hash, "thank you"));
	print_hash_find(find(&hash, "hash_tablee"));


	printf("\n----- erase -----\n");
	erase(&hash, "mmm");
	print_hash(&hash);

	erase(&hash, "this is");
	print_hash(&hash);

	erase(&hash, "is sikpang");
	print_hash(&hash);

	erase(&hash, "world");
	print_hash(&hash);

	erase(&hash, "hello");
	print_hash(&hash);


	printf("\n----- edge_case -----\n");
	print_hash_find(find(&hash, "hello"));	// find the erased key
	print_hash_find(find(&hash, "world"));
	print_hash_find(find(&hash, "nice"));	// pass DELETED node when find

	insert(&hash, make_pair("world", 10));	// insert to DELETED node
	print_hash(&hash);

	insert(&hash, make_pair("hello", 11));
	print_hash(&hash);

	insert(&hash, make_pair("abc", 12));
	print_hash(&hash);

	insert(&hash, make_pair("abcd", 13));
	print_hash(&hash);

	print_hash_find(find(&hash, "abcd"));	// pass DELETED node when find
	printf("\n");

	insert(&hash, make_pair("abcde", 14));	// re_allocate
	print_hash(&hash);

	print_hash_find(find(&hash, "abcd"));	// find again!
	print_hash_find(find(&hash, "world"));
	print_hash_find(find(&hash, "my name"));
	print_hash_find(find(&hash, "is sikpang"));
	print_hash_find(find(&hash, "abcdef"));
	printf("\n");

	printf("\n----- clear -----\n");
	clear(&hash);
	print_hash(&hash);

	clear(&hash);			// double clear
	print_hash(&hash);

	insert(&hash, make_pair("abc", 1));	// use after clear
	print_hash(&hash);

	insert(&hash, make_pair("abcd", 2));
	print_hash(&hash);

	insert(&hash, make_pair("abcde", 3));
	print_hash(&hash);

	print_hash_find(find(&hash, "abc"));	// find again again!
	print_hash_find(find(&hash, "abcd"));
	print_hash_find(find(&hash, "world"));
}

 

 

마무리

해시 테이블이 이론 자체는 간단하지만, 깊게 들어가려면 굉장히 깊게 들어갈 수 있을 것 같은 자료 구조인 것 같다.

 

해시 함수와 더불어 여러 요인들이 해시 테이블의 성능에 굉장히 크게 작용하므로 

다음과 같은 여러가지 요인들을 고려해가며 구현해보는 것이 좋을 것 같다.

 

1. 해시 함수

2. 충돌 처리 방법

3. 배열의 크기, 증가 폭

4. 배열의 재할당 기준

 

마지막으로 전체 코드

https://github.com/SikPang/DataStructures/tree/main/C_HashTable

GitHub - SikPang/DataStructures

 

개인 공부용 포스팅인 점을 참고하시고, 잘못된 부분이 있다면 댓글로 남겨주시면 감사드리겠습니다.