해싱으로 문자열 비교 — Rabin-Karp와 롤링 해시

두 문자열이 같은지 확인하려면 한 글자씩 비교해야 할까요? 해시를 쓰면 O(1)에 비교할 수 있지 않을까요?

Rabin-Karp란

Rabin-Karp 알고리즘 은 해시 함수를 이용해 문자열 매칭을 수행하는 알고리즘입니다. 텍스트의 모든 길이-M 부분 문자열의 해시를 패턴의 해시와 비교하되, 롤링 해시(rolling hash) 로 해시 계산을 O(1)에 수행하는 것이 핵심입니다.

왜 필요한가

KMP는 단일 패턴 매칭에 최적이지만, 여러 패턴을 동시에 검색 할 때는 Rabin-Karp가 더 효율적입니다. 패턴마다 해시를 미리 계산해두고, 텍스트의 각 위치에서 해시만 비교하면 되기 때문입니다.

**다중 패턴 매칭 **: 여러 키워드를 동시에 검색
** 표절 탐지 **: 문서 간 유사한 구절 찾기
** 파일 동기화 **: rsync의 롤링 체크섬

동작 원리

해시 함수

문자열을 숫자로 변환합니다. 다항 해시가 가장 흔합니다.

PLAINTEXT

hash("abc") = 'a' × base² + 'b' × base¹ + 'c' × base⁰

보통 base = 31 또는 131, mod = 큰 소수를 사용합니다.

롤링 해시

윈도우를 한 칸 이동할 때, 빠지는 문자의 기여를 빼고 들어오는 문자의 기여를 더합니다.

PLAINTEXT

텍스트: a b c d e
윈도우 크기: 3

hash("abc") = a × 31² + b × 31¹ + c × 31⁰

한 칸 이동 후:
hash("bcd") = (hash("abc") - a × 31²) × 31 + d × 31⁰

이전 해시에서 O(1) 연산으로 새 해시를 구합니다.

알고리즘 흐름

패턴의 해시를 계산합니다
텍스트의 첫 윈도우 해시를 계산합니다
해시가 같으면 실제 문자를 비교합니다 (spurious hit 방지)
롤링 해시로 다음 윈도우의 해시를 O(1)에 갱신합니다
3~4를 반복합니다

코드 예제 — Java

JAVA

public class RabinKarp {
    private static final long BASE = 31;
    private static final long MOD = 1_000_000_007;

    public List<Integer> search(String text, String pattern) {
        List<Integer> result = new ArrayList<>();
        int n = text.length(), m = pattern.length();
        if (n < m) return result;

        // 패턴 해시 계산
        long patternHash = computeHash(pattern, m);

        // 첫 윈도우 해시 계산
        long textHash = computeHash(text, m);

        // base^(m-1) mod MOD — 롤링 시 사용
        long highPow = 1;
        for (int i = 0; i < m - 1; i++) {
            highPow = (highPow * BASE) % MOD;
        }

        for (int i = 0; i <= n - m; i++) {
            // 해시 비교 → 같으면 실제 비교
            if (textHash == patternHash && verify(text, i, pattern)) {
                result.add(i);
            }

            // 롤링 해시: 다음 윈도우로 이동
            if (i < n - m) {
                textHash = rollHash(textHash, text.charAt(i), text.charAt(i + m), highPow);
            }
        }
        return result;
    }

    private long computeHash(String s, int len) {
        long hash = 0;
        for (int i = 0; i < len; i++) {
            hash = (hash * BASE + s.charAt(i)) % MOD;
        }
        return hash;
    }

    private long rollHash(long oldHash, char removeChar, char addChar, long highPow) {
        long hash = (oldHash - removeChar * highPow % MOD + MOD) % MOD;
        hash = (hash * BASE + addChar) % MOD;
        return hash;
    }

    // 해시 충돌 대비 실제 문자 비교
    private boolean verify(String text, int start, String pattern) {
        for (int j = 0; j < pattern.length(); j++) {
            if (text.charAt(start + j) != pattern.charAt(j)) return false;
        }
        return true;
    }
}

다중 패턴 매칭

Rabin-Karp의 진가는 여러 패턴을 동시에 검색할 때 발휘됩니다.

JAVA

