[자료구조] map/unordered_map

• 순서
  1. map이란?
  2. map의 특
  3. unordered_map이란?
  4. map과 unordered_map의차이점
  5. 해싱
  6. 해시충돌
• map이란?
  1. 레드 블랙 트리 또는 이진 탐색 트리 기반으로 데이터를 저장하는 컨테이너 자료구조
  2. pair<const Key, T>로 이루어진 컨테이너로 key를 기준으로 오름차순 정렬된 상태임
• map의 특징
  • key와 value 쌍으로 이루어진 트리로 중복을 허용하지 않음.
  • first, second가 pair 객체로 저장되며 first는 key second는 value로 저장됨
  • 시간 복잡도는 O(log n)이다.
• unordered_map이란?
  1. 해시 테이블을 기반으로 데이터를 저장하는 컨테이너 자료구조
  2. 정렬되지 않은 상태로 데이터를 저장하며, 데이터를 삽입한 순서와 다를 수 있음.
  3. 중복된 키를 허용하지 않음
  4. 시간 복잡도는 O(1)이다.
• map과 unordered_map의 차이점

항목	std::map	std::unordered_map
내부 구조	균형 이진 탐색 트리(대부분 RB-tree)	해시 테이블(버킷 기반)
키 순서	정렬(오름차순 기본)	없음(임의 순서)
시간복잡도	O(log n)보장	평균 O(1), 최악 O(n)
범위 연산	lower_bound, upper_bound 가능	범위 연산 비효율적
iterator 무효화	삭제된 원소만 무효화	rehash시 모든 iterator 무효화
메모리 오버헤드	노드 포인터 등	버킷 배열 + 노드
사용 상황	키 정렬/범위 쿼리 필요할 때	빠른 조회가 최우선일 때

• 해싱
  1. 해시 함수를 사용하여 임의의 데이터를 고정된 크기의 해시값으로 변환하는 과정.
  2. 위 과정으로 생성된 해시 값으로 데이터를 해시 테이블이라는 자료구조의 특정 위치를 계산하여 데이터를 저장하고 검색하는 방식.
  3. 매우 빠르게 데이터에 접근할 수 있게 해주어 STL의 map과 unordered_set 같은 키-값 쌍을 저장하고 검색하는 자료구조의 기반이 됨
• 해시충돌
  1. 서로 다른 두 키가 같은 해시값을 갖는 상황
  2. 해시 함수 결과 공간은 유한한데, 입력 공간은 거의 무한=>비둘기집 원리에 의해 충돌은 필연적
     • ex) 32비트 해시 함수 2의 32제곱 개의 값만 표현 가능. 하지만 이 이상 키를 넣으면 충돌 발생
  3. 해시 충돌의 문제점
     • 충돌이 많아질수록 탐색 시간이 길어짐 => 성능 저하
     • 보안적 문제(암호학 해시에서는 충돌 발견 시 안정성이 무너짐)
  4. 해시 충돌 해결 방법
     1. 체이닝
     2. 오픈 어드레싱
  5. unordered_map과 해시충돌
     • unordered_map에서 이러한 충돌을 해결하기 위해 해시 테이블의 체이닝 기법을 사용함.