해시테이블(Hash Table)과 체이닝(Chaining)에 대한 간략한 정리

해싱과, 해시테이블 그리고 충돌을 처리하는 체이닝 기법에 대해서 한 번 정리해보자.

이 글을 시작하기에 앞서, 스택오버플로우의 많은 자료들 그리고 위키피디아, 각종 유튜브 강의를 참고했다는 사실을 먼저 알립니다.

해시와 해시함수

해시 함수(Hash Function)는 데이터의 효율적인 관리를 위해 길이가 각기 다른 데이터를 고정 길이로 매핑하는 함수다. 이 때 매핑하는 과정을 해싱(Hashing)이라고 하며, 매핑하기 전의 데이터를 키(Key), 매핑 후의 데이터를 해시 값(Hash Value; 때로는 Value)이라 한다.

해시의 목적

해시 테이블(Hash Table)

해시 테이블은 데이터의 해시 값을 테이블 내 주소로 이용해먹는 탐색 알고리즘으로, 잘 구현하면 이진 탐색보다 빠르게 처리할 수 있다.

암호화

암호화에서 해시는 자주 등장한다. 어떤 값들을 해시로 변환하면, 기존의 값을 알아볼 수 없게 만든다. 이것 자체가 암호화에 매우 유용하며, 이런 해시의 특성을 활용한 대표적인 암호화 알고리즘이, SHA(Secure Hash Algorithm)이다.

데이터 축약

길이가 다른 데이터를 일정한 길이로 축약시킬 수 있다. 방대한 양의 데이터를 해시로 줄일 수 있으며, 데이터 비교에 있어서도 축약한 것을 비교하는 것이 원본 데이터를 비교하는 것보다 빠른 성능을 보일 수 있다. 단, 데이터가 다름에도 해시 값이 같은 경우가 발생할 수 있기 때문에, 충돌 가능성을 고려해야 한다.

해시에 대해서는 이쯤 설명하고, 이 포스트에서 다룰 것은 해시 테이블과 해시 테이블에서의 충돌을 피하기 위한 기법인 체이닝 기법이다.

기본적인 설명

해시 테이블은 앞서 말한 것처럼 해시값을 테이블 내 주소로 이용하는 탐색 알고리즘이다. 키값에 따라 접근하기 때문에 이론적으로 탐색, 삽입, 삭제 작업에서 평균적으로 상수 시간, O(1)의 시간 복잡도를 보이지만, 최악의 경우에는 O(n)이다. 공간 복잡도는 평균과 최악 구분할 것 없이 O(n)이다.

해시 함수는 키를 바탕으로 해시 주소를 생성하고, 이 해시 주소가 배열로 구현된 해시 테이블의 인덱스가 된다. 이 인덱스로 해당 위치에 배열을 저장하거나 삭제, 탐색할 수 있다. 아래 그림을 통해 간단하게 구조를 보고 넘어가자.

계산된 해시 주소를 통해 값을 저장한다. 이 때 저장되는 공간을 버켓이나 슬롯이라고 한다. 책에 따라서는 슬롯을 버켓의 하위 단위로 구분하는 경우가 있다. 해시 주소는 버켓에 접근할 때의 값이고, 그 버켓 내에서는 여러 개의 슬롯이 있는 구조에서 그렇게 구분하는데, 여기서는 그렇게 하지 않고 모두 슬롯이라고 지칭하겠다. 

여기서 키는 어떤 것이어도 상관이 없다. 개인 정보로 치면, 주민등록번호여도 되고, 이름이어도 된다.

가장 간단하게 해시 함수를 구현하는 방법은 바로 제산 함수, 즉 나머지 연산(mod)을 이용하는 것이다. 해시 함수의 다양한 연산법에 대해서는 다른 게시물에서 다루도록 하고, 여기서는 나머지 연산으로 구현해보자.

제산 함수로 된 해시 함수

H(k)= k mod M

여기서 M은 해시 테이블의 슬롯 사이즈로, 해시 주소값의 범위는 0~M-1까지다.

