unordered_map

**해싱(hashing)

• 각각의 데이터를 산술 연산을 이용하여 고유한 숫자 값으로 표현 한 뒤, 특정 데이터의 존재여부를 확인하거나 원본데이터를 추출하는 작업
• 검색하고자 하는 키 값을 입력 값으로 삼아 계산을 실시하게 되면 자료의 위치를 찾을 수 있다는 개념

---

📌map vs unordered_map

• map은 이진 검색 트리 기반으로 자동 정렬을 지원하지만 그로 인해 삽입, 삭제 연산이 O(log n)으로 느림.
• unordered_map은 해시 테이블 기반으로 삽입, 삭제 연산이 평균 O(1)로 매우 빠름.¹
• map은 데이터의 삽입, 삭제가 별로 없고 key값이 정렬되어 있어야 하는 경우 더 유리함.
• unordered_map은 데이터의 삽입, 삭제가 빈번하게 일어날 경우 더 유리함
• map과 unordered_map 중에 무조건 이걸 사용해야 한다고 정해진건 없음. 상황에 따라 판단해서 사용

---

Footnotes

1. 해싱 충돌이 심할 경우 최악의 경우에는 O(n) ↩