해시를 사용한 집합과 맵 (Hash Set / Hash Map)

정의

해시 집합 (Hash Set) 과 해시 맵 (Hash Map) 은 해시 함수를 이용해 키를 버킷 인덱스로 변환하고, 평균 O(1) 시간에 삽입, 조회, 삭제를 수행하는 자료구조다. C++ std::unordered_set, std::unordered_map, Python dict, set, Java HashMap, HashSet 이 대표적이다.

해시 테이블은 1953년 Hans Peter Luhn 이 고안했으며, 현대 프로그래밍 언어의 가장 기초적인 자료구조 중 하나다.

문제 상황과 동기

다음 쿼리를 Q번 처리해야 한다:

• 멤버십 검사: “원소 x가 있는가?”
• 빈도 세기: “단어 w의 등장 횟수는?”
• 중복 제거: N개 원소에서 고유한 값만

naive (배열 탐색): O(N) per query. N=Q=10^5 이면 10^10.

해시: 해시 함수 h(x) 로 O(1) 평균 시간에 버킷 접근. 총 O(N + Q).

핵심 통찰: 키를 균등 분포된 정수로 변환하면 충돌이 적고 접근이 빠르다. 최악 O(N) (모든 원소가 한 버킷) 이지만 좋은 해시 함수와 재해싱으로 실용적으로는 거의 O(1).

실무 위치: DB 인덱스, 캐시 (Redis, Memcached), 컴파일러 심볼 테이블, 브라우저 쿠키, DNS 조회.

시각화

핵심 아이디어

해시 함수

키 k 를 버킷 배열 크기 M 범위 정수로 변환:

h(k) = f(k) mod M

좋은 해시 함수 조건:

• 균등 분포: 모든 버킷에 골고루
• 결정적: 같은 입력은 항상 같은 출력
• 빠름: O(1) 계산

예:

• 정수: h(k) = k mod M
• 문자열: h(s) = (Σ s[i] * p^i) mod M (polynomial rolling hash, p는 소수)

충돌 처리

두 키가 같은 버킷에 매핑되면 충돌 (collision).

1. Chaining (체이닝)

각 버킷에 연결 리스트. 같은 해시값인 원소를 리스트에 추가.

Bucket[0]: []
Bucket[1]: [5, 15, 25]
Bucket[2]: [7]

삽입/조회: O(1 + α), α = load factor = N / M.

2. Open Addressing (개방 주소법)

충돌 시 다음 빈 슬롯 찾기.

• Linear probing: (h(k) + i) mod M
• Quadratic probing: (h(k) + i^2) mod M
• Double hashing: (h1(k) + i * h2(k)) mod M

clustering 문제 있으나 캐시 친화적.

Load Factor와 재해싱

load factor α = N / M  (원소 개수 / 버킷 개수)

• α > 0.75 되면 M을 2배로 확장, 모든 원소 재해싱 (amortized O(1))
• α < 0.25 되면 축소 (선택)

알고리즘

해시 집합 (Chaining)

hash_set:
    buckets: array of lists
    size: 0
    M: bucket count
    
insert(x):
    idx = h(x) mod M
    if x not in buckets[idx]:
        buckets[idx].append(x)
        size++
        if size / M > 0.75:
            rehash()

contains(x):
    idx = h(x) mod M
    return x in buckets[idx]

erase(x):
    idx = h(x) mod M
    if x in buckets[idx]:
        buckets[idx].remove(x)
        size--

rehash():
    M_new = M * 2
    new_buckets = [[] for _ in range(M_new)]
    for bucket in buckets:
        for x in bucket:
            new_idx = h(x) mod M_new
            new_buckets[new_idx].append(x)
    buckets = new_buckets
    M = M_new

구현

