해싱

해싱이란?

해싱(hashing) 은 임의의 데이터(문자열, 상태 등)를 고정 크기의 정수(해시값)
로 바꾸는 기법입니다. 긴 데이터를 짧은 숫자로 요약해, 비교와 검색을 매우 빠르게
만듭니다.

핵심 직관: 두 데이터의 해시값이 다르면 반드시 두 데이터가 다릅니다. 해시값이
같으면 "거의 확실히" 같습니다(드물게 충돌 가능). 그래서 무거운 비교를 가벼운
정수 비교로 대체할 수 있습니다.

1. 왜 빠른가

문자열 두 개를 직접 비교하면 길이에 비례해 \(O(L)\)이 듭니다. 하지만 미리 해시값을
구해 두면 정수 한 번 비교로 \(O(1)\) 에 끝납니다. 문자열을 수없이 비교하는
문제에서 이 차이는 결정적입니다.

집합·맵(unordered_set/map, 파이썬 set/dict)이 평균 \(O(1)\)인 것도 내부적으로
해싱을 쓰기 때문입니다.

2. 문자열 해싱: 다항식 해시

문자열을 다항식의 계수로 보고, 어떤 밑 \(p\)와 모듈러 \(m\)으로 값을 계산합니다.

$$ H(s) = (s_0 \cdot p^{0} + s_1 \cdot p^{1} + \cdots + s_{L-1} \cdot p^{L-1}) \bmod m $$

이렇게 하면 각 문자의 위치 정보가 해시값에 반영되어, 서로 다른 문자열이 같은
값을 가질 확률이 매우 낮아집니다. \(p\)는 보통 알파벳 크기보다 큰 소수(31, 53,
\(10^9+7\) 근방), \(m\)은 큰 소수를 씁니다.

3. 부분 문자열 해시를 O(1)에

다항식 해시의 진짜 위력은 누적 해시(prefix hash) 와 결합할 때입니다. 누적
해시를 미리 구해 두면, 임의 부분 문자열의 해시를 \(O(1)\) 에 꺼낼 수 있습니다.

이로써 "두 부분 문자열이 같은가?"를 \(O(1)\)에 판정할 수 있어, KMP 같은 전용
알고리즘 없이도 문자열 매칭·중복 탐지·회문 검사를 풀 수 있습니다. 이것을
라빈-카프(Rabin-Karp) 스타일이라 부릅니다.

4. 충돌과 그 대처

서로 다른 데이터가 같은 해시값을 갖는 것을 충돌(collision) 이라 합니다.
완벽히 피할 수는 없지만 확률을 낮출 수 있습니다.

• 큰 모듈러 — \(m\)이 클수록 충돌 확률 \(\approx 1/m\)로 낮아집니다.
• 이중 해시(double hashing) — 서로 다른 \((p, m)\) 쌍으로 두 해시를 함께 쓰면,
  둘 다 충돌할 확률이 사실상 \(0\)이 됩니다. 경쟁에서 안전을 위해 자주 씁니다.
• 저격(anti-hash) — 밑/모듈러가 알려지면 의도적 충돌 입력이 가능. 무작위 밑을
  쓰면 방어됩니다.

5. 대표 활용

정리

해싱은 데이터를 정수로 요약해 비교·검색을 \(O(1)\)로 만듭니다. 문자열은 다항식
해시 + 누적 해시로 부분 문자열 비교를 \(O(1)\)에 처리하고, 충돌은 큰 모듈러와
이중 해시로 방어합니다. 다음 강의에서 구현합니다.

해싱을 코드로

다항식 해시, 부분 문자열 해시, 문자열 매칭, 그리고 충돌 방어를 구현합니다.

1. 누적 해시 전처리

밑 \(p\)와 모듈러 \(m\)으로 누적 해시와 \(p\)의 거듭제곱을 미리 계산합니다.

