[C++ 자/알 Note] 해시테이블

해시테이블

배열이나 리스트는 탐색이 매우 느리다

반면, 탐색이 빠른 자료구조는 이진탐색트리가 있다

이진탐색트리보다 더 빠른 자료구조가 바로 해시테이블이다

탐색뿐 아니라 삽입/삭제/탐색 모두 O(1) 소모된다

하지만, 그만큼 공간을 많이 차지한다는 것이 단점이다

 

테이블 개념

해시테이블을 알아보기 전 테이블과 해시 개념을 천천히 알아보자

테이블이란 아파트의 우편함과 같다

비록 공간을 많이 차지하지만, 삽입/삭제/탐색이 빠르다

 

예를 들어, 아래의 코드처럼

vector의 임의접근을 활용한다면

userId를 통해 쉽게 탐색을 할 수 있다

그러나, 문제는 유저수가 많으면 많을수록 공간을 너무 많이 차지한다는 것이다  

void TestTable()
{
	struct User
	{
		int userId = 0; // 1~999
		string username;
	};

	vector<User> users;
	users.resize(1000);

	// 777번 유저 정보 세팅
	users[777] = User{ 777, "Chovy" };

	// 777번 유저 이름은?
	string name = users[777].username;
	cout << name << endl;
}

 

해시 개념

위에서 본 것처럼 테이블 개념을 이용했을 때

공간을 너무 많이 차지한다는 것이 문제였다

이를 해결하기 위해서 key를 해시함수를 거쳐 사용하면 된다

 

예를 들어, 아래의 코드처럼

hash 함수를 이용해서 key를 저장 및 탐색하면 된다

이렇게 하면, 유저수가 많아지더라도 계속 resize를 해줄 필요가 없고

공간을 덜 소모하게 된다

그러나, 중복된 key가 발생하는 경우 충돌이 발생하는 것이 문제이다

void TestHash()
{
	struct User
	{
		int userId = 0; // 1~int32_max
		string username;
	};

	vector<User> users;
	users.resize(1000);
	
	const int userId = 123456789;
	int key = (userId % 1000); // hash < 고유번호

	// 123456789번 유저 정보 세팅
	users[key] = User{ userId, "Chovy" };

	// 123456789번 유저 이름은?
	User& user = users[key];
	if (user.userId == userId)
	{
		string name = user.username;
		cout << name << endl;
	}
}

 

해시테이블 체이닝 개념

위에서 본 것 처럼 해시테이블을 이용하는 경우 문제가 있었다

중복된 key가 발생하는 경우 충돌이 발생한다는 것이다

이를 해결하는 방법은 개방주소법과 체이닝이 있다

 

개방주소법(Open Addressing)

- 선형 조사법 (Linear Probing)

충돌이 발생한 위치에서 일정한 간격(보통 +1)으로 다음 슬롯을 순차적으로 검사 및 추가

ex. hash(key)+1, hash(key)+2,...
- 이차 조사법 (Quadratic Probing)

충돌이 발생한 위치에서 제곱수 간격으로 다음 슬롯을 검사 및 추가

ex. hash(key)+1^2, hash(key)+2^2,...
- 이중 해싱 (Double Hashing)

두 개의 해시 함수를 사용하여 충돌이 발생했을 때 다른 간격으로 다음 슬롯을 검사 및 추가

이중 해싱뿐 아니라 다중 해싱도 가능

 

장점: 추가적인 메모리 오버헤드가 적다
단점: 클러스터링(데이터가 특정 영역에 집중되는 현상)이 발생해 성능 저하를 유발할 수 있다

체이닝(Chaining)
각 해시 테이블 슬롯에 vector나 list와 같은 다른 자료구조를 사용해

충돌이 발생한 데이터를 저장하는 방식이다

 

장점: 클러스터링 문제가 적고, 삭제 연산이 간단하다
단점: 추가적인 메모리 오버헤드가 발생한다

 

체이닝을 사용하는 예시는 아래와 같다

void TestHashTableChaining()
{
	struct User
	{
		int userId = 0; // 1~int32_max
		string username;
	};

	vector<vector<User>> users;
	users.resize(1000);

	const int userId = 123456789;
	int key = (userId % 1000); // hash < 고유번호

	// 123456789번 유저 정보 세팅
	users[key].push_back(User{ userId, "Chovy" });
	users[789].push_back(User{ 789, "Faker" });

	// 123456789번 유저 이름은?
	vector<User>& bucket = users[key];
	for (User& user : bucket)
	{
		if (user.userId == userId)
		{
			string name = user.username;
			cout << name << endl;
		}
	}
}