1. std::unordered_map

• HashTable로 구현된 자료구조
• 탐색 시간이 O(1)로 상수시간복잡도를 가짐
• 요소의 삽입/삭제가 빈번합 경우 사용될 수 있음

2. structure

unordered_map의 경우 일반적인 map과 달리 key값을 기준으로 정렬하지 않는다. 그렇다면 더 느린 시간복잡도를 가진다고 생각하겠지만 HashTable을 사용해 이를 해결했다.

[동작 구조]
1. 해시함수에 key값을 넣어 반환 값을 받는다.
2. 반환 값을 bucket의 index로 사용해 value를 알 수 있다.

3. hash collision

key값은 무한하지만 bucket의 사이즈는 유한하기 때문에 다른 key값이더라도 해시 함수는 같은 값을 반환할 수 있다. 이러한 문제를 어떻게 해결할까?

3.1. 체이닝

• 해시 충돌이 발생한다면 인덱스에 추가로 이어서 저장하는 방법
• 삽입 삭제가 쉬운 list로 구현하는 것이 효과적
• 탐색시간이 증가

3.2. 개방 번지화

• 해시 충돌이 발생하면 반환값을 버리고 다른 index에 value를 할당하는 방법
• 다른 index를 할당하는 규칙이 존재해야 함
  • 선형 탐사: 고정된 폭으로 탐사하는 기법
    • 다음 인덱스를 확인
    • value가 특정 부분에 밀집되는 클러스터 현상이 발생하기 쉬움
    • 밀집된 경우 탐색 시간이 길어짐
  • 제곱 탐사: 이차식을 통해 인덱스를 구해 한 곳에 데이터가 집중되지 않도록 하는 기법
    • 같은 해시값이 나온다면 동일한 과정을 거치기 때문에 2차 클러스터가 발생가능
  • 이중 해싱: 또 다른 해시 함수를 사용해 증가폭을 구한 뒤 인덱스를 증가시켜 비어있는 곳을 탐색하는 기법