정의
- google 에서 만든 C++ hash container library
- STL과 동일한 문법, 함수로 만들어져 있으므로, STL을 사용하듯이 사용하면 된다.
- memory를 덜 잡아먹는 'sparse' 방식, 속도가 빠른 'dense' 방식이 있다.
- 현재 0.6 version까지 나와있다.
download
Install google hash library
- template 라이브러리 이므로 컴파일할 필요는 없다. 헤더 파일의 경로만 지정해주면 사용할 수 있다.
사용법
Class 정의
sparse_hash_map<Key, Data, HashFcn, EqualKey, Alloc>
- Key: Key 값의 type이다.
- Data: 데이터 값의 type 이다.
- HashFcn: Key 를 distribute하기 위한 hash 함수이다. 보통 hash<key type> 을 사용한지만, 직접 구현해서 쓰는 것이 성능이 더 좋을 수도 있다.
- EqualKey: 동일한 key인지를 비교하기 위한 functor 이다. 직접 구현해주어야 한다. C++ style의 functor 를 사용하면 된다.
Key: C-style string
- C-style string을 Key로 사용하고 싶을 때에는 다음 코드에 나온대로 사용하면 된다.
#include <iostream>
#include <google/sparse_hash_map>
using google::sparse_hash_map; // namespace where class lives by default
using std::cout;
using std::endl;
// functor for EqualKey
struct eqstr
{
bool operator()(const char* s1, const char* s2) const
{
return (s1 == s2) || (s1 && s2 && strcmp(s1, s2) == 0);
}
};
//hash<const char*> 는 google/sparsehash/hash_fun.h 에 정의되어 있다.
int main()
{
sparse_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;
cout << "september -> " << months["september"] << endl;
cout << "april -> " << months["april"] << endl;
cout << "june -> " << months["june"] << endl;
cout << "november -> " << months["november"] << endl;
}
Key: C++ style(STL) string
- 만약에 C++ style string을 key로 사용하고 싶다면 아래와 같이 사용한다.
struct HashString
{
size_t operator()(const std::string _string) const
{
register size_t ret = 0;
for(std::string::const_iterator it = _string.begin(); it != _string.end(); ++it )
ret = 5 * ret + *it;
return ret;
}
};
struct EqualString
{
bool operator()(const std::string& s1, const std::string& s2) const
{
return s1 == s2;
//return (s1 == s2) || (s1 && s2 && strcmp(s1, s2) == 0);
}
};
sparse_hash_map<const char*, int, HashString, EqualString> months;
성능
- 성능 측정 결과
Average over 10000000 iterations
Wed Dec 8 14:56:38 PST 2004
SPARSE_HASH_MAP:
map_grow 665 ns
map_predict/grow 303 ns
map_replace 177 ns
map_fetch 117 ns
map_remove 192 ns
memory used in map_grow 84.3956 Mbytes
DENSE_HASH_MAP:
map_grow 84 ns
map_predict/grow 22 ns
map_replace 18 ns
map_fetch 13 ns
map_remove 23 ns
memory used in map_grow 256.0000 Mbytes
STANDARD HASH_MAP:
map_grow 162 ns
map_predict/grow 107 ns
map_replace 44 ns
map_fetch 22 ns
map_remove 124 ns
memory used in map_grow 204.1643 Mbytes
STANDARD MAP:
map_grow 297 ns
map_predict/grow 282 ns
map_replace 113 ns
map_fetch 113 ns
map_remove 238 ns
memory used in map_grow 236.8081 Mbytes
구글 해쉬 루틴이 성능이 좋은 이유는 좋은 해쉬 펑션-데이터를 균등하게 배분해주는-를 사용하기 때문이다. 덜 최적화된 해쉬 함수는 해쉬 루틴의 성능을 저하시킨다. 예를 들어, Knuth의 Art of computer programming에 나온 알고리즘이나, SGI의 STL hash 함수는 데이터를 불균등하게 배분해주기 때문에 성능이 떨어진다.
좋은 해쉬 함수는 아래에서 구할 수 있다.
- Bob Jenkins: http://burtleburtle.net/bob/hash/
- Paul Hsieh: http://www.azillionmonkeys.com/qed/hash.html
- Fowler/Noll/Vo (FNV): http://www.isthe.com/chongo/tech/comp/fnv/
References
