일부의 정보만 기억을 했다가 매칭을 하는 것
📍 키에 대응되는 값을 저장하는 자료구조

• 배열로 구현을 하면, O(N)으로 원소를 찾게 될텐데 해시에서는 모든 연산(Insert, Erase, Find, Update)이 O(1)
• 해시 함수: 임의 길이의 데이터를 고정된 길이의 데이터로 대응시키는 함수 (일부의 정보만 보자!)
  -> 배열의 인덱스로 사용

충돌 문제

• 키가 서로 같을 경우 발생
• 충돌이 발생하는 것을 막을 수는 없음
• 충돌이 발생했을 때의 회피 방안은 있음

1) 충돌 회피1 - Chaining

• 연결 리스트 사용
• 실제 STL 자료구조에서는 Chaining을 이용하고 있음
• 좋은 해시 함수 정의 필요

2) 충돌 회피2 - Open Addressing

• 인덱스 기준으로 가되, 이미 원소가 들어가 있으면 옆 칸에 삽입
• 삭제를 할 때 해당 칸에 쓰레기 값을 넣는 등 빈칸이 되지 않도록 해야 함 -> 해당 칸이 빈칸이 아니라 원래 값이 있었는데 제거된 상태임을 명시

Linear Probing

• 충돌 발생 시 오른쪽으로 1칸씩 이동하는 방식
• 장점: Cache hit rate가 높다.
• 단점: Clustering이 생겨 빈칸을 찾을 때까지 이동하는 횟수가 늘어나서 성능에 안 좋은 영향을 준다.

Quadratic Probing

• 충돌 발생 시 1, 3, 5, ... 칸씩 이동하는 방식
• 처음 위치를 기준으로 생각해보면 1, 4, 9, ... 칸씩 이동(제곱)
• 장점: Cache hit rate가 나쁘지 않다. Clustering도 어느 정도 회피할 수 있다.
• 단점: 해시 값이 같다면 Clustering이 생긴다.

Double Hashing

• 충돌 발생 시 이동할 칸의 수를 새로운 해시 함수로 계산하는 방식
• e.g. 맨 뒤 숫자로 이동할 칸의 개수 정하기
• 장점: Clustering을 효과적으로 회피할 수 있다.
• 단점: Cache hit rate가 낮다.

STL

1) unordered_set

• set과 달리 해시 함수를 통해 원소를 찾음 -> 정렬될 필요 X
• 탐색할 때 시간복잡도는 O(1)이지만, 만약에 해시 충돌이 발생하면 같은 해시 값 내에서 또 원소를 찾아야 하므로 O(N)까지도 늘어날 수 있음

#include <unordered_set>

void unordered_set_example() {
	unordered_set<int> s;
    s.insert(-10);
    s.insert(100);
    s.insert(15); // {-10, 100, 15}
    s.insert(-10); // 중복 불가
    cout << s.erase(100) << '\n'; // {-10, 15}, 1 반환
    cout << s.erase(20) << '\n'; // {-10, 15}, 0 반환
    
    if (s.find(15) != s.end()) // 반환값의 형태는 iterator
    	cout << "15 is in s\n";
    else
    	cout << "15 is not in s\n";
    
    cout << s.size() << '\n'; // 2 반환
    cout << s.count(50) << '\n'; // unordered_set에서는 중복이 허용되지 않으므로 항상 1 또는 0 반환
    
    for (auto e : s) // range-based loop
    	cout << e << ' ';
    
    cout << '\n';
}

2) unordered_multiset

✔️ 중복 허용

#include <unordered_set>

void unordered_multiset_example() {
	unordered_multiset<int> ms;
    ms.insert(-10);
    ms.insert(100);
    ms.insert(15);
    ms.insert(-10); // 중복 허용
    ms.insert(15);
    cout << ms.erase(15) << '\n'; // 15가 모두 다 지워짐!
    cout << ms.erase(ms.find(-10)) << '\n'; // 딱 한 개의 -10만 지워짐
    
    if (ms.find(15) != ms.end()) // 반환값의 형태는 iterator
    	cout << "15 is in ms\n";
    else
    	cout << "15 is not in ms\n";
    
    cout << ms.size() << '\n';
    
    for (auto e : ms) // range-based loop
    	cout << e << ' ';
    
    cout << '\n';
}

3) unordered_map

• 키에 대응되는 값을 찾아주는 STL
• 탐색할 때 시간복잡도는 O(1) (cf. map의 시간복잡도는 O(logN))

#include <unordered_map>

void unordered_map_example() {
	unordered_map<string, int> m;
    m["hi"] = 123;
    m["bkd"] = 1000;
    m["gogo"] = 165;
    cout << m.size() << '\n'; // 3 반환
    m["hi"] = -7;
    
    if (m.find("hi") != m.end())
    	cout << "hi in m\n";
    else
    	cout << "hi is not in m\n";
    
    m.erase("bkd"); // ("hi", 123), ("gogo", 165)
    
    for (auto e : m)
    	cout << e.first << ' ' << e.second << '\n';
        
    for (unordered_map<string, int>::iterator idx = m.begin(); idx != m.end(); idx++)
        cout << idx->first << ' ' << idx->second << '\n';
}