[Effective STL] 25. hash 컨테이너

항목 25. 해쉬 컨테이너에 대해 충분히 대비해 두자

 

 

 

C++11 이전의 해쉬 테이블

• STL에는 해쉬 연관 컨테이너가 포함되지 않았다.
• C++11 이후에는 unordered_set, unordered_map이 추가되었다.
• 이 책은 모던 C++이 나오기 전이므로 표준이 아닌 해쉬 컨테이너를 기준으로 설명하고 있다.
• 표준이기 전에 가장 대표적으로 쓰이던 것은 SGI과 딩컴웨어(Dinkumware)의 해쉬 컨테이너이다.

 

 

 

해쉬 컨테이너

• 다른 연관 컨테이너와 대부분 동일하다.
• 허나, 해쉬 컨테이너는 해쉬 함수(hashing function)을 지정해야 한다.

// 해쉬 컨테이너의 일반적인 형태
template<typename T,
         typename HashFunction,
         typename CompareFunction,
         typename Allocator = allocator<T> >
class hash_container;

// SGI 버전의 hash_set의 형태
// 해쉬 함수와 비교 함수에 대한 기본 타입을 제공한다.
template<typename T,
         typename HashFunction = hash<T>,
         typename CompareFunction = equal_to<T>,
         typename Allocator = allocator<T> >
class hash_set;

// 표준 해쉬 set의 형태
// SGI 버전과 동일하다.
template<typename T,
         typename HashFunction = hash<T>,
         typename CompareFunction = equal_to<T>,
         typename Allocator = allocator<T> >
class unordered_set;

• 비교 함수로 less가 아닌 equal_to를 사용하고 있다.
  • 즉 동등성이 아닌 상등성(euality) 검사(항목 19 참조)를 한다는 뜻이다.
  • 왜냐하면 해쉬 컨테이너는 요소 정렬에 의미가 없기 때문이다.
• 딩컴웨어에서 설계한 해쉬 컨테이너는 조금 다른 형태를 취한다.
  • 특성 정보(traits)처럼 별도의 클래스인 hash_compare에 해쉬 기본 함수와 비교 함수를 묶었다.
    • 특정 정보(traits) (EC++ 47 참조)

// 딩컴웨어 버전

// 해쉬 함수, 비교 함수를 포함하는 traits를 닮은 별도의 클래스
template<typename T, typename CompareFunction = less<T> >
class hash_compare
{
public:
    enum
    {
        bucket_size = 4, // 버킷 갯수에 대한 요소 개수의 최대 허용 비율
                         // 해당 비율이 넘었을 때 해쉬 테이블 내의 버킷 수를 증가시키고,
                         // 테이블에 저장된 요소들을 다시 해쉬 처리한다.
        min_buckets = 8 // 버킷의 최소 갯수
    };
    
    // operator()를 오버로딩해서 해쉬 함수와 비교 함수를 구현
    size_t operator()(const T&) const; // 해쉬 함수
    bool operator()(const T&, const T&) const; // 비교 함수
    ...
};

template<typename T,
         typename HashingInfo = hash_compare<T, less<T> >,
         typename Allocator = allocator<T> >
class hash_set;

 

 

 

사용법과 동작

• 사실 어떤 버전이든 다음처럼 간단히 사용 가능하다.

hash_set<int> intTable;

• 하지만 SGI와 딩컴웨어는 내부 동작은 다르게 구현되어 있다.
• SGI 버전
  
  • 전통적인 개방형 해싱(open hashing)
  • 데이터 요소들의 단일 연결 리스트에 대한 포인터가 배열(버킷 집합)에 들어간 형태

• 딩컴웨어 버전
  • 개방형 해싱을 취하지만, 다소 독특한 자료 구조의 기반 하에 설계.
  • 버킷은 반복자 쌍의 배열로 구성되어 있으며, 이 반복자가 가리키는 것이 데이터 요소의 이중 연결 리스트이다.
  • 즉, 두 개의 반복자로 각 버킷에 들어 있는 데이터 요소의 범위를 나타낸다.