typedef unsigned long long ull;
const ull P = 31, M = 1000000007ULL;
int n = s.size();
vector<ull> h(n + 1, 0), pw(n + 1, 1);
for (int i = 0; i < n; i++) {
    h[i + 1] = (h[i] * P + (s[i] - 'a' + 1)) % M;   // 누적 해시
    pw[i + 1] = pw[i] * P % M;                       // P^(i+1)
}
// 부분 문자열 s[l..r] (0-인덱스, 닫힌 구간)의 해시
auto sub = [&](int l, int r) -> ull {
    return (h[r + 1] - h[l] * pw[r - l + 1] % M + M * M) % M;
};

P, M = 31, (1 << 61) - 1
n = len(s)
h = [0] * (n + 1)
pw = [1] * (n + 1)
for i in range(n):
    h[i + 1] = (h[i] * P + (ord(s[i]) - ord('a') + 1)) % M
    pw[i + 1] = pw[i] * P % M

def sub(l, r):                      # s[l..r] 닫힌 구간
    return (h[r + 1] - h[l] * pw[r - l + 1]) % M

+ M*M(C++)은 뺄셈에서 음수가 나오지 않게 하는 보정입니다. 파이썬은 음수
모듈러가 자동 처리됩니다.

2. 문자열 매칭 (라빈-카프)

길이 \(L\) 패턴을 텍스트에서 찾기: 패턴의 해시와, 텍스트의 모든 길이 \(L\) 부분
문자열 해시를 비교합니다.

ull target = sub_of_pattern;        // 패턴 해시
for (int i = 0; i + L - 1 < n; i++)
    if (sub(i, i + L - 1) == target) {
        // 후보 발견 — 안전하게 실제 문자열도 한 번 비교(선택)
    }

각 비교가 \(O(1)\)이라 전체 \(O(N)\)입니다.

3. 회문 판정

정방향 해시와 역방향 해시를 모두 만들어, 같은 구간의 두 해시가 같으면
회문입니다.

# rev = s를 뒤집어 같은 방식으로 누적 해시
# s[l..r]이 회문 ⟺ sub_forward(l, r) == sub_backward(대응 구간)

4. 충돌 방어: 이중 해시

서로 다른 \((P, M)\) 쌍으로 두 해시를 동시에 쓰고, 둘 다 같을 때만 같다고
판정합니다.

// 해시1: (P1, M1), 해시2: (P2, M2)
// 비교: h1[a] == h1[b] && h2[a] == h2[b]

이렇게 하면 충돌 확률이 \(1/(M_1\ M_2)\)로 사실상 \(0\)이 됩니다. 무작위 밑을 쓰면
의도적 저격 입력도 막습니다.

import random
P = random.randint(256, 10**6)      # 매 실행 다른 밑 → anti-hash 방어

5. 흔한 실수

• 문자 값에 +1 안 함 — 'a'를 \(0\)으로 매기면 "a", "aa" 등 앞쪽 a가
  값에 기여하지 못해 충돌. - 'a' + 1로 1부터 시작.
• 부분 해시 뺄셈 음수 — C++에서 보정 안 하면 언더플로. + M*M 또는 부호 처리.
• 단일 해시 저격 — 알려진 밑/모듈러는 충돌 입력에 당함. 이중·무작위 해시.
• 오버플로 — 곱셈 전에 unsigned long long 또는 모듈러. 파이썬은 무한정수라
  안전하지만 모듈러로 값을 작게 유지.
• 거듭제곱 미리 계산 안 함 — pw 배열 없이 매번 거듭제곱하면 느림.

6. 패턴 알아보기

• "문자열 매칭/검색" → 다항식 해시(라빈-카프) 또는 KMP.
• "부분 문자열이 같은가를 여러 번 비교" → 누적 해시 \(O(1)\) 비교.
• "회문/중복 부분 문자열" → 정·역 해시 또는 해시 집합.
• 안전이 중요하면 → 이중 해시 + 무작위 밑.

실전에서 해싱 문제 알아보기

