map vs hash map

map

• red black tree (이진 균형 트리) 구조
• 추가/탐색/삭제 : O(logN)
• 코드

#include <map>
using namespace std;

int main()
{
	map<int, string> m;
    m.insert({100, "Kim"});
    m.insert({200, "Jun"});
    m.insert({100, "Lee"});
    
    //중복된 값을 쓰고 싶으면, multimap 써야함
    cout << m[100] <<" \n"; //Kim
    m[100] = "Leem"; //value값 덮어쓴다.
    cout << m[100] << "\n"; //Leem
}

hash map

• C++ STL에서 unordered_map
• C#에서는 dictionary
• 추가/탐색/삭제 : O(1)
  • 메모리를 더 많이 쓰는 대신 속도가 빠르다.
• 코드
  unorderd_map<key, value>
unordered_multimap<key, value>
  • unordered_multimap에서는 [] operator 사용 불가능
  • insert 로 값 넣기
• unordered_map을 순회해서 값을 찾고 싶을때

auto u = um.equal_range(cur);
for(auto it = u.first; it != u.second; ++it)
{
	cout<<it->second<<"\n";
}

cf) hash table

• table
  • O(1)에 추가/탐색/삭제를 할 수 있는 구조
  • 키와 데이터의 쌍으로 구성
  • 그러나 데이터가 너무 커지면, 더이상 효율성이 사라짐
  • 이 문제를 해결하기 위해 hash 사용
• hash
  • 키에 따라 데이터를 넣을 때 충돌된 것을 해결해주는 방법
  • 충돌 방지 기법
    • 선형 조사법
      • 이미 있는 key 값이라면, 한칸 뒤로 밀면서 빈 key값 찾기
    • 이차 조사법
      • 이미 있는 key 값이라면, 제곱값 만큼 밀면서 빈 key값 찾기
    • 체이닝 기법
      • 이미 있는 key 값이라면, 중복된 key값을 가지는 value 넣어주기
• hash 예시 코드

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

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

	const int userId = 123456789;
	int key = (userId % 1000); //hash 함수를 통해 만든 key

	//정보 넣기
	users[key] = User{ userId, "Leem" };

	//정보 찾기
	User& user = users[key];
	if (user.userId == userId)
	{
		string name = user.username;
		cout << name << "\n";
	}  
}

• 체이닝 예시 코드

void TestHashTableChaining()
{
	struct User
	{
		int userId = 0;
		string username;
	};

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

	const int userId = 123456789;
	int key = (userId % 1000); //hash 함수를 통해 만든 key

	//정보 넣기
	users[key].push_back(User{ userId, "Leem" });
	users[key].push_back(User{ 789, "Jun" });


	//정보 찾기
	vector<User>& bucket = users[key];
	for (const auto& user : bucket)
	{
		if (user.userId == userId)
		{
			string name = user.username;
			cout << name << "\n";
		}
	}
}

참고) unordered_map에서 key값으로 pair를 쓰고 싶을 때

struct pair_hash
{
	template<class T1, class T2>
    size_t operator () (const pair<T1,T2>&pair) const
    {
    	auto hash1 = hash<T1>{}(pair.first);
        auto hash2 = hash<T2>{}(pair.second);
        return hash1^hash2;        
    }
}

unordered_map<pair<string, string>, int, pair_hash> um;