[자료구조] 해쉬(Hash)

해달e 2023. 8. 1. 05:10

해쉬 자료구조는 키에 대응되는 값을 저장하는 자료구조이다.

Key 값이 특정 인물의 카드 번호라고 가정하고, value 값은 사람 이름이라고 하자. 그래서 특정 카드 번호가 누구의 것인지를 찾고자 한다. 가장 간단하게 쉬운방법으로 구현한다고 한다면, 배열에 모든 데이터를 넣고 탐색을 하는 방법이 있을 것이다. 다만 특정 데이터를 지우는 건 O(N)이고, 특정 카드번호가 누구의 것인지 찾을 때는 배열의 원소를 하나씩 살펴봐야하니 O(N)이 된다.

그런데 해쉬(Hash) 자료구조에서는 insert, erase, find, update 등의 모든 연산이 전부 O(1)이다. 배열에서 인덱스를 가지고 특정 원소를 O(1)에 찾지만, 삽입과 삭제의 경우 O(N)의 시간복잡도를 가진다. 또한 연결 리스트에서는 삽입과 삭제가 O(1)에 가능하지만, 탐색의 경우 O(N)이다. 배열과 연결리스트에서는 특정 연산은 빠르고 특정 연산은 느린 상황이 생기는데, 해쉬에서는 모든게 O(1)로 처리가능하다는 특징이 있다.

        Key                value
3838 2738 1938 2428  ->    Kim
2983 9123 4823 8173  ->    Lee
9023 4938 4932 1234  ->    Park
4245 1239 6472 5842  ->    choi

3838 2738 1938 2428	->	Kim
2983 9123 4823 8173	->	Lee
9023 4938 4932 1234	->	Park
4245 1239 6472 5842	->	Choi

이것이 어떻게 가능한걸까?

16자리 전체를 어떻게 하려고 하지 말고 그냥 뒤의 4자리만 인덱스로 활용하는 것이 훨씬 합리적이다. 이렇게 만들면, insert, erase, find 모두 주어진 카드 번호의 뒷 4자리를 인덱스로 생각하고 대응되는 배열 값을 보고 처리할 수 있기에 전부 O(1)에 처리가 가능하다.

해쉬 자료구조에서는 해쉬 함수라는 것이 쓰이는데, 마치 카드번호 16자리에서 뒷 4자리만 배열의 인덱스로 쓴 것 처럼 임의의 데이터를 고정된 길이의 데이터로 대응시키는 함수이다. 데이터가 16자리가 아닌 24자리거나 9자리여도 똑같이 뒤 4자리만 취하면 되니 임의 길이의 데이터를 고정된 길이의 데이터로 만든다는 개념이 어렵지 않을 것이다.

0000	0001	...	1234	...	2428	...	5842	...	8173
			Park		Kim		Choi		Park

그런데 가만 생각해보면, 문제되는 상황이 있다. 만약 뒤의 4자리가 같은 2개의 다른 카드번호가 있는 경우이다. 이를 충돌이라하고, 가장 큰 애로사항이다. 이것을 잘 처리해주는 것이 해쉬의 성능을 결정하게 된다.

9023 4938 4932 1234

8937 2831 1283 1234

위와 같이 다른 뒤의 4자리가 같은 다른 두 카드번호가 있는 경우이다.

이를 처리하기 위한 방법들이 있다.

1) Chaining

9023 4938 4932 1234

8937 2831 1283 1234

각 인덱스에 연결리스트를 하나씩 둔다. C++기준으로 vector를 두어도 상관없다. 예를들어, Park value가 있는 인덱스 1234에 연결리스트를 활용해서 위처럼 삽입이 됐을 때 해당하는 인덱스의 연결리스트에 값을 추가한다. 삭제도 해당 인덱스를 찾아가서 처리하면 되고, find 및 update도 마찬가지다.

2) Open Addressing

9023 4938 4932 1234 -> Park

8937 2831 1283 1234 -> Ha

