Hash Table과 Map은 언제 사용하면 좋을까?
| Hash Table | Map | |
| 삽입속도 | O(1) | O(logN) |
| 삭제속도 | O(1) | O(logN) |
| 검색속도 | O(1) | O(logN) |
Hash와 Map의 핵심적인 차이점은 다음과 같다.
1. Hash table은 멀티스레드에서 동기화를 지원할 수 있다.
2. Map은 항상 정렬된 상태로 데이터가 유지된다.
3. Hash는 Hash Function을 이용해 O(1)의 검색속도를, Map은 O(logN)의 성능을 지닌다.
따라서 데이터의 양이 적을 경우 map보다 Hash Table의 성능이 우수해진다.
기본적으로 RB-Tree 기반으로 구현되어 자체적인 balancing이 가능하기에 성능은 트리의 레벨만에 영향을 받는다.
http://veblush.github.io/ko/posts/map-vs-unorderedmap-for-string-key/
문자열 키의 map, unordered_map 성능 비교
map 과 unordered_map 은 키, 값을 저장할 수 있는 컨테이너다. map 은 Red-Black Tree 를 사용해 키의 순서를 유지하는 반면 unoredered_map 은 해시 테이블을 사용해 키의 순서를 유지하지 않는다. unordered_map
veblush.github.io
데이터의 수가 많고 멀티스레드 환경에서의 안전성을 고려한다면 HashTable의 사용도 고려할 수 있다.
다만 해시 테이블의 성능은 Hash Function에 지극히 의존적이기 때문에
사전에 Key의 분포를 알고 알맞는 Function을 작성할 수 있을때 사용하는것이 유용하다.
아래는 Thread Safety를 구현한 C++ 해시맵 오픈소스
https://github.com/kshk123/hashMap
GitHub - kshk123/hashMap: A concurrent thread-safe hash map implemented in C++
A concurrent thread-safe hash map implemented in C++ - GitHub - kshk123/hashMap: A concurrent thread-safe hash map implemented in C++
github.com