STL 컨테이너 중 map은 말씀하신 대로 바이너리 서치 트리를 이용합니다.
(일반 binary tree가 아니라, binary search tree 입니다) 구현된 STL제품은 대부분 red-black트리를 이용하고 있습니다.
BST는 평균 탐색 시간이 O(log n)이 되는데, 이는 대부분의 경우 납득할 만한 성능을 보여주지만, 평균 탐색시간을 O(1), 즉 상수시간 안에 탐색을 해내고 싶을 때는 해쉬 테이블을 사용하게 되죠.
해쉬 테이블은 어떤 데이터를 사용하여 해슁 키를 생성합니다. 이를테면 "123456"이라는 문자열의 해슁 키로 123456이라는 정수를 생성하는 식이죠. 해슁 키 생성에는 여러가지 방법을 고려할 수 있습니다. 이를테면, 데이터를 구성하는 모든 자료를 각각의 바이트 별로 더하는 방법도 고려할 수 있고, 자릿수에 가중치를 두어서 더하는 방법도 있을 수 있습니다. 이로서 "근사적으로" 키와 자료 사이에 1:1 대응이 이루어지도록 해슁 키를 생성하고, 이 해슁 키를 배열의 인덱스로 사용하여 자료에 접근합니다. 단, 잘 만들어진 해슁 키는 랜덤 분포가 되므로, 해슁키를 배열의 사이즈로 (대개는 예상되는 자료 양의 2배에 가까운 소수) 나눈 나머지를 배열의 인덱스로 사용합니다.
배열의 접근은 당연히 상수 시간이 걸리므로, 해쉬 테이블 접근은 O(1)의 시간 복잡도가 나타나게 됩니다.
단, 이때 키를 배열의 사이즈로 나눈 나머지가 겹치는 경우가 발생 할 수 있는데, (배열의 사이즈로 소수를 사용하는 이유는 이러한 경우를 최소화하기 위해서입니다) 이런 경우에는 빈 영역을 찾아서 자료를 저장해야 합니다. 이를 해결하는 방법에는 선형 탐색, 2차 탐색 등이 있을 수 있습니다. 선형 탐색의 경우는 blob이 생성되는 문제가 있고, (즉, 한번 충돌이 일어난 영역 근방에서는 계속 충돌이 일어나게 되어 그 근처에 자료가 몰리게 되는 현상), 2차 탐색에서는 그런 문제가 다소 줄어들게 됩니다.
따라서 해쉬테이블의 성능을 좌우하는 것은 해슁 키를 어떻게 적절하게 생성하느냐 하는 것입니다. 해슁 키의 분포 상태가 랜덤에 가까울 수록 성능이 좋아지는 것이죠. 해쉬 테이블이 아직 STL에 포함되지 않은 것은, STL은 그 규정에서 수행 성능을 보장하도록 되어 있습니다. 이를테면, map, set 등의 컨테이너는 삽입, 삭제, 탐색이 모두 O(log n)을 보장하도록 규정되어 있으며, list등의 컨테이너는 지정된 위치의 삽입과 삭제는 모두 O(1)을 보장하고, 탐색, 임의원소 접근은 O(n)을 보장하도록 되어 있죠. vector 컨테이너는 삽인과 삭제, 탐색 모두 O(n)을 보장하되, 임의원소에의 접근은 O(1)을 보장합니다.
그러나, 해쉬 테이블은 사용자 데이터 타입에 대해서는 이러한 성능 보장을 할 수 없기 때문에, 아직 표준에 편입되지는 못하고 있습니다. 물론, 시판되는 STL제품군 중에는 hash_set과 hash_map, hash_list 등의 컨테이너가 포함되어 있는 제품도 있긴 하지만, 정식 표준 컨테이너는 아닙니다.
ref : http://kin.naver.com/qna/detail.nhn?d1id=1&dirId=1040101&docId=65660603&qb=aGFzaCBtYXAg7JuQ66as&enc=utf8§ion=kin&rank=1&search_sort=0&spq=0&pid=gGP/Ac5Y7u8sssmJZshssc--324518&sid=T4e-XaOYh08AACD-yto
