해시 테이블

map  vs hash_map (C++ 표준 unordered_map)

 

- map

Red-Black Tree 

추가, 탐색, 삭제 O(logN)

정렬되어있음

 

- hash_map(unordered_map)

추가, 탐색, 삭제 O(1) 

충돌만 하지 않고 잘 동작하면 map보다 빠른 시간에 동작

원하는 키 값을 빠르게 찾아주는데 최적화 되어 있음

 

- 메모리를 내주고 속도를 취한다

 

ex. 1-999 user (userId = 1~999)

       [1][2][3][ ][ ][ ][999]

 

해시 테이블

 

'테이블'

키를 알면, 데이터를 단번에 찾을 수 있음

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

	vector<User> users;
	users.resize(1000);
	
	//777번 유저 정보 세팅
	users[777] = User{ 777,"Jinny" };

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

	cout << name << endl;

	//테이블
	//키를 알면, 데이터를 단번에 찾을 수 있다.
}

 

 

 

테이블을 실전에서 쓸 수 있나?

 

int32_max(3억~)

3억개 할당할 수 없다. 

메모리도 무한은 아니니까!

 

 

 

'해시'

 

ex. 보안

id : Jinny + pw: qwer1234

DB : [Jinny][1234]

 

이대로 DB에 id와 pw를 저장하면 보안에 문제가 있음

그래서 hash함수로 감싸줌

 

id : Jinny + pw: hash(qwer1234) -> sdjkfhakjh1234

DB : [Jinny][sdjkfhakjh1234]

 

이렇게 되면 해커가 해쉬함수로 변환된 sdjkfhakjh1234를 가지고 qwer1234를 알아낼 수 없다.

hash: 일방향

qwer1234를 알면 hash를 씌워서 -> sdjkfhakjh1234 알아내는데 반대는 못함

 

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,"Jinny" };

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

 

해시를 실전에서 쓸 수 있나?

- 충돌이 일어남!!

 

ex. 123456789 vs 789 : 동일한 키가 나올 수 있음

 

어떻게 해결?

충돌이 발생한 자리를 대신해서 다른 빈자리를 찾아 나서면 된다

 

ex.

선형 조사법(linear probing)

hash(key)+1 -> hash(key)+2

이차 조사법(quadratic probing)

hash(key)+1^2 -> hash(key)+2^2

 

 

데이터가 엄청 많으면?

체이닝

 

ex. 동일한 키 값이 있으면 연이어서 데이터를 만듦

          [ ]  (new)

[ ][ ][ ][ ][ ][ ][ ]  

 

void TestHashTableChaning()
{
	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,"Jinny"});
	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;
		}
		
	}
}

 

요약

map vs hash_map?

map은 Red-Black Tree로 만들어져있어서 트리 구조로 관리를 하고 데이터가 추가/삭제되면 이진 트리를 유지하지만 균형을 맞춰줘서 한쪽으로 쏠리는 것을 예방함

시간 복잡도는 O(logN)

근데 속도는 hash_map이 빠르다. hash_map은 메모리를 내주고 속도를 취하기 때문에. 

단, 충돌이 일어나지 않는다는 가정 하에만 hash_map이 빠름

 

차이를 꼭 알고 있기. 설명할 수 있을 정도로!

 

 

 

참고:

인프런 Rookiss - [C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part3: 자료구조와 알고리즘

https://www.inflearn.com/course/%EC%96%B8%EB%A6%AC%EC%96%BC-3d-mmorpg-3/dashboard