해시 (Hash)

---

전날 내용 요약 — 큐 (Queue)

• 큐는 FIFO(First In, First Out) 자료구조
• push() / pop() / front() / back() / empty() / size()
• deque는 앞뒤 양쪽에서 삽입/삭제 가능
• BFS(너비 우선 탐색)는 큐로 구현 → 최단 경로 보장

---

해시란?

배열에서 특정 값을 찾으려고 하면 처음부터 하나씩 비교해야 하기에 O(N)의 시간 복잡도를 가진다.
정렬 후 이분 탐색을 사용하면 O(log N)으로 줄어들기는 하지만, 정렬 자체가 O(N log N)이다.

하지만, 해시는 O(1)로 탐색이 가능하다.

해시는 key를 숫자로 변환해서 그 숫자를 배열의 인덱스로써 접근을 한다.

---

해시 충돌

다른 키가 같은 인덱스로 매핑되는 현상을 해시 충돌이라고 부른다.

이를 해결하기 위한 방법으로는 체이닝과 개방 주소법이 있다.

체이닝은 같은 인덱스에 연결 리스트로 여러 값을 저장하는 방법이다. (unordered_map이 체이닝 방식)

개방 주소법은 충돌 시에 다른 빈 슬롯을 찾아서 저장시키는 방법이다.

---

unordered_map

map과는 달리 정렬이 없고, 해시 기반이기 때문에 탐색/삽입/삭제가 모두 평균 O(1)의 시간 복잡도를 가진다.

#include <unordered_map>
using namespace std;

unordered_map<string, int> um;

//삽입
um["apple"] = 3;
um["banana"] = 5;
um.insert({"cherry", 2});

//조회
cout << um["apple"];  //3
cout << um["banana"]; //5

//존재 여부 확인
if(um.count("apple")) { /*존재*/ }
if(um.find("apple") != um.end()) { /*존재*/ }

//삭제
um.erase("apple");

//순회
for(auto& [key, val] : um)
{
    cout << key << ": " << val << "\n";
}

//크기
cout << um.size();

---

map vs unordered_map

	map	unordered_map
내부 구조	레드-블랙 트리	해시 테이블
탐색/삽입	O(log N)	O(1) 평균
정렬 여부	key 기준 정렬됨	정렬 없음
사용 시점	정렬이 필요할 때	빠른 탐색이 필요할 때

---

unordered_set

값의 존재 여부만 확인할 때 사용. key-value가 아니라 key만 저장

#include <unordered_set>
using namespace std;

unordered_set<string> us;

// 삽입
us.insert("apple");
us.insert("banana");

// 존재 여부
if(us.count("apple")) { /* 존재 */ }
if(us.find("apple") != us.end()) { /* 존재 */ }

// 삭제
us.erase("apple");

// 순회
for(auto& val : us)
{
    cout << val << "\n";
}

---

자주 쓰는 패턴

빈도 카운팅

unordered_map<string, int> counter;
vector<string> words = {"apple", "banana", "apple", "cherry", "banana", "apple"};

for (auto& w : words) counter[w]++;

중복 확인

unordered_set<int> seen;
vector<int> arr = {1, 2, 3, 2, 1};

for (int x : arr) {
    if (seen.count(x)) {
        cout << x << "는 중복\n";
    }
    seen.insert(x);
}

---

[] vs at()

unordered_map<string, int> um;
um["없는키"]++; //um["없는키"] == 1
//존재하지 않는 키에 []로 접근하면 자동으로 0으로 초기화 됨
//존재하지 않는 키에 at()으로 접근하면 예외 발생

---

시간복잡도

연산	평균	최악 (해시 충돌 극심)
삽입	O(1)	O(N)
삭제	O(1)	O(N)
탐색	O(1)	O(N)

• algorithm
• hash
• c