해싱을 꺼낼 타이밍은 명확합니다 — "같은가?"라는 비교가 너무 많이, 너무 긴
대상에 대해 일어날 때입니다. 그 판단과 안전 수칙을 정리합니다.

1. 출제 신호

• 부분 문자열 비교가 반복 — "구간 \([a,b]\)와 \([c,d]\)가 같은 문자열인가"를
  \(Q\)번. 직접 비교는 \(O(QN)\), 누적 해시는 질의당 \(O(1)\)입니다.
• 패턴 검색 — 본문에서 패턴 등장 횟수(라빈-카프). KMP로도 되지만 해시가
  구현이 짧고 변형(2D, 여러 패턴)에 유연합니다.
• 서로 다른 부분 문자열 개수, 중복 검출 — 해시값을 집합에 모읍니다.
• 회문 질의 다수 — 정방향·역방향 해시를 모두 전처리해 \(O(1)\) 비교.
• 긴 문자열 다수를 그룹으로 묶기(아나그램 제외) — 해시를 키로 한 맵.

2. 풀이 결정 절차

1. 비교 횟수 × 직접 비교 비용을 계산합니다 — 제한 안이면 그냥 직접
   비교하세요. 해시는 그게 안 될 때 꺼내는 도구입니다.
2. 전처리를 설계합니다 — 접두사 해시 배열 \(h\)와 거듭제곱 배열 \(pw\)를
   \(O(N)\)에 만들어 두면 임의 구간 해시가 \(O(1)\)입니다.
3. 충돌 위험을 평가합니다 — 비교 횟수가 많거나(생일 역설) 저격 입력이
   가능한 환경이면 이중 해시 또는 무작위 밑으로.
4. 해시 일치를 "같다"로 단정해도 되는 문제인지 정합니다 — 확신이
   필요하면 일치 시 실제 비교로 한 번 검증하는 절충도 가능합니다.

3. 자주 하는 실수

• 구간 해시 뺄셈에서 음수. $\text{hash}(l, r) = h_r - h_{l-1} \cdot
  p^{r-l+1}$은 모듈러 아래에서 음수가 될 수 있습니다.

long long get(int l, int r) {                  // 1-indexed [l, r]
    long long v = (h[r] - h[l-1] * pw[r-l+1]) % MOD;
    return (v + MOD * MOD % MOD + MOD) % MOD;  // 음수 보정 필수
}

• pw를 매번 거듭제곱으로 계산. 질의마다 \(O(\log N)\) 거듭제곱을 하면
  아깝고, 반복문 거듭제곱이면 \(O(N)\)이라 시간 초과입니다. 전처리 배열로.
• 충돌 확률 계산 없이 단일 해시. 비교가 \(10^9\)번 수준이면 모듈러
  \(10^9{+}7\) 하나로는 생일 역설로 충돌이 기대됩니다. 서로 다른 모듈러
  두 개를 쌍으로 쓰세요.
• 해시 집합 크기를 "서로 다른 문자열 개수"로 단정 — 충돌 한 번이면
  오답입니다. 개수를 세는 문제일수록 이중 해시가 필수입니다.
• 곱셈 중간값 오버플로. C++에서 h * pw는 모듈러를 곱하기 전에
  넘칠 수 있습니다. 두 인자를 먼저 % MOD 해 두고 long long 곱으로
  유지하거나 __int128을 쓰세요. 파이썬은 무한 정수라 안전합니다.

4. 연습 방법

이 페이지 오른쪽의 추천 문제는 쉬운 것부터 어려운 것 순입니다. 단순 해시
맵 분류 → 패턴 검색 → 구간 해시 질의 순서로 전처리가 점점 본격화됩니다.

각 문제에서 "비교 횟수가 몇 번인지" 를 먼저 계산해 해시가 정말 필요한지
판정하고, 필요하다면 충돌 확률까지 한 줄로 적어 보세요. 3문제 이상 풀어
클리어하면 레이팅의 CLASS 보너스에 반영됩니다.