5-4. 해시 테이블(Hash Table)

0. map vs hash_map (std::unordered_map)

(1) map ( C#의 dictionary와는 다름 )

- 균형 이진 트리의 트리 구조, 레드-블랙 트리로 구성되어 있음

- 키를 기준으로 자동으로 정렬해서 저장

- 시간 복잡도 : O( log N )

 

(2) hash_map (std::unordered_map, C#의 dictionary)

- 메모리를 대가로 속도를 이점으로 가져감

- 삽입 순서에 따라서 저장

- 해시 충돌이 없으면 속도가 map에 비해 굉장히 빠름

- 시간 복잡도 : 데이터의 추가, 탐색, 삭제가 상수의 시간 복잡도를 가짐 => O(1)

 

1. 해시 테이블 ; unordered_map

키-값 쌍으로 이루어져 있으므로 특정 값에 접근하려면 키만 알면 됨.

그러나 키-값 쌍이 많아지면 메모리 용량을 많이 차지함.

 

(1) 테이블(Hash 'Table')

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

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

	// 777번 유저 정보 대입
	users[777] = User{ 777, "Guest" };

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

키를 이용하여 배열에 임의 접근할 수 있다.

 

(2) 해시('Hash' Table)

해시 알고리즘에 따라서 주어진 데이터를 어떤 크기의 값으로 변환 함.

해시 값을 알아도 원래 데이터를 알아낼 수는 없음(해시 알고리즘을 알아내지 못하는 이상).

-> 비밀번호 찾기를 하면 원래 비밀번호를 알려주지 않고 새로운 비밀번호로 바꾸는 이유

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

	// 1000개의 버킷 사용
	vector<User> users;
	users.resize(1000);

	const int userId = 123456789; //123456789번째 유저
	int key = (userId % 1000); // 해시 알고리즘


	// 유저 정보 대입
	users[key] = User{ userId, "Guest" };

	// 유저의 이름 찾기
	User& user = users[key];
	if (user.userId == userId)
	{
		string name = user.username;
		cout << name << endl;
	}
}

 

2. 해시 충돌(Hash Collision)

서로 다른 데이터가 동일한 해시 값을 가질 때(키 중복) 이 두 데이터는 같은 버킷에 담긴다(한 지붕 두 가족?).

이로 인해 데이터 검색, 삽입, 수정의 속도가 저하된다.

 

- 조사법(Probing)

해시 충돌이 발생한 버킷에 수행하는 방법. 다른 빈 버킷을 찾아 데이터를 저장(중복된 데이터를 분리)하려 시도한다.

 

(1) 선형 조사법 (Linear Probing)

충돌이 발생한 버킷의 바로 다음 버킷을 탐색한다. 빈 버킷이 나올 때까지 반복한다.

 

(2) 이차 조사법 (Quadratic Probing)

충돌이 발생한 버킷에서 이차 함수만큼 떨어진 버킷을 탐색한다. 빈 버킷이 나올 때까지 반복한다.

 

- 체이닝(Chaining)

각 버킷을 연결 리스트(혹은 배열)로 관리함.

중복되는 해시 값이 등장하면 연결 리스트(혹은 배열)에 추가하는 방법으로 버킷에 저장.

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

	// 1000개의 버킷 사용
	vector<vector<User>> users;
	users.resize(1000);

	const int userId = 123456789; //123456789번째 유저
	int key = (userId % 1000); // 해시 알고리즘


	//  유저 정보 대입
	users[key].push_back(User{ userId, "Guest" });

	vector<User>& bucket = users[key]; // 각 버킷은 users 이중 배열로 이루어져 있음
    
	// 버킷의 유저들을 각각 대입
	for (User& user : bucket)
	{
		if (user.userId == userId) // 입력된 userId와 일치하면
		{
			string name = user.username; // username 출력
			cout << name << endl;
		}
	}
}

위 코드에서 각 버킷은 users 이중 배열로 되어 있다. users 이중 배열 내의 user 들의 userId를 입력된 userId값과 비교해서 일치하면 username을 출력하게 한다.

 

시간 복잡도 : O( N ), 상수의 시간 복잡도