1) 정의
- map은 일반적으로 균형 트리(balanced tree) 기반의 알고리즘으로 만들어짐
- unordered map은 해시(hash)를 기반으로 만들어짐
2) 이슈
- 두 자료구조 모두 성능을 저하의 요인으로 데이터들이 편향된 상황에서 사실상 두 자료구조 모두 일반적인 선형 자료 구조보다도 못한 성능을 가짐
3) map과 unordered map의 선호되는 용법
map
- 사전에 key의 분포를 알수 없는 경우 map이 더 유리함
- map의 경우는 균형 트리(balanced tree) 알고리즘을 사용함으로 삽입이나 삭제 시 균형 맞추는 알고리즘을 동작시켜 균형 트리를 유지함 ((red-black, AVL등...) 이때 생각보다 많은 비용이 들어갈수 있음) 그러나 사전에 데이터의 분포를 알수 없는 경우에도 늘 균형을 맞출수 있기 때문에 분포를 알수 없는 임의의 데이터의 경우 map의 성능이 더 우수함
unordered map
- 사전에 분포확률을 정확히 알 수 있어서 적절한 해시 함수(hash function)를 만들 수 있다면 unordered map이 유리함
- 해싱(hashing)은 기본적으로 충돌(collision)이 발생한 데이터를 실시간을 맞추는 알고리즘을 사용하지 않고 데이터의 분포는 해시 함수에 의존함. 따라서 key의 분포를 미리 알 경우 버킷(bucket)에 골고루 분포시킬수 있는 해싱 함수를 만들 수 있기 때문에 성능을 향상시킬수 있음. 또한 균형 트리처럼 삽입이나 삭제시 균형(balance)을 위한 처리가 없기 때문에 그만큼 성능에서 유리함
- key의 분포를 모를 경우 해싱 함수를 잘못만들면 충돌이 발생해 성능저하에 요인이 됌. 분포를 실시간으로 바꿀수 없기 때문에 아무런 방법이 없이 성능은 극적으로 떨어짐
4) map의 특정 사용
- map은 iterator로 순차적으로 데이터를 얻을 수 있음
단순히 전체를 순회(traversal)할 때만 유리한 것이 아니고 범위 검색 혹은 범위 추출이 가능하다는 장점도 있음
- 데이터의 빠른 삽입/삭제/검색은 유지하되 데이터가 정렬된 상태로 저장되길 원할 때에 사용함 예를 들어 범위 검색이 필요하거나, 유동적인 데이터에서 최소/최대값을 필요로 할 때 사용할 수 있음
그냥 프로그래머