Hash map
jjuiddong
목차 |
STL의 hash_map 과 map 둘 중에 어떤 것을 써야 할까?
- hash_map 에 대해 설명이 잘 되어있다.
테스트 1
- 키 = 20개의 랜덤으로 만들어진 알파벳 스트링
- 데이타 갯수: 십만개
- CAtlMap 180.920 millisecond
- map 1812.640869 millisecond
- hash_map 너무 오래걸려서 중간에 끔, 1분이상 걸림
테스트 2
- 키 = 랜덤으로 만들어진 int
- 데이타 갯수 십만개
- CAtlMap 114.920 millisecond
- map 745.780 millisecond
- hash_map 1171.985 millisecond
결론
- 키 값이 거의 중복이 되지 않으며, 데이타갯수가 많을 때, int, string 의 키값으로 하는 경우는 log(N) 성능을 가진 map 이 더 빠르게 나왔다.
- CAtlMap이 가장 좋은 결과를 내지만, std::string을 쓰는 방법을 몰라 일단 보류 중이다.
- hash_map 은 해쉬함수를 어떻게 만드느냐에 따라 영향이 크기 때문에 전문적으로 이것을 연구하지 않는 이상 잘 만들기가 힘들다.
- 기본으로 제공하는 해쉬함수를 쓸 경우 log(N)으로 검색하는 map보다 느리다.