[자료구조] 해시 테이블 (2)

<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>

---

충돌 해결

체이닝(Chaining)

　해시 충돌 문제를 해결하는 첫 번째 방법인 체이닝 기법에서는 충돌이 발생한 지점에서 연결 리스트를 만든다. 즉, 이 방법은 해시 테이블의 특정 위치에서 하나의 연결 리스트를 저장하여, 충돌이 발생하면 리스트의 맨 뒤에 새로운 키를 추가하는 방식이다. 

 

　연결 리스트는 포인터를 이용하여 다음 노드를 가리키기 때문에, 메모리를 재사용하지 않아 중간에 요소를 삽입하거나 삭제하는 경우에도 O(1) 시간에 수행할 수 있다는 장점이 있다. 그리고 배열과 다르게 데이터가 흩어져 있지 않고 연속된 메모리 공간을 차지하지 않으므로, 캐시 효율성이 높다.

 

　이러한 체이닝 기법을 이용하여 이전 충돌 문제를 해결해 보자.

 

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

class hash_table
{
	std::vector<std::list<int>> _hash;

public:
	hash_table(size_t n)
	{
		_hash.resize(n);
	}

　vector의 자료형으로 list를 받고, 생성자를 이용해 초기화한다.

 

	void insert(unsigned int value)
	{
		_hash[value % _hash.size()].push_back(value);
		std::cout << "Input the " << value << " in hash table.\n";
	}

　삽입 함수 insert()를 구현한다. 동일한 키가 들어왔을 때 push_back()을 통해 리스트 형식으로 저장한다.

 

	void lookUp(unsigned int value)
	{
		auto& buckets = _hash[value % _hash.size()];
		auto it = std::find(buckets.begin(), buckets.end(), value);

		if (it != buckets.end())
			std::cout << "Find the " << value << " in hash table.\n";
		else
			std::cout << "Can't find the " << value << " in hash table.\n";
	}

　원소를 찾는 lookUp() 함수다. _hash에 존재하는 버킷들을 초기화한 후, 해당 키에 값이 있는지 find() 함수로 찾는다. 이때 버킷(bucket)이란 해시 테이블의 한 셀 또는 한 셀에 연결되어 있는 하나의 연결 리스트를 의미한다.

 

	void erase(unsigned int value)
	{
		auto& buckets = _hash[value % _hash.size()];
		auto it = std::find(buckets.begin(), buckets.end(), value);

		if (it != buckets.end())
		{
			buckets.erase(it);
			std::cout << "Erase the " << value << " in hash table.\n";
		}
	}
};

　값을 지우는 erase() 함수다. _hash에 존재하는 버킷들을 불러온 후, 해당 키에 값이 있으면 erase() 함수를 통해 값을 지운다.

 

int main()
{
	hash_table hash(7);

	hash.insert(2);
	hash.insert(25);
	hash.insert(10);

	hash.lookUp(25);

	hash.insert(100);
	hash.lookUp(100);
	hash.lookUp(2);

	hash.erase(25);
}

　main() 함수에서 작동시키면, 전에 했던 모듈로 함수와는 다르게 해결할 수 있다는 것을 확인할 수 있다.

 

실행 결과

 

　이 과정을 그림으로 표현하면 다음과 같다.

 

 

총합본

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>

class hash_table
{
	std::vector<std::list<int>> _hash;

public:
	hash_table(size_t n)
	{
		_hash.resize(n);
	}

	void insert(unsigned int value)
	{
		_hash[value % _hash.size()].push_back(value);
		std::cout << "Input the " << value << " in hash table.\n";
	}

	void lookUp(unsigned int value)
	{
		auto& buckets = _hash[value % _hash.size()];
		auto it = std::find(buckets.begin(), buckets.end(), value);

		if (it != buckets.end())
			std::cout << "Find the " << value << " in hash table.\n";
		else
			std::cout << "Can't find the " << value << " in hash table.\n";
	}

	void erase(unsigned int value)
	{
		auto& buckets = _hash[value % _hash.size()];
		auto it = std::find(buckets.begin(), buckets.end(), value);

		if (it != buckets.end())
		{
			buckets.erase(it);
			std::cout << "Erase the " << value << " in hash table.\n";
		}
	}
};

int main()
{
	hash_table hash(7);

	hash.insert(2);
	hash.insert(25);
	hash.insert(10);

	hash.lookUp(25);

	hash.insert(100);
	hash.lookUp(100);
	hash.lookUp(2);

	hash.erase(25);
}

 

　이때 속도는 해시 테이블에서 각각의 리스트에 저장되는 키의 평균 개수를 의미하는 부하율(load factor)에 의해 결정된다. 

• 부하율 = 전체 키 개수 / 해시 테이블 크기

　만약 해시 테이블의 크기가 key의 개수보다 월등히 많다면, 실제 데이터가 듬성듬성 존재하게 되므로 메모리 낭비가 발생한다. 반대로 key의 개수가 해시 테이블의 크기보다 월등히 많다면, 충돌이 많이 발생하게 되어 리스트가가 길어진다. 

