[C++] Hash Table

[ Hash Table ]

 

Key를 알면, 데이터를 단번에 찾을 수 있는 자료구조

탐색에 상수시간, O(1)이 소요된다.

메모리를 내주고 대신 빠른 시간을 얻는 방식

 

[ Table ]

우선 테이블은, 예를 들어 UserId 같은 것을 인덱스로해서 버킷(bucket)에 접근, 데이터를 얻을 수 있음

하지만 만약, 게임내의 유저 수가 몇백만명을 넘어가는 상황이라면 어떻게 해야할까? 메모리가 터질 수도 있을 것이다.

→ 여기에 해시를 추가해서 사용해보자.

 

[ Hash ]

userId를 인덱스로 써서 직접적으로 접근하는게 아닌, 해시함수를 통해서 한 번 변환된 걸 Key값으로 사용해서 접근.

 

Example) 보안

DB에 있는 유저 아이디에 대한 비밀번호의 경우 평문을 그대로 넣지 않고 해시값을 저장함.

비밀번호를 통해 해시값이 일치하는지는 확인할 수 있지만, 역으로 해시값으로 비밀번호를 얻을 수는 없음.

→ 웹사이트에서 비밀번호 찾기를 한다면 비밀번호를 알려주는게 아니라 변경할 새 비밀번호를 입력하세요라고 뜨는 이유가 이것 때문이다. (개발자, 운영자도 실제 비밀번호를 직접적으로 알 수 없게 해서 만약 DB 정보가 탈취되더라도 비밀번호를 알 수 없음)

 

[ Hash Table ]

테이블로 관리를 하되, 해시값을 추출해서 key값을 어디에 활용할지 고르기 때문에 합쳐져서 용어가 사용되는 것.

문제점) 해시 충돌 문제

해시 변환 알고리즘이 단순하다면 중복이 생길 수 있다.

 

다양한 해결방법

 

1) 아이디는 길지만 실제 사용할 데이터 수가 적을 때

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

i) 선형 조사법 (Linear Probing)

중복된 해시에서 +1, +2... 해서 빈 자리를 찾음

ii) 이차 조사법 (Quadratic Probing)

단순히 +1, +2...를 하면 몰릴 확률이 높으니 +1^2, +2^3 등으로 조금 더 분산시켜서 저장한다.

 

2) 데이터의 수가 정말 많을 때 (몇십, 몇백만 이상)

i) 체이닝

버킷에 애초에 바로 데이터를 추가하는 것이 아니라, 처음에 vector나 list를 추가한 뒤에

중복된 칸에 세로로 더 늘려서 추가한다. (2차원 형태를 띄게 되는 것)

이 방식은 굳이 선형 조사법 등 피해서 저장할 필요가 없어짐

ex)
users[key] = User{ userId, "Alice" }; 가 아니라

users[key].push_back(User{ userId, "Alice"}); 이렇게 사용

 

데이터 접근

void TestHashTableChaining()
{
    struct User
    {
        int userId = 0;
        string username;
    };
 
    vector<vector<User>> users;
    users.resize(1000);
 
    const int userId = 123456789;
    int key = { userId % 1000 };
 
    users[key].push_back(User{ userId, "Alice" });
 
    vector<User>& bucket = users[key];
    for (User& user : bucket)
    {
        if (user.userId == userId)
        {
            string name = user.username;
            cout << name << "\n";
        }
    }
}

 

[ 중요한 사실 ]

해시 충돌 문제를 해결하기 위한 다양한 알고리즘을 다 알아보는 것이 중요한게 아니라, 프로그래머의 관점에서 생각해보자면

1) 테이블을 사용해서 빠르게 접근하고 데이터를 꺼내고 저장하는게 중요하다.

2) 해시라는 것 자체는 고유 Key값을 이용해서 어떤 버킷을 사용할지를 정하는 것이다.

 

이 두 가지 위주의 관점에서 생각해야 한다.

map과 hash map은 둘 다 굉장히 자주 사용하는 컨테이너들인데, 각 컨테이너의 장점과 단점, 차이점을 정확히 이해하지 못한다면 실제 프로그래밍을 할 때 적절한 자료구조를 선택하지 못해 문제가 생길 수 있기 때문이다.

 

