Map Container와 마찬가지로 Functor Iterating을 이용하여 측정하였다.
측정 환경 : Visual Studio 2008
측정 컨테이너 :
1. std::set
2. stdext::hash_set
3. boost::unordered_set
측정 방법 : Functor
boost::unordered_set의 경우 컨테이너의 element가 1천개가 되더라도 bucket이 1:1.5로 생기는 것을 확인하였다.
(약 1.5배의 Bucket이 생성되었다.)
Hash 알고리즘에서 Collision이 발생하지 않도록 Bucket을 생성하는 것이 핵심인데,
VisualStudio 2008의 std::hash_set에서는 Type을 고려하지 않고 동일한 해쉬 함수를 사용하는데,
boost::unordered_set은
1. std::numeric_limits로 해당 타입의 크기
2. signed / unsigned
를 고려하여 해쉬 Seed 값을 생성하여 사용하기 때문에 각각의 Type 특성에 맞는 해쉬 키를 사용한다.
덧글을 달아 주세요