📌 개요

해시(Hash)는 키(Key)를 해시 함수(Hash Function)로 변환하여 빠르게 값을 찾는 자료구조입니다.
특히 문자열 해싱(String Hashing) 은 문자열을 정수 값으로 변환하여 검색, 비교 연산을 효율적으로 수행하는 방법입니다.

✅ 해시의 주요 특징

검색, 삽입, 삭제 연산이 평균 O(1)
해시 충돌(Collision)을 해결하는 기법 필요
문자열 비교 연산을 O(N) → O(1)로 최적화 가능 (문자열 해싱)

📌 해시 테이블 (Hash Table)

1. 해시 테이블 개념

해시 테이블(Hash Table)은 키(Key) → 값(Value) 형태로 데이터를 저장하며, 해시 함수(Hash Function) 를 이용해 데이터를 저장할 위치를 결정합니다.

2. Python 딕셔너리(Dictionary) 사용

Python에서 기본적으로 제공하는 dict 자료구조는 해시 테이블 기반으로 동작합니다.

hash_map = {}  # 딕셔너리 생성
hash_map["name"] = "Alice"
hash_map["age"] = 25
hash_map["city"] = "New York"

print(hash_map["name"])  # 출력: Alice
print(hash_map["age"])   # 출력: 25

✅ 딕셔너리는 O(1) 시간 복잡도로 빠른 검색, 삽입, 삭제 가능

📌 문자열 해싱 (String Hashing)

문자열 해싱은 문자열을 해시 값으로 변환하여 효율적인 검색 및 비교를 수행하는 기법입니다.

1. 문자열 해싱의 필요성

일반적으로 두 개의 문자열을 비교하는 연산은 O(N) 시간이 걸림
해시 값을 이용하면 O(1) 시간 내에 문자열 비교 가능
문자열 검색, 중복 탐지, 롤링 해시(Rolling Hash) 등에 활용

📌 1. 기본 문자열 해싱 (Polynomial Hashing)

문자열 "hello" 를 해싱하는 과정: H=(h0×p0+h1×p1+h2×p2+...+hn×pn)mod MH = (h_0 × p^0 + h_1 × p^1 + h_2 × p^2 + ... + h_n × p^n) \mod M

h_i: 문자 ASCII 값
p: 소수(보통 31 또는 37 사용)
M: 큰 소수 (충돌 방지)

📌 Python 코드

def polynomial_hash(s, p=31, M=10**9+9):
    hash_value = 0
    power = 1  # p^0 = 1

    for char in s:
        hash_value = (hash_value + (ord(char) - ord('a') + 1) * power) % M
        power = (power * p) % M  # p^i 계산

    return hash_value

print(polynomial_hash("hello"))  # 문자열의 해시 값 출력

✅ 시간 복잡도: O(N) (N은 문자열 길이)
✅ 해시 충돌을 방지하기 위해 M을 큰 소수로 설정

📌 2. 해시를 활용한 문자열 비교 (O(1) 비교)

문자열을 비교할 때 일반적인 O(N) 비교 대신 O(1) 비교 가능

s1 = "hello"
s2 = "world"

if polynomial_hash(s1) == polynomial_hash(s2):
    print("같은 문자열입니다.")
else:
    print("다른 문자열입니다.")

✅ 두 문자열이 다르면 해시 값도 다르게 나오므로 빠르게 비교 가능
✅ 충돌(Collision) 가능성이 있지만 확률적으로 매우 낮음

📌 3. 롤링 해시 (Rolling Hash)

✅ 부분 문자열 검색에 유용한 해시 기법
✅ 문자열을 슬라이딩 윈도우처럼 이동하며 해시 값 갱신 (O(1) 업데이트 가능)
✅ 라빈-카프 알고리즘(Rabin-Karp Algorithm)에서 사용됨

📌 롤링 해시 공식

문자열 S의 구간 [L, R] 의 해시 값을 다음과 같이 계산할 수 있음: H[L,R]=(H[R]−H[L−1]×p(R−L+1))mod MH[L, R] = (H[R] - H[L-1] \times p^{(R-L+1)}) \mod M

📌 Python 코드

def rolling_hash(s, p=31, M=10**9+9):
    n = len(s)
    hash_values = [0] * (n + 1)
    power = [1] * (n + 1)  # p^i 값 저장

    for i in range(1, n + 1):
        hash_values[i] = (hash_values[i - 1] + (ord(s[i - 1]) - ord('a') + 1) * power[i - 1]) % M
        power[i] = (power[i - 1] * p) % M

    return hash_values, power

def get_substring_hash(hash_values, power, L, R, M=10**9+9):
    return (hash_values[R] - hash_values[L - 1] * power[R - L + 1]) % M

s = "hellohello"
hash_values, power = rolling_hash(s)

# "hello"의 해시 값 비교
hash1 = get_substring_hash(hash_values, power, 1, 5)
hash2 = get_substring_hash(hash_values, power, 6, 10)

print(hash1 == hash2)  # 출력: True (같은 부분 문자열)

✅ 시간 복잡도: O(N) (초기 해싱) + O(1) (부분 문자열 비교)
✅ 효율적인 부분 문자열 탐색 가능 (검색 알고리즘에 활용 가능)

📌 해시 테이블과 문자열 해싱 비교

기법	목적	시간 복잡도	주요 활용
해시 테이블	키-값 저장	O(1)	데이터 저장, 검색
문자열 해싱	문자열을 숫자로 변환	O(N)	문자열 비교, 검색
롤링 해시	부분 문자열 검색	O(1)	문자열 패턴 매칭

✅ 문자열 해싱은 해시 테이블과 결합하여 빠른 검색 가능
✅ 라빈-카프 알고리즘(Rabin-Karp)에서 활용

📌 해시 자료구조의 장단점

✅ 장점

빠른 데이터 접근 (O(1))
검색, 삽입, 삭제 연산이 빠름
문자열 비교를 O(1)로 최적화 가능 (문자열 해싱 활용)

❌ 단점

충돌(Collision) 문제 발생 가능
해시 함수가 비효율적이면 성능 저하
해시 충돌 방지를 위해 추가적인 처리(체이닝, 오픈 어드레싱)가 필요

📌 결론

해시는 빠른 검색을 위한 필수 자료구조 (딕셔너리, 집합 등)
문자열 해싱을 활용하면 O(N) 문자열 비교 → O(1)로 최적화 가능
롤링 해시는 부분 문자열 탐색에 유용하며, 검색 알고리즘(라빈-카프)에서 사용됨
충돌 방지를 위한 적절한 해시 함수 선택이 중요

🚀 해시는 알고리즘 문제 해결에서 필수적으로 사용되는 자료구조이므로 반드시 익혀야 합니다!

728x90