이렇게 키(Key)를 바탕한 계산한 해시 주소(Hash Address)에 값(Value)을 할당하는 것이 해시 테이블(Hash Table)인 것이다.

해시 테이블이 이상적으로 작동하기 위해서는 저장되는 값의 양이 슬롯의 크기보다 작으면서, 계산한 해시 주소의 값들이 한 번도 겹치지 않아야 한다. 해시 값이 겹치는 상황을 충돌(Collision)이라고 한다. 그러나, 이건 어디까지나 이상적인 이야기다. 실제와는 거리가 있다. 해시 테이블의 슬롯 크기보다 작고, 해시 주소의 값이 한 번도 겹치지 않는 건 어디까지나 데이터의 크기가 엄청 작을 때 가능할 법한 이야기다.

비둘기집 원리(Pigeonhole Principle)

M개의 비둘기 집에 M+1마리의 비둘기를 채워 넣는다고 할 때, 반드시 어느 한 집에는 비둘기가 두 마리 이상이 들어가게 된다는 원리로, 아주 기초적인 내용이다. 바꿔서 말하면 M개의 슬롯에 M+1개의 데이터를 넣는다면, 반드시 어느 한 슬롯에는 두 개 이상의 데이터가 들어감을 이야기한다.

생일의 역설(Birthday Paradox)

사람이 모여 있을 때 그 중 생일이 같은 두 명이 존재할 확률. 비둘기집 원리를 따르면 366명이 모이면 반드시 생일이 같은 두 명이 존재하는 건 알 수 있다. 직관적으로 보면 사람들은 300명 쯤 모이면 높은 확률로 존재할 것 같지만, 틀린 생각이다. 실제로는 57명만 모여도 99% 확률로 생일이 같은 두 명이 존재한다.

공식에 대해서는 위키피디아(링크)에 잘 설명이 되어 있다. 티스토리에서는 수식을 넣기가 너무 불편해서 생략한다.

이 문제를 해시에 대입해보자. 슬롯의 크기에 비해서 데이터의 양이 작다고 하더라도 같은 해시 값을 가지는 키값이 있을 가능성이 매우 높다는 것을 뜻한다.

강력한 해시 함수와 적절한 크기의 슬롯 사이즈는 해시 테이블 자체의 효율을 위해서 필요하지만, 결국 위에서 언급한 두 가지 문제로 인해서 충돌을 무한정 회피하는 것이 답이 아님을 뜻한다. 충돌은 회피하는 것이 아니라 적절히 잘 처리할 문제라는 것이다. 우리는 충돌을 처리하는 방법으로 크게 두 가지를 고려할 수 있다.

1. 충돌이 일어난 항목을 해시 테이블의 다른 위치에 저장
2. 해시 테이블의 하나의 위치에 여러 개 항목을 저장할 수 있게 하는 구조로 설계

이 글에서는 두 번째 방법 중 체이닝(Chaining)에 대해서만 다룰 것이다.

체이닝(Chaining)

첫 번째 방법(선형 조사법 같은 것이 이에 해당한다.)을 사용하는 기존의 구조로는, 해시 주소 하나에는 하나의 슬롯에 존재해 이미 점유된 슬롯을 피해야 했다. 하지만, 두 번째 방식에서는 점유된 슬롯을 피하지 않고, 점유된 슬롯에 어떻게든 자료를 추가하는 방식이며, 체이닝은 연결 리스트를 이용해서 두 번째 방법을 구현한 것 중 하나다.

그림을 보면 어떻게 자료가 추가되는지 알 수 있다. 리스트 자료구조를 공부한 사람이라면 이 그림을 보고 인접 리스트를 떠올렸을 것이다. 인접 리스트와 유사한 구조로 체이닝을 구현할 수 있다.

글의 처음에 나타낸 방법은 해시 주소 하나에 슬롯이 하나만 존재할 수 있어서 충돌을 피하려면 다른 주소의 빈 슬롯을 찾아야 했다. 하지만, 체이닝 기법을 사용하면, 해시 주소 하나에 리스트가 하나씩 배정된다면 리스트에 노드(슬롯)를 연결하는 방식으로 더 이상 다른 주소로 이동할 필요가 없어진 것이다. 

