해시테이블(Hash Table)

해싱의 동기: TLB와의 유사성

CPU가 연산을 할 때 메모리에서 데이터를 가져와야 한다. 현대 컴퓨터는 각 프로세스마다 가상 메모리주소 를 부여하는데, 이는 메모리 관리 효율성과 보안상 장점이 있다.

하지만 CPU가 실제 연산을 할 때는 가상 주소를 물리 주소로 변환해야 하는 문제가 발생한다. 이를 해결하기 위해 TLB(Translation Lookaside Buffer) 를 사용한다.

TLB는 가상 주소와 물리 주소를 매핑한 테이블로, 빠른 주소 변환을 제공한다. 해싱 알고리즘도 이와 유사한 방식으로 작동해서 기존 검색 알고리즘보다 훨씬 빠른 성능을 보인다.

해싱의 시간 복잡도 : 평균 O(1) 최악 O(n)

해싱이 필요한 이유

예시: 처음으로 반복되는 문자 찾기

문자열에서 처음으로 반복되는 문자를 찾는 알고리즘을 생각해보자.

방법 1: 이중 반복문

for i in range(len(s)):
    for j in range(i+1, len(s)):
        if s[i] == s[j]:
            return s[i]

시간 복잡도: O(n²)

방법 2: 배열 카운터 사용

count = [0] * 128  # ASCII 문자 개수
for char in s:
    count[ord(char)] += 1
    if count[ord(char)] == 2:
        return char

시간 복잡도: O(n)

문자의 경우 ASCII 코드로 유한한 범위를 가지므로 미리 배열 크기를 알 수 있다. 하지만 자연수처럼 가능한 전체 집합 U의 크기가 실제 사용되는 집합 K의 크기보다 월등히 큰 경우에는 해싱이 사용된다.

해시테이블의 구성 요소

1. 해시테이블 (Hash Table)

해싱 알고리즘에서 실제 데이터가 저장되는 자료구조다.

• 키(Key): 데이터를 식별하는 고유한 값
• 값(Value): 실제 저장되는 데이터
• 인덱스 기반 접근: 평균 O(1) 시간에 데이터 접근 가능

2. 해시함수 (Hash Function)

해싱에서 가장 핵심적인 요소로, 키를 해시테이블의 인덱스로 변환하는 함수다.

해시함수의 중요한 특성:

• 빠른 연산: 해시함수 자체가 느리면 해싱의 장점이 사라진다
• 균등 분포: 데이터를 테이블 전체에 고르게 분산시켜야 한다
• 결정적: 같은 입력에 대해 항상 같은 출력을 내야 한다
• 충돌 최소화: 서로 다른 키가 같은 인덱스로 매핑되는 것을 최소화해야 한다

일반적인 해시함수 예시:

• Division Method: h(k) = k mod m
• Multiplication Method: h(k) = floor(m * (k*A mod 1))
• Universal Hashing

충돌(Collision) 처리

서로 다른 두 키가 같은 인덱스로 변환되는 현상을 충돌이라고 한다.

충돌 해결 방법

1. 체이닝(Chaining)

• 같은 인덱스에 매핑되는 모든 원소를 연결리스트로 저장하는 방법이다
• 구현이 간단하고 테이블이 가득 차도 성능 저하가 완만하다
• 하지만 추가 메모리가 필요하다

2. 개방 주소법(Open Addressing)

• 충돌 발생 시 다른 빈 슬롯을 찾아 저장하는 방법이다
• 선형 탐사(Linear Probing), 이차 탐사(Quadratic Probing), 이중 해싱(Double Hashing) 등이 있다
• 메모리는 효율적이지만 클러스터링 문제가 발생할 수 있다

해싱의 장단점

장점

• 빠른 접근: 평균 O(1) 시간에 삽입, 삭제, 검색이 가능하다
• 유연성: 다양한 데이터 타입을 키로 사용할 수 있다
• 메모리 효율성: 필요한 만큼만 공간을 사용한다 (체이닝의 경우)

단점

• 최악 시간 복잡도: O(n) (모든 키가 같은 인덱스로 해싱되는 경우)
• 순서 보장 없음: 데이터가 삽입 순서대로 저장되지 않는다
• 해시함수 의존성: 좋지 않은 해시함수를 사용하면 성능이 급격히 저하된다
• 공간 오버헤드: 충돌 처리를 위한 추가 공간이 필요하다

해싱 vs 다른 자료구조

| 자료구조 | 평균 검색 | 평균 삽입 | 평균 삭제 | 공간 복잡도 |
| -------- | -------- | -------- | -------- | ------ |
| 해시테이블 | O(1) | O(1) | O(1) | O(n) |
| 이진 탐색 트리 | O(log n) | O(log n) | O(log n) | O(n) |
| 배열 (정렬된) | O(log n) | O(n) | O(n) | O(n) |
| 연결리스트 | O(n) | O(1) | O(n) | O(n) |

결론

해싱은 공간을 조금 더 사용하는 대신 시간 복잡도를 대폭 줄이는 트레이드오프를 제공한다. 좋은 해시함수와 적절한 충돌 처리 방법을 선택한다면, 대부분의 실용적인 상황에서 매우 효율적인 성능을 얻을 수 있다.

특히 데이터의 빈번한 검색, 삽입, 삭제가 필요하고 데이터의 순서가 중요하지 않은 경우에 해시테이블이 최적의 선택이 될 수 있다. 그렇지 않다면 이진 트리와 같은 검색과 삽입, 삭제가 적절히 빠른 자료구조를 사용하는게 훨씬 이득이니까 말이다.