C++에서 다항식 롤링 해시 구현 및 해시 테이블 활용하기

---

1. 다항식 롤링 해시란?

다항식 롤링 해시는 문자열의 각 문자를 일정한 베이스(예: 131, 257 등) 를 이용해 하나의 정수로 변환하는 방식입니다.
예를 들어, 문자열 s에 대해 해시값을 아래와 같이 계산할 수 있습니다.

하지만 실제 구현에서는 오버플로우와 연산 효율을 고려하여 보통 누적 방식으로 계산합니다.

코드로 살펴보기

const int TABLE_SIZE = 100003; // 큰 소수를 사용하는 것이 좋습니다.

int getHash(const string &s) {
    unsigned long long hash_val = 0;
    for (char c : s) {
        hash_val = hash_val * 131 + c;  // 131은 베이스로 자주 사용되는 소수입니다.
    }
    return hash_val % TABLE_SIZE;       // 해시 테이블의 인덱스 범위 내로 제한
}

• 설명:
  • hash_val을 0에서 시작하여 문자열의 각 문자를 순회하면서 hash_val * 131 + c로 업데이트합니다.
  • 최종적으로 TABLE_SIZE로 나눈 나머지를 반환하여, 해시 테이블 내에서 사용할 인덱스를 결정합니다.

---

2. 해시 테이블 구현 및 충돌 처리

해시 테이블은 해시 함수를 이용하여 데이터를 빠르게 저장하고 찾는 자료구조입니다.
문자열의 해시값을 인덱스로 사용하여 데이터를 저장하는데, 서로 다른 문자열이 같은 인덱스를 갖는 경우 충돌(Collision) 이 발생할 수 있습니다.

체이닝(Chaining) 방식으로 충돌 해결하기

아래는 체이닝 기법을 사용하여 문자열 집합의 교집합 문제를 해결하는 예제입니다.
첫 번째 집합의 문자열을 해시 테이블에 저장하고, 두 번째 집합의 문자열을 검색하여 교집합 개수를 계산합니다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

const int TABLE_SIZE = 100003; // 해시 테이블 크기

// 다항식 롤링 해시 함수 (베이스: 131)
int getHash(const string &s) {
    unsigned long long hash_val = 0;
    for (char c : s) {
        hash_val = hash_val * 131 + c;
    }
    return hash_val % TABLE_SIZE;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        int N, M;
        cin >> N >> M;
        
        // 해시 테이블: 각 버킷은 문자열들을 저장하는 벡터입니다.
        vector<vector<string>> hashTable(TABLE_SIZE);
        
        string str;
        // 첫 번째 집합의 문자열들을 해시 테이블에 저장합니다.
        for (int i = 0; i < N; i++) {
            cin >> str;
            int idx = getHash(str);
            hashTable[idx].push_back(str);
        }
        
        int answer = 0;
        // 두 번째 집합의 문자열들을 확인하며 교집합을 찾습니다.
        for (int i = 0; i < M; i++) {
            cin >> str;
            int idx = getHash(str);
            // 해당 버킷 내에서 문자열이 존재하는지 선형 탐색합니다.
            for (const auto &s : hashTable[idx]) {
                if (s == str) {
                    answer++;
                    break; // 집합 내 중복은 없으므로, 한 번 찾으면 바로 종료합니다.
                }
            }
        }
        
        cout << "#" << t << " " << answer << "\n";
    }
    
    return 0;
}

• 핵심 포인트:
  • 해시 테이블 구조:
    vector<vector<string>> 형태로 각 인덱스(버킷)에 여러 문자열을 저장할 수 있도록 하여, 충돌이 발생해도 체이닝 방식으로 처리합니다.
  • 문자열 저장 및 검색:
    첫 번째 집합의 각 문자열을 해시 함수로 계산한 인덱스에 저장하고, 두 번째 집합의 문자열 역시 같은 방식으로 인덱스를 구해 해당 버킷에서 검색합니다.

---

3. 해시 충돌 예측 및 예방

충돌 가능성

• 이론적으로:
  모든 해시 함수는 무한한 입력을 유한한 범위로 매핑하기 때문에 충돌은 언제든지 발생할 수 있습니다.
• 실제로:
  • 베이스 값 (예: 131): 소수를 사용하면 해시 값이 균등하게 분포될 가능성이 높습니다.
  • 테이블 크기 (TABLE_SIZE): 충분히 큰 소수(예: 100003)를 사용하면 평균적으로 각 버킷에 저장되는 항목 수가 매우 적어져 충돌 확률을 낮출 수 있습니다.
  • 입력 데이터의 특성: 입력 데이터가 무작위라면 충돌이 적게 발생하지만, 특정 패턴이나 유사한 문자열들이 많다면 충돌 가능성이 올라갑니다.

예방 및 처리 방법

• 예방:
  • 적절한 베이스와 모듈로 값을 선택합니다.
  • 경우에 따라 이중 해싱(Double Hashing) 등의 기법을 사용할 수도 있습니다.
• 처리:
  • 위 예제처럼 체이닝(Chaining) 방식을 사용하면 같은 인덱스에 여러 문자열을 저장하고, 선형 탐색을 통해 검색할 수 있습니다.
  • 또는, 오픈 어드레싱(Open Addressing) 방식도 있지만, 체이닝이 구현하기 더 쉽습니다.