map과 hash map의 차이 (C++11 : map vs unordered_map)

[ map ]

map은 자가 균형 이진 탐색 트리의 일종인 Red-Black Tree로 이루어져 있어 트리 구조로 관리한다.

데이터가 추가되거나 삭제되면 이진 탐색 트리 형태를 유지하고, 한쪽으로 극단적으로 쏠린다면 시간복잡도가 리스트와 차이 없어지기 때문에 균형을 스스로 맞춰 한쪽으로 쏠리는걸 예방하는 형태로 되어 있다.
추가/탐색/삭제의 시간복잡도가 O(logN)에 해당한다. 또한 Key값을 기준으로 정렬되어 있다.

그리고 각 노드들이 Heap 할당이기 때문에 random memory access가 자주 일어나고, O(logN)이어도 균형을 맞춰주기 위한 추가적인 작업들이 많고 무겁기 때문에 overhead가 발생해 상당히 느리다.

 

[ hash map ]

속도적인 측면에서 보면 hash map이 훨씬 더 빠르다.

메모리를 내주고 속도를 얻는 방법이기 때문에 해시 충돌이 일어나지 않는다고 가정하면 해시맵이 훨씬 더 빠르다.

Key값을 기준으로하는 정렬이 필요 없다면, 해시맵을 사용하고 O(1)의 시간복잡도의 이점을 얻을 수 있다.

 

// 추가 //

해시맵은 Key에 대응되는 Value를 저장하는 자료구조입니다.

가장 큰 특징은, insert, erase, find, update가 전부 O(1)이라는 것.

Key의 경우의수가 매우 크다면, 단순하게 저장하려면 크기가 매우커져 현실적으로 불가능함.

그래서, 일부만 구분하여 인덱스로 활용.

해시 함수 : 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수.

해시 함수로 변환해서, 테이블로 관리하는 것을 Hash Table이라고 함.

 

*충돌

충돌을 처리하는 것이 해시의 성능에 가장 큰 영향.

0000 0000 0000 5135와 9999 9999 9999 5135는 기본적으로 동일하게 변환되는데, 이것을  구분하는 것이 문제.

→ 충돌이 발생하는 것.

 

[ 충돌 회피1 - Chaining ]

각 인덱스마다 list or vector를 삽입. 2차원으로 관리하게 되는 것.

이상적인 상황 : O(1)

최악의 상황 : O(N)

STL이 이 방식 사용.

 

[ 충돌 회피2 - Open Addresing ]

충돌이 된다면, 다음 칸으로 가는 것.

이 방식의 가장 큰 문제는, 대체하는 자리를 찾아서 거기에 저장하기 때문에, 원래의 해시값이 저장된 곳이 삭제되었다고 빈 자리로 놔둔다면, 다음에는 해당 빈 자리가 비어있다고 생각하여 대체된 자리에 있는 값을 못찾을 수도 있음.

→ 제거된 상태임을 명시해야 하므로, 더미값을 넣어줘야 함.

특정 해시값이 퍼지지않고 뭉치게 됨.

1) Linear Probing

+1, +2, +3... 으로 가서 저장.

장점 : Cache hit rate가 높다.

단점 : Clustering이 생겨 성능에 영향을 줄 수 있다. (Cluster가 커질수록 연산이 오래걸려 성능을 저하시키는 것.)

 

2) Quadratic Probing

^2+1, ^3+1 ... 으로 가서 저장.

장점 : Cache hit rate가 나쁘지 않다, Clustering을 어느 정도 회피할 수 있다.

단점 : 해시 값이 같을 경우 여전히 Clustering이 발생한다. (경로는 동일하므로)

 

3) Double Hashing

충돌 발생시 이동할 칸의 수를 새로운 해시 함수로 다시 계산하는 방식.

이전에 뒷 4자리만으로 변환했다면, 이번엔 앞 4자리로 변환하는 것.

장점 : Clustering을 효과적으로 피할 수 있음.

단점 : Cache hit rate가 극악으로 안좋아짐.

 

 

 

[ Reference : Rookiss의 C++ 자료구조 Part3, https://stackoverflow.com/questions/1822114/c-map-insertion-and-lookup-performance-and-storage-overhead , 바킹독님 해시맵 강의 ]