　따라서 부하율을 1에 가깝게(O(1)) 하는 것이 가장 최적화하는 것이라고 할 수 있다. 이렇게 부하율을 1 근방으로 조절하는 것을 재해싱(rehashing)이라고 한다.

---

열린 주소 지정

　열린 주소 지정(open addressing)은 모든 원소를 해시 테이블 내부에 저장하는 방식이다. 즉, 충돌이 발생하면 해시 함수를 재호출하여 다른 주소를 탐색한다. 이 기법은 데이터 개수가 해시 테이블 크기보다 크다면 모든 자료들이 테이블에 들어가지 않기 때문에, 해시 테이블의 크기가 반드시 데이터 개수보다 커야 한다. 이때 다른 주소를 탐색하는 방법에는 여러 가지가 존재한다.

 

선형 탐색(Linear probing)

　선형 탐색 방법은 해시 충돌이 발생했을 때 다음 셀 위치로 선형적으로 이동하면서 비어있는 셀을 찾는 방법이다. 이 기법은 해시 테이블의 모든 셀을 탐색할 필요 없이 해시 충돌이 발생한 지점으로부터 일정한 간격으로 이동하며 탐색을 수행한다. 이는 가장 간단한 탐색 방법으로서, hash(x)에 해당하는 셀이 이미 채워져 있다면 hash(x+1)의 위치로 이동해 셀을 확인한다.

 

　데이터가 특정 위치에 군집화(clustering)되는 경우, 즉 특정 해시 값이 너무 자주 발생해서 데이터가 몇 개의 그룹으로 뭉치는 형태로 저장되면 성능이 크게 저하된다. 예를 들어, 해시 함수에서 반환한 위치가 큰 군집의 시작 위치를 가리킨다면, 클러스터의 맨 마지막 위치까지 선형 검색을 하게 되어 검색 속도가 크게 느려질 것이다. 또한 해시 테이블이 가득 찼다면, 재해싱이 이뤄지지 않는 한 값을 삽입할 수 없다는 단점이 있다.

 

이차함수 탐색(Quadratic probing)

　이차 방정식을 사용하여 탐색을 수행하는 것을 이차함수 탐색이라고 한다. 이 방법은 해시 충돌이 발생한 지점에서 일정한 간격을 두고 이차 함수의 형태로 이동하면서 비어있는 셀을 찾는 방법이다. 예를 들어, hash(x)의 위치에 셀이 이미 채워져 있다면, hash(x) → hash(x+1) → hash(x+2^2) ... 으로 이동하며 셀을 확인한다. 이렇게 하면 군집이 나타날 확률을 줄일 수 있다.

 

　그러나 이차함수 탐색에서도 군집화가 발생할 수 있다. 예를 들어, 해시 함수의 반환 값이 일정 구간 내에서만 변동하게 되면, 이차함수 탐색을 이용하여도 동일한 위치에 데이터가 쌓일 수 있다. 또한 선형 탐색과 마찬가지로 해시 테이블이 가득 찼다면, 재해싱 없인 값을 삽입할 수 없다. 

 

　앞서 설명한 방식들은 모두 원소 위치가 기존에 삽입되어 있는 다른 원소들에 의해 영향을 받는다. 이는 기존에 저장되어 있던 원소는 새로 삽입하는 원소와 서로 다른 해시 값을 가지는 문제가 발생할 수 있다는 것을 의미한다. 

 

뻐꾸기 해싱(Cuckoo hashing)

　뻐꾸기 해싱은 크기가 같은 두 개의 해시 테이블을 사용하고, 각각의 해시 테이블은 서로 다른 해시 함수를 갖게 하는 기법이다. 완벽한 해싱 기법 중 하나로서, 구현만 제대로 한다면 O(1)의 시간 복잡도를 보장한다. 

 

　뻐꾸기 해싱의 핵심은 순환(cycle)을 일으키지 않게 하는 것이다. 이때 순환이란 방문하는 위치가 반복되는 것을 의미한다. 예를 들어, 테이블에 10이 옮겨가야 할 위치에 다른 원소 5가 있고, 5를 옮기다 보니 다시 10을 방문하는 것이다. 이러한 순환이 발생한다면 무한 루프에 빠질 수 있게 되므로 새로운 해시 함수를 이용해 재해싱을 해야 한다. 

 

　이 기법의 특징을 간략하게 정리하고, 다음 시간엔 뻐꾸기 해싱을 구현하는 시간을 가져보도록 하겠다.

• 원소가 두 해시 테이블 중 어디든 저장될 수 있음
• 원소가 나중에 다른 위치로 이동할 수 있음
• 룩업의 시간 복잡도는 저장 가능한 위치 두 군데만 확인해 보면 되므로 O(1) 
• 삽입 연산의 시간 복잡도는 O(1)이지만, 완전히 비어 있는 셀이 나타낼 때까지 재귀적으로 반복하므로 O(1) 보다 느릴 수 있음