C++의 unordered_map이라는 STL은 내부적으로 해시테이블로 구현되어있다. (해시맵이라고도 한다.)

해시테이블은 다음과 같은 특징을 가지고 있다.

• key-value 쌍으로 관리된다.
• 같은 key값을 허용하지 않는다.
• 내부에서 자동으로 정렬되지 않는다.
• hash function을 통한 index로 관리한다.
• 버킷이 필요하기 때문에 메모리 사용량이 증가한다.
• 다른 key여도 같은 hash 값을 가질 수 있다.

탐색 : O(1)

삽입 : O(1)

삭제 : O(1)

→ worst는 O(n)

언제 좋을까?

• 자료의 삽입, 삭제가 빈번하지 않은 경우
• 많은 자료 저장과 빠른 검색이 필요할 경우

→ 양이 적으면 차라리 vector, list가 good (unordered_map을 사용할 때 메모리 낭비와 검색 시 오버헤드가 있기 때문)