체이닝이 첫 번째 방법에 비해 가지는 장점과 단점에 대해서 간략히 알아보자.

장점

1. 항목을 탐색하거나 저장, 삭제하고자 하면, 계산한 해시 주소에 해당하는 연결 리스트에서 독립적으로 수행하기 때문에, 오버 플로우가 발생해도 수행 시간 면에서 효율적이다.
2. 연결 리스트로 구현하기 때문에 메모리 낭비도 없다.

단점

1. 이 역시 해시 함수의 질적인 수준에 따라서 한 주소에 쏠림 현상이 발생할 수 있다.

여기까지 해시 테이블에 대한 간단한 설명과 구성 과정에서 발생할 수 있는 충돌을 피하는 기법 중 하나인 체이닝에 대한 설명이다. 설명한 내용들을 간단하게 구현한 소스코드를 첨부한다. 체이닝 해시 테이블을 구현했을 때 값들이 들어가는 방식들에 대해 구현한 것으로, 해시 주소를 만드는 키값과 테이블 내에 들어가는 값이 동일하다. 실제로는 테이블 내에 들어가는 값은 이러지 않고 다양한 정보를 담고 있을 것이다.

#include <iostream>
#include <algorithm>
#include <time.h>
#define HASHSIZE 10
using namespace std;
typedef struct Node
{
	int id;
	Node* next = nullptr;
} Node;
int getHashKey(int key)
{
	return key % HASHSIZE;
}
Node* hashTable[HASHSIZE];
void addHashData(int key, Node* node)
{
	int hashKey = getHashKey(key);
	if (hashTable[hashKey] == nullptr)
	{
		hashTable[hashKey] = node;
	}
	else
	{
		node->next = hashTable[hashKey];
		hashTable[hashKey] = node;
	}
}
void deleteHashData(int id)
{
	int hashKey = getHashKey(id);
	if (hashTable[hashKey] == nullptr)
		return;

	Node* deleteNode = nullptr;
	if (hashTable[hashKey]->id == id)
	{
		deleteNode = hashTable[hashKey];
		hashTable[hashKey] = hashTable[hashKey]->next;
	}
	else
	{
		Node* curNode = hashTable[hashKey];
		Node* nextNode = curNode->next;
		while (nextNode != nullptr)
		{
			if (nextNode->id == id)
			{
				curNode->next = nextNode->next;
				deleteNode = nextNode;
				break;
			}
			curNode = nextNode;
			nextNode = curNode->next;
		}
	}
	free(deleteNode);
}
Node* findHashData(int id)
{
	int hashKey = getHashKey(id);
	if (hashTable[hashKey] == nullptr)
		return nullptr;

	if (hashTable[hashKey]->id == id)
	{
		return hashTable[hashKey];
	}
	else
	{
		Node* curNode = hashTable[hashKey];
		while (curNode->next)
		{
			if (curNode->next->id == id)
				return curNode->next;
			curNode = curNode->next;
		}
	}
	return nullptr;
}
void print()
{
	cout << "Simple Hash Table\n";
	for (int i = 0; i < HASHSIZE; i++)
	{
		cout << "idx:" << i << endl;
		if (hashTable[i] != nullptr)
		{
			Node* node = hashTable[i];
			while (node->next)
			{
				cout << node->id << " -> ";
				node = node->next;
			}
			cout << node->id << endl;
		}
	}
	cout << endl;
}
int main()
{
	srand((unsigned)time(NULL));
	int idx[1000] = { 0, };
	for (int i = 0; i < 1000; i++)
	{
		Node* node = new Node;
		node->id = rand() % 10000;
		node->next = nullptr;
		addHashData(node->id, node);
		idx[i] = node->id;
	}
	print();

	for (int i = 0; i < 300; i++)
	{
		deleteHashData(idx[i]);
	}
	print();
}

참고

위키피디아

스택오버플로우

윤성우의 열혈 자료구조

C언어로 쉽게 풀어쓴 자료구조