해시 테이블에 관하여
많이 나오는 질문 map vs hash_map(C++11 표준 unordered_map)
map : 레드블랙트리.
균형 이진 트리로 만들어져 트리 구조로 관리가 된다.
그리고 균형을 맞추기 위해 트리의 한 계층으로 쏠리는 것을 방지하기 위한 조건과 알고리즘이 적용되어 있다.
삽입/삭제/탐색 의 시간복잡도가 O(logN) 이다.
그런데 시간복잡도 상의 더 빠른 자료구조는 hash_map 이다.
해쉬 맵은 메모리를 더 많이 사용하여 속도를 취하는 방식이다.
다만, 충돌이 너무 많이 일어나지 않는다는 가정하에 해쉬 맵이 더 빠르다.
충돌이 일어나면 다른 자리를 찾거나 체이닝 등에 의해 시간이 할애되기 때문이다. 충돌이 적다는 가정하에 hash_map 의 삽입/삭제/탐색의 시간복잡도는 O(1) 로 가장 빠른 수준의 자료구조이다.
map : Red-Black Tree
- 추가/탐색/삭제 O(lonN)
hash_map (unordered_map)
- 추가/탐색/삭제 O(1) 조건부긴함 조건을 이해하는게 중요하다
메모리를 내주고 속도를 취한다.
아파트 우편함 [1][2][3][4][5][6][7] 각자 자신의 우편함이 있다면 나의 우편함만 보면 된다. 메모리 제한 없이 사용 가능할 시 효율 최고 수준이다.
원하는 정보의 갯수만큼 배열을 만들고 정보를 가져올 때 그냥 해당 배열의 인덱스로 바로 접근
'해시' '테이블' 키 를 알고 있으면 해당 키를 인덱스로 해서 정보 접근을 상수로 접근한다. 이렇게 테이브로만 관리하면 메모리 부족하다. 해시 기능도 같이 사용한다.
일반 테이블 코드
void TestTable()
{
struct User
{
int userId = 0;
string username;
};
vector<User> users;
users.resize(1000);
// 100 번 째 유저 정보
users[100] = User{ 100, "one" };
cout << users[100].username << endl;
}
해쉬 테이블 코드
void TestHash()
{
struct User
{
int userId = 0; // 1~3억!
string username;
};
vector<User> users;
users.resize(1000);
const int userId = 12345678; // userId 가 1000 을 넘어섰다! 저장이 될까?
int key = (userId % 1000); // 해쉬 추출 알고리즘 hash < 고유번호를 가져오는 것.
// 해당 해쉬 추출 알고리즘은 다양함
// 100 번 째 유저 정보
users[key] = User{ userId, "one" };
if (users[key].userId == userId)
{
cout << users[key].username << endl;
}
// 충돌 문제가 있다. key 값이 중복 될 수 있다.
// 충돌이 발생한 자리를 대신해서 다른 빈자리를 찾아나서면 된다.
// - 선형 조사법
// hash(key) + 1 -> hash(key) + 2 자리 찾기
// - 이차 조사법
// hash(key) +1^2 -> hash(key) + 2^2 자리 찾기
// 체이닝
// 약간 이중 배열 느낌처럼 하나의 인덱스에 여러 키 값을 넣는 것
}
충돌 문제가 있다. key 값이 중복 될 수 있다. 충돌이 발생한 자리를 대신해서 다른 빈자리를 찾아나서면 된다.
- 선형 조사법 hash(key) + 1 -> hash(key) + 2 자리 찾기
- 이차 조사법 hash(key) +1^2 -> hash(key) + 2^2 자리 찾기
체이닝
약간 이중 배열 느낌처럼 하나의 인덱스에 여러 키 값을 넣는 것
// O(1) 상수의 시간복잡도
// 메모리를 엄청 쓴다. 정렬하는건 아님
void TestHashTableChaining()
{
struct User
{
int userId = 0; // 1~3억!
string username;
};
vector<vector<User>> users;
users.resize(1000);
const int userId = 12345678;
int key = (userId % 1000);
users[key].push_back(User{ userId, "one" });
users[678].push_back(User{ 1234, "1234" });
// 유저 찾기
vector<User>& user = users[key];
for (auto u : user)
{
if (u.userId == userId)
{
cout << u.username << endl;
}
}
}