Recommanded Free YOUTUBE Lecture: <% selectedImage[1] %>

Hashed Associative Container

해쉬 연관 컨테이너hash table의 연관 컨테이너 구현이다. 해쉬 연관 컨테이너의 원소들은 정렬이 되지 않는다. 평균적으로 상수타임에 원소를 검색할 수 있지만, 최악의 경우에는 선형시간이 소비된다. 해쉬 연관 컨테이너의 성능은 순전히 Hash 함수에 좌우된다.

컴파일

해쉬 연관 컨테이너는 std namespace에 포함되지 않는다. 아래와 같이 namespace를 지정해줘야 한다.
using namespace __gnu_cxx;

hash_map

hash_map은 데이터를 가지는 객체의 해쉬 연관 컨테이너다. map(:12)과 마찬가지로 는 유일하다. hash_map은 "dictionaries"의 구현에 효과적인 컨테이너다.
a <apple, 사과>
<air, 공기>
<act, 행위>
b <baby, 아기>
<bag, 가방>

예제

#include <iostream>
#include <hash_map>
#include <string.h>

using namespace std;
using namespace __gnu_cxx;

struct eqstr
{
    bool operator()(const char* s1, const char* s2) const
    {
        return strcmp(s1, s2) == 0;
    }
};

int main()
{
    hash_map<const char*, int, hash<const char*>, eqstr> months;

    months["january"] = 31;
    months["february"] = 28;
    months["march"] = 31;
    months["april"] = 30;
    months["may"] = 31;
    months["june"] = 30;
    months["july"] = 31;
    months["august"] = 31;
    months["september"] = 30;
    months["october"] = 31;
    months["november"] = 30;
    months["december"] = 31;

    std::cout << "september -> " << months["september"] << endl;
    std::cout << "april     -> " << months["april"] << endl;
    std::cout << "june      -> " << months["june"] << endl;
    std::cout << "november  -> " << months["november"] << endl;
}
다음은 실행결과다.
$ ./hash_map 
september -> 30
april     -> 30
june      -> 30
november  -> 30

hash_set

hash_multimap

hash_multiset

해쉬 연관 컨테이너의 사용에 대해서

hash table을 이용해서 성능을 높이려는 목적으로 사용한다. 하지만 굳이 해쉬 연관 컨테이너를 사용할 필요가 있을까라는 생각이 든다. 그냥 hash function을 이용해서 해쉬 테이블 만들고 다른 STL container를 배치하는게 더 낫지 않을까 ?