public Set<Integer> multiPatternSearch(String text, Set<String> patterns) {
    Set<Integer> result = new HashSet<>();
    int n = text.length();

    // 패턴 길이별로 그룹핑
    Map<Integer, Set<Long>> hashByLength = new HashMap<>();
    for (String p : patterns) {
        int len = p.length();
        hashByLength
            .computeIfAbsent(len, k -> new HashSet<>())
            .add(computeHash(p, len));
    }

    // 각 길이별로 롤링 해시 수행
    for (var entry : hashByLength.entrySet()) {
        int m = entry.getKey();
        Set<Long> targetHashes = entry.getValue();

        if (n < m) continue;

        long hash = computeHash(text, m);
        long highPow = 1;
        for (int i = 0; i < m - 1; i++) highPow = (highPow * BASE) % MOD;

        for (int i = 0; i <= n - m; i++) {
            if (targetHashes.contains(hash)) {
                result.add(i); // 실제로는 verify도 필요
            }
            if (i < n - m) {
                hash = rollHash(hash, text.charAt(i), text.charAt(i + m), highPow);
            }
        }
    }
    return result;
}

이중 해시로 충돌 줄이기

단일 해시는 충돌 확률이 있습니다. 두 개의 서로 다른 모듈러를 사용하면 충돌 확률을 극적으로 줄일 수 있습니다.

JAVA

// 이중 해시 — 두 해시가 모두 같아야 매칭
private static final long MOD1 = 1_000_000_007;
private static final long MOD2 = 998_244_353;
private static final long BASE1 = 31;
private static final long BASE2 = 37;

// 충돌 확률: 1/(MOD1 × MOD2) ≈ 10^(-18) → 사실상 0

시간 복잡도

경우	시간 복잡도	설명
평균	O(N + M)	해시 충돌이 적을 때
최악	O(N × M)	모든 위치에서 충돌 시
다중 패턴 (k개)	O(N × k + 총 패턴 길이)	패턴 길이가 같으면 O(N)

백엔드/실무 연결

Git Content-Addressable Storage

Git은 파일 내용을 SHA-1 해시로 식별합니다. 같은 내용의 파일은 같은 해시를 가지므로 중복 저장이 없습니다.

BASH

# Git 내부에서 파일의 해시 확인
git hash-object README.md
# → e69de29bb2d1d6434b8b29ae775ad8c2e48c5391

이것이 "content-addressable" 저장소입니다. 내용이 주소(해시)가 되는 것입니다.

rsync의 롤링 체크섬

rsync는 파일 동기화 시 변경된 부분만 전송합니다. 원격 파일의 블록별 해시를 미리 받아두고, 로컬 파일에서 롤링 해시로 같은 블록을 찾아 변경된 부분만 전송합니다. Rabin-Karp와 같은 원리입니다.

표절 탐지 시스템

문서에서 일정 길이의 n-gram을 롤링 해시로 추출하고, 다른 문서의 해시와 비교하여 유사한 구절을 찾습니다. Turnitin 같은 표절 탐지 서비스의 기반 기술입니다.

해시 기반 캐시 키

Spring의 @Cacheable에서 메서드 인자를 해시하여 캐시 키를 만드는 것도, 문자열(인자의 toString)을 해시로 비교하는 관점에서 같은 원리입니다.

주의할 점

해시 충돌을 무시하는 실수

Rabin-Karp에서 해시값이 같다고 무조건 같은 문자열은 아닙니다. 해시가 일치하면 반드시 문자열을 직접 비교하는 검증 단계가 필요합니다. 이를 빠뜨리면 오답이 나옵니다.

롤링 해시에서 음수 모듈러

해시 계산 중 뺄셈이 포함되면 결과가 음수가 될 수 있습니다. (hash - removed + MOD) % MOD처럼 MOD를 더한 뒤 나머지를 구해야 합니다.

정리

Rabin-Karp 는 해시 함수로 문자열 매칭을 수행하는 알고리즘입니다
롤링 해시 로 윈도우 이동 시 해시를 O(1)에 갱신합니다
평균 O(N + M)이지만, 해시 충돌 시 최악 O(N × M)입니다
이중 해시 로 충돌 확률을 사실상 0으로 만들 수 있습니다
다중 패턴 매칭 에서 KMP보다 효율적입니다
Git의 content-addressable storage, rsync, 표절 탐지 등 실무에서 광범위하게 활용됩니다