C++ 해시 테이블
- 해시 구현에서 항상 양의 정수만 취급할 수는 없다.
- 오히려 문자열 데이터를 다루게 되는 경우가 더 많다
- 영어 사전을 구현하려면 영어 단어를 키로 사용하고, 뜻을 값으로 사용해야 한다
- 모듈로 함수는 문자열에는 적용할 수 없다
- 간단한 해결책은 문자열의 모든 문자에 대한 ASCII 코드 값을 모두 더한 후에 모듈로 연산을 하는 것이다.
- 위 방법은 충돌이 빈번하게 발생할 수 있다
- C++은 문자열로부터 해시 값을 생성하는 용도로 std::hash<std::string>(std::string) 함수 객체를 제공한다
- 이 함수 객체 내부에는 해시 함수 알고리즘이 구현되어 있다.
- C++은 문자열 이외에도 모든 기본 데이터 타입에 대한 해시 값을 생성하는 기능도 제공한다
- "체이닝을 사용하는 해시 테이블"에서 구현했던 해시 테이블 코드를 템플릿 형태로 바꾸면 모든 데이터 타입에 대해 사용할 수 있는 형태로 만들 수 있다.
- STL은 이러한 기능을 std::unordered_set와 std::unordered_set<Key, Value> 형태로 미리 구현하여 제공한다
- std::unordered_set은 키만 저장할 수 있고, std::unordered_map은 키와 value를 함께 저장할 수 있다
- 두 컨테이너 모두 체이닝을 사용하는 해시 테이블 형태로 구현되어 있다.
- 해시 테이블의 각 행은 키 또는 키와 값의 쌍을 저장하는 벡터이다. 여기서 각 행을 버킷(bucket)이라고 부른다
- 즉, key로부터 해시 값을 구하면 이에 해당하는 버킷에 접근할 수 있다
- 기본적으로 이들 컨테이너는 최대 1의 부하율을 가진다
- 해시 테이블 크기보다 원소 개수가 많아지게 되면 곧바로 해시 테이블을 키우고, 해시 함수를 변경하는 재해싱이 일어난다
- 사용자가 강제로 rehash()함수를 호출하여 재해싱을 할 수도 있다
- max_load_factor(float) 함수를 사용하여 기본값이 1로 되어 있는 부하율 최대 한계치를 변경할 수도 있다
- std::unordered_set와 std::unordered_map 컨테이너는 검색, 삽입, 삭제 등의 보편적인 기능을 제공한다
- 모든 원소에 차례대로 접근할 수 있도록 반복자 기능도 제공하고, 벡터나 배열 같은 다른 컨테이너로부터 바로 std::unordered_set 또는 std::unordered_map을 구성할 수 있는 생성자도 제공한다.
- std::unordered_map은 []연산자를 이용하여 주어진 키에 해당하는 값을 받을 수도 있다.
Example) STL에서 제공하는 해시 테이블
#include <iostream>
#include <unordered_map>
#include <unordered_set>
void print(const std::unordered_set<int>& container)
{
for(const auto& element : container)
std::cout << element << " ";
std::cout << std::endl;
}
void print(const std::unordered_map<int, int>& container)
{
for(const auto& element : container)
std::cout << element.first << " -> " << element.second << ", ";
std::cout << std::endl;
}
void find(const std::unordered_set<int>& container, const int element)
{
if(container.find(element) == container.end())
std::cout << element << " 검색 실패" << std::endl;
else
std::cout << element << " 검색 성공" << std::endl;
}
void find(const std::unordered_map<int, int>& container, const int element)
{
auto it = container.find(element);
if(it == container.end())
std::cout << element << " 검색 실패" << std::endl;
else
std::cout << element << "검색 성공 값 = " << it->second << std::endl;
}
int main()
{
std::cout << "*** std::unordered_set 예제 ***" << std::endl;
std::unordered_set<int> set1 = { 1, 2, 3, 4, 5 };
std::cout << "set1 초깃값 : ";
print(set1);
set1.insert(2);
std::cout << "2 삽입 : ";
print(set1);
set1.insert(10);
set1.insert(300);
std::cout << "10, 300 삽입 : ";
print(set1);
find(set1, 4);
find(set1, 100);
set1.erase(2);
std::cout << "2 삭제 : ";
print(set1);
find(set1, 2);
std::cout << "*** std::unordered_map 예제 ***" << std::endl;
std::unordered_map<int, int> squareMap;
squareMap.insert({2, 4});
squareMap[3] = 9;
std::cout << "2, 3의 제곱 삽입 : ";
print(squareMap);
squareMap[20] = 400;
squareMap[3] = 900;
std::cout << "20, 30의 제곱 삽입 : ";
print(squareMap);
find(squareMap, 10);
find(squareMap, 20);
std::cout << "squareMap[3] = " << squareMap[3] << std::endl;
std::cout << "squareMap[100] = " << squareMap[100] << std::endl;
print(squareMap);
return 0;
}
- 이들 컨테이너에서 저장된 원소 순서는 정해져 있지 않으며, 이 때문에 컨테이너 이름에 'unordered'가 들어간다
- [] 연산자는 key에 해당하는 실제 값이 없을 때는 기본 값 0을 추가한 후 반환해준다
- 현재 버킷의 개수를 알고 싶으면 bucket_count() 함수를 사용할 수 있다
- 이 외에도 load_factor(), max_bucket_count() 등의 함수를 이용하여 컨테이너 내부에서 사용되는 설정 값을 알 수 있다
- 또한 rehash()함수를 이용하여 수동으로 재해싱을 수행할 수 있다
- 이들 컨테이너는 체이닝 기법을 사용하여 구현되었으므로, 버킷에서 특정 키를 찾을 때 키가 같은지를 비교해야 한다
- 그러므로 키 타입에 대해 등호 연산이 정의되어 있어야 한다. 또는 템플릿 매개변수로 비교자를 지정할 수 있다
- std::unordered_set와 std::unordered_map은 중복된 키를 허용하지 않는다
- 만약 중복된 값을 저장하고 싶다면 std::unordered_multiset 또는 std::unordered_multimap을 사용해야 한다
- 이 두 컨테이너의 삽입 함수는 주어진 키가 이미 존재하는지를 검사하지 않는다.
- 또한 이들 컨테이너는 특정 키에 해당하는 모든 값을 얻을 수 있는 기능도 지원한다
- STL은 C++에서 지원하는 모든 기본 데이터 타입에 대한 해시 함수를 제공한다
- 따라서 앞서 언급했던 컨테이너에서 사용자 정의 클래스 또는 구조체를 키 타입으로 사용하려면 std 네임스페이스 안에서 해시 함수를 구현해야 한다
- 또는 컨테이너 템플릿 매개변수로 해서 해시 함수 객체를 지정할 수도 있다
- 해시 함수를 직접 만드는 것은 성능에 큰 영향을 주기 때문에 그다지 좋은 생각은 아니다
- 해시 함수로 MD5, SHA-1, SHA-256 같은 복잡한 암호화 함수도 사용할 수 있다
- 암호화 함수를 사용하면, 해시 값으로 부터 원본 데이터를 알아내는 역해싱이 매우 어렵기 때문에 보안 시스템에서 사용되기도 한다