// unordered_set, unordered_map 예제
#include <bits/stdc++.h>
using namespace std;
int main() {
  unordered_set<int> s;
  s.insert(5); s.insert(3); s.insert(7);
  
  cout << "contains 3? " << (s.count(3) ? "YES" : "NO") << "\n";
  cout << "contains 8? " << (s.count(8) ? "YES" : "NO") << "\n";
  
  unordered_map<string, int> freq;
  vector<string> words = {"apple", "banana", "apple"};
  for (auto w : words) freq[w]++;
  
  cout << "freq[apple] = " << freq["apple"] << "\n";
  cout << "freq[banana] = " << freq["banana"] << "\n";
}

# set, dict (둘 다 해시 기반)
s = set()
s.add(5); s.add(3); s.add(7)
​
print("contains 3?", 3 in s)
print("contains 8?", 8 in s)
​
from collections import Counter
words = ["apple", "banana", "apple"]
freq = Counter(words)
​
print("freq[apple] =", freq["apple"])
print("freq[banana] =", freq["banana"])

// HashSet, HashMap
import java.util.*;
public class Main {
  public static void main(String[] args) {
      HashSet<Integer> s = new HashSet<>();
      s.add(5); s.add(3); s.add(7);
      
      System.out.println("contains 3? " + s.contains(3));
      System.out.println("contains 8? " + s.contains(8));
      
      HashMap<String, Integer> freq = new HashMap<>();
      String[] words = {"apple", "banana", "apple"};
      for (String w : words)
          freq.put(w, freq.getOrDefault(w, 0) + 1);
      
      System.out.println("freq[apple] = " + freq.get("apple"));
      System.out.println("freq[banana] = " + freq.get("banana"));
  }
}

contains 3? YES
contains 8? NO
freq[apple] = 2
freq[banana] = 1

복잡도

해시 함수 예시

문자열 해시 (Polynomial Rolling Hash)

unsigned long long hash_string(const string& s) {
    const int p = 31, mod = 1e9 + 9;
    unsigned long long h = 0, pow = 1;
    for (char c : s) {
        h = (h + (c - 'a' + 1) * pow) % mod;
        pow = (pow * p) % mod;
    }
    return h;
}

쌍 해시 (pair<int, int>)

struct pair_hash {
    size_t operator()(const pair<int, int>& p) const {
        return hash<int>()(p.first) ^ (hash<int>()(p.second) << 1);
    }
};
unordered_set<pair<int, int>, pair_hash> s;

변형

1. Perfect Hashing

키 집합이 고정이면 충돌 없는 해시 함수 구성 가능 (two-level hashing). 최악 O(1) 보장.

2. Cuckoo Hashing

두 해시 함수 사용. 충돌 시 다른 버킷으로 기존 원소를 쫓아냄. 최악 O(1) 조회, 삽입은 amortized O(1).

3. Bloom Filter

확률적 자료구조. “없음” 은 확실, “있음” 은 false positive 가능. 공간 효율적.

함정

1. 해시 충돌 공격

악의적 입력으로 모든 키를 한 버킷에 몰아 O(N^2). 방어: 랜덤 시드, SipHash 같은 cryptographic hash.

2. 순서 보장 없음

unordered_set 은 순회 순서가 삽입 순서와 무관. 정렬 필요시 set 또는 vector + sort.

3. 키 해싱 불가능

C++ 에서 기본 타입만 std::hash 지원. 커스텀 클래스는 해시 함수 직접 정의 필요.

struct Point {
    int x, y;
    bool operator==(const Point& p) const { return x == p.x && y == p.y; }
};
namespace std {
    template<> struct hash<Point> {
        size_t operator()(const Point& p) const {
            return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
        }
    };
}

4. 재해싱 비용

load factor 초과 시 재해싱 O(N). 대량 삽입 전 reserve() 로 미리 확장.

unordered_set<int> s;
s.reserve(1000000);  // 재해싱 횟수 감소

BOJ 연습 문제

참고

• 집합과 맵
• 트리 집합과 맵