0000	0001	...	1234	1235	...	...	2428	...	5842
			Park	Ha			Kim		Choi

(8937 2831 1283 1234, Ha) insert 및 find

이미 해당 인덱스에 데이터가 있는 경우, 다음 번지수에 가서 데이터를 삽입한다. 1235도 이미 있다면, 1236에 삽입한다. 다음으로, find를 생각해보면, 1234번지의 값을 확인해본다. 하지만 카드가 다르다. 따라서 다음 번지를 확인하고, 해당 카드번호를 찾을 수 있다. 만약 카드 번호가 존재하지 않을 경우에는 1234, 1235를 탐색 후 비어있는 인덱스를 발견하게 되고, 따라서 존재하지 않는 카드라는 것을 알 수 있다.

삭제의 경우에는 그냥 값을 날려서 빈 칸을 만들면 안되고, Dummy값을 두어서 해당 칸이 빈 칸이 아니라 원래 값은 있었으나, 제거된 상태임을 명시해주어야만 한다. 따라서 insert를 추후에 할 때 빈 칸이 아니라 dummy가 들어있는 칸을 마주했을 때 정상적으로 삽입이 가능하다.

DATA

Open addressing 방식에서는 Linear Probing 개념이 사용된다. 앞에서 충돌이 발생하면 오른쪽으로 한 칸 이동을 해서 그 칸을 확인했다. Linear Probing은 구현이 간단하면서, Cache hit rate가 높다. 인접한 영역의 배열칸을 확인하기 때문이다. 그러나 단점으로는 Clustering을 꼽을 수 있다. 노란색의 DATA들을 보면, 데이터가 군집되어 있는 것을 알 수 있다. 이렇게 계속해서 cluster의 크기가 1씩 늘어나게되면, 인덱스가 이 군집에 걸렸을 때 빈 칸을 찾을 때 까지 이동 하는 횟수가 늘어나서 성능이 저하된다.

두 번째 방법은 Quadratic Probing이라는 것을 사용하게 되는데.

바킹독님의 슬라이드 참고 - https://blog.encrypted.gg/1009

Quadratic이 제곱을 하는 그런 의미이다. 현 위치 기준으로 1,3,5 칸 씩 이동하는데 처음 위치를 기준으로 생각하면 1의 제곱, 2의 제곱, 3의 제곱 만큼 떨어져있다. 따라서 Quadratic probing이라고 한다.

장점을 먼저 살펴보면 Linear probing이랑 비교했을 때 hit rate가 안좋아지기는 하지만, 그래도 충분히 괜찮고, Clustering도 어느정도 피할 수 있다. 해쉬값이 동일한 상황이 아닐 경우에 가능하다. 그러나 해쉬 값이 동일하다면 계속 똑같은 경로를 따라가기 때문에 여전히 Clustering이 발생할 수 있다.

마지막 방법은 Double Hashing이다. 이는 해쉬 함수를 하나 더 둬서 충돌이 발생할 경우 몇 칸 점프할지 계산한다. 가령, 1234 9293 2832 6789 일 경우, 앞의 4자리를 활용해서 점프 칸 수를 계산하는 방법이 있다. 이는 Clustering을 매우 효율적으로 해결한다. 그러나 hit rate가 극악으로 안 좋아지는 단점이 있다.

이론적으로 해쉬에 대해서 알아봤고, STL에 해쉬도 물론 구현되어 있다.

<unordered_set>

https://cplusplus.com/reference/unordered_set/unordered_set/

value_typethe first template parameter (Key)The same as key_type

cplusplus.com

