[해시(Hash)] STL 제공 해시 함수 객체: std::hash 및 해시 컨테이너: std::unordered_map/set

reference: "전문가를 위한 C++" / 마크 그레고리

std::hash 템플릿 함수 객체

• C++는 문자열을 비롯해 모든 기본 데이터 타입에 대한 해시 값을 생성하는 기능을 제공
• 객체 내부에 해시 함수 알고리즘이 구현

reference: https://www.delftstack.com/ko/howto/cpp/hash-in-cpp/

#include <iostream>
#include <iomanip>
#include <functional>
#include <vector>

using std::cout; using std::endl;
using std::setw; using std::string;

int main() {
    string str1("arbitrary string");
    std::vector<string> vec2 = { "true", "false", "false", "true", "false", "true" };

    std::hash<string> str_hash;

    cout << "str_hash(\"" << str1 << "\") => " << str_hash(str1) << endl;

    for (const auto& item : vec2) {
        cout << "str_hash(\"" << item << "\") => " << str_hash(item) << endl;
    }

    return EXIT_SUCCESS;
}

std::hash 템플릿 클래스는 STL의 <functional> 헤더에서 제공된다. string 인수 뿐 아니라 주어진 템플릿 인수로 해시 함수 객체를 생성하고, operator()를 사용하여 size_t값을 반환하며 해시 값을 생성한다.

---

std::unordered_set/map 해시 컨테이너

• 체이닝을 사용하는 해시 테이블에서 구현했던 해시 테이블 코드를 템플릿 형태로 바꾸면 모든 데이터 타입에 대해 사용할 수 있는 형태로 만들 수 있음
• STL은 이러한 기능을 std::unordered_set<Key>와 std::unordered_map<Key, Value> 형태로 미리 구현하여 제공한다. _set은 키만 저장할 수 있고, _map은 키와 값을 함께 저장할 수 있다.
• 두 컨테이너 모두 체이닝을 사용하는 해시 테이블로 구현
• 해시 테이블의 각 행은 키 또는 키/값의 쌍을 저장하는 벡터이고, 벡터의 각 버킷에 저장하는 값은 그 인덱스를 해시 값으로 하는 연결 리스트의 첫 번째 노드(node)에 대한 참조
• 데이터가 없는 버킷은 널(null)을 가리킨다.

부하율과 재해싱

• 기본적으로 이들 컨테이너는 최대 1의 부하율을 가짐
• 해시 테이블보다 원소 개수가 많아지게 되면 곧바로 해시 테이블 크기를 키우고, 해시 함수를 변경하는 재해싱이 일어남. 그 결과 부하율은 1보다 작아지게 됨
• 사용자가 강제로 rehash() 함수를 호출하여 재해싱을 할 수도 있고, max_load_factor(float) 함수를 사용하여 기본값이 1로 되어있는 부하율 최대 한계치를 변경할 수도 있음
  • 부하율이 지정된 한계치를 넘어가면 재해싱 발생

참조 연산자 []

• 참조연산자 []와 키를 통해 값을 받아올 수 있다.
• 이 연산자는 값에 대한 참조를 반환하므로 이를 이용하여 저장된 값을 변경할 수도 있다.
• 만약 해당 키가 없다면 해당 위치에 기본값을 추가하여 반환한다.
  • 기본 값은 0이다.

기타 메서드

• rehash(): 재해싱 강제
• load_factor(): 현재 부하율 반환
• max_load_factor(float): 부하율 최대 한계치 변경
• bucket_count(): 현재 버킷의 갯수 반환

시간 복잡도

• 부하율을 최대 1로 유지한다고 해서 모든 키에 대한 룩업/삭제 연산이 O(1)을 보장하는 것은 아니다. 부하율은 단순히 특정 버킷에 해당하는 리스트들의 평균 길이(키 갯수/버킷 갯수)일 뿐이다. 만약 해시 함수가 적절하지 못하다면 룩업/삭제 연산에 있어 O(1) 이상의 시간이 소요된다.

해시 함수가 중복되지 않는, 골고루 해시 값을 반환해주고(= 해시 충돌이 거의 X), 부하율이 1 이하라면

• 삽입 시간 복잡도: O(1)
  • 반면 map 같은 경우 정렬이 이루어져야 하기에 O(logN)
• 룩업/삭제 시간 복잡도: O(1)

해시 함수가 적절치 못하여 해시 충돌이 자주 발행하는 경우

• 삽입 시간 복잡도: O(1)
• 룩업/삭제 시간 복잡도: (최악)O(N)

---

multiset/map

• unordered_set과 unordered_map은 중복 키를 허용하지 않는다. 만약 중복된 키를 저장하고 싶다면, unordered_multiset과 unordered_multimap을 사용해야 한다.
• 이 두 컨테이너의 삽입 함수는 주어진 키가 이미 존재하는지를 검사하지 않는다.
• 특정 키에 해당하는 모든 값을 얻을 수 있는 기능도 지원한다.

---

사용자 자료형이 키가 될 때

• to be ..