unordered_set은 집합과 같은 느낌의 STL이다. 데이터를 unordered_set에 추가할 수 있고, 데이터가 unordered_set에 있는지 확인하고, 데이터를 unordered_set에서 지우고 이런 것들을 수행할 수 있다. 선언할 때 자료형도 같이 지정해주어야한다. 중복을 허용하지 않기 때문에 동일한 값을 insert하면 아무일도 생기지 않는다. erase의 경우 해당 값이 안에 있으면 지운 후 1을 반환하고, 그렇지 않으면 0을 반환한다. iterator를 인자로 줄 수도 있다. find함수는 값을 찾아서 iterator를 반환하는 함수다. 만약 값이 없다면, s.end()를 반환한다. size 함수는 말 그대로 들어있는 값의 수이고, count는 수가 몇 개 들어있는지 세는 함수이다. 사실 중복을 허용하지 않기 떄문에 count 함수는 해당 값이 있으면 1이고, 없으면 0이다. 마지막으로 range-based for loop -를 이용해서 값을 출력할 수 있다. 해쉬는 특성상 원소들이 크기 순서나 삽입한 순서로 위치해 있지 않다. 그래서 출력해보면 순서가 뒤죽박죽이다.

void unordered_set_example(){
    unordered_set<int> s;
    s.insert(-10); 
    s.insert(100); 
    s.insert(15);
    s.insert(-10); // 중복이기 때문에 변화 X
    cout << s.erase(100) << '\n'; // 1 반환
    cout << s.erase(20) << '\n'; // 0 반환
    if(s.find(15) != s.end()) cout << "15 in s\n";
    else cout << "15 not in s\n";
    cout << s.size() << '\n';
    cout << s.count(50) << '\n';
    for(auto e : s) cout << e << ' ';
    cout << '\n';
}

<unordered_multiset>

https://cplusplus.com/reference/unordered_set/unordered_multiset/

value_typethe first template parameter (Key)The same as key_type

cplusplus.com

다음은 unordered_multiset이다. set이랑 거의 똑같은데 원소의 중복이 허용된다.

이미 존재하는 원소를 insert해도 multiset에 추가가 된다. erase의 경우 해당 원소를 set에서 모두 지운다. 하나만 지우고 싶다면, ms.find(-10)을 통해서 -10이 들어있는 iterator를 erase의 인자로 넘겨줘서 하나만 지울 수 있다. count 함수는 O(원소의 개수)만큼의 시간복잡도를 가지는 것도 주의하자.

void unordered_multiset_example(){
    unordered_multiset<int> ms;
    ms.insert(-10);
    ms.insert(100);
    ms.insert(15); // {-10, 100, 15}
    ms.insert(-10); 
    ms.insert(15); // {-10, -10, 100, 15, 15}
    for(auto e : ms) cout << e  << ' ';
    cout << '\n';
    cout << ms.erase(15) << '\n'; // {-10, -10, 100}, 2
    ms.erase(ms.find(-10)); // {-10, 100}
    ms.insert(100); // {-10, 100, 100}
    cout << ms.count(100) << '\n'; // 2
}

<unordered_map>

https://cplusplus.com/reference/unordered_map/unordered_map/

1234 unordered_map ::iterator it; (*it).first; // the key value (of type Key) (*it).second; // the mapped value (of type T) (*it); // the "element value" (of type pair )

cplusplus.com

마지막으로 unordered_map이다. 처음 선언할 때 키의 자료형과 값의 자료형을 명시한다. 보면 확인할 수 있겠지만, 중복허용이 되지않는다. multimap은 중복허용이 가능한데, 거의 사용할 일이 없어 전혀 사용하지 않는다.

void unordered_map_example(){
    unorederd_map<string, int> m;
    m["hi"] = 123;
    m["bkd"] = 1000;
    m["gogo"] = 165; // ("hi", 123), ("bkd",1000), ("gogo", 165)
    cout << m.size() << '\n'; // 3
    m["hi"] = -7; // ("hi", -7), ("bkd",1000), ("gogo", 165) -> 중복허용X
    if(m.find("hi") != m.end()) cout << "hi in m\n";
    else cout << "hi not in m\n";
    m.erase("bkd"); // ("hi", 123), ("gogo", 165)
    for(auto e : m){
        cout << e.first << ' ' << e.second << '\n';
    }
}

바킹독님의 실전 알고리즘 글을 참고했습니다.