해시테이블(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) |

결론

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

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

%%

해싱

CPU가 연산을 할때 메모리(혹은 디스크)에서 자료를 가져와 연산을 한다. x + y를 연산할 때 x와 y의 값을 메모리에서 가져온다.

요즘 컴퓨터는 각 프로세스마다 변수에게 가상 메모리 주소를 부여하고 사용하는데 (메모리 관리 효율성과 보안에 장점이 있다고 한다.), 그러면 cpu가 각 변수들을 가지고 연산을 할 때 마다 실제 물리 메모리 주소를 찾아야 한다. 그래서 TLB(Translation Lookaside Buffer) 라는 것을 사용하는데, TLB에는 간단히 변수의 가상 주소와 그에 맞는 물리 주소가 적혀있는 테이블인데, TLB에서 물리 주소가 있으면 굳이 다른 방법으로 찾을 필요 없이 바로 가져올 수 있다. 이 TLB가 작동하는 방식은 매우 빠른데 해싱 알고리즘도 이와 비슷하고 기존의 검색 알고리즘보다 훨씬 빠르다. 해싱은 최악의 경우 복잡도는 O(n) 이지만 **평균 복잡도는 O(1)**이다.

'해싱'이란?

주어진 문자열에서, 처음으로 반복되는 글자를 출력하는 알고리즘을 고안해보자.

1. 일단 for문 중첩을 통해 구현 할 수 있을것이다. $O(n^2)$
2. 더 나은 방법으로는 ACII코드 개수 만큼의 배열을 만들고, ACSCII값을 기준으로 그 글자가 등장할 때 마다 해당 인덱스의 값을 1 올려서 카운터가 2가 되는 글자를 찾으면 반환하는 방법으로도 구현할 수 있다. $O(n)$

글자의 경우 어쨋든 경우의 수가 유한하기 때문에 미리 테이블의 크기를 미리 알 수 있지만, 만약 자연수를 가지고 똑같은 알고리즘을 구현하려면? 자연수의 경우처럼 가능한 경우의 전체 집합 U의 크기가 실제 사용되는 집합 K의 크기보다 월등히 큰 경우에는 해싱이 사용된다.

해시 테이블

해시 테이블은 해싱 알고리즘에서 실제 데이터가 저장되어있는 곳이다. 키(인덱스) 와 값(데이터) 의 쌍으로 이루어져 있고, 인덱스를 기반으로 아주 빠르게 (평균 O(1) 복잡도)데이터를 가져올 수 있다.

해시 함수

해싱에서 가장 중요한 요소로, 데이터들을 해시 테이블의 인덱스로 적절히 변환시키는 함수다. (키를 인덱스로 변환)

중요한것은 해싱의 목적 자체가 미리 테이블을 만들어두어 공간을 많이 차지하는 대신, 데이터 처리에 대한 시간 복잡도를 줄이는 것이기 때문에, 키를 인덱스로 변환하는 과정이 다른 알고리즘보다 빨라야 한다는 점이다. 그렇지 않다면 이진 트리와 같은 검색과 삽입,삭제가 적절히 빠른 자료구조를 사용하는게 훨씬 이득이니까 말이다.

충돌

그리고 효율적인 해시 함수는 충돌을 최소화 해야한다. 충돌이란, 다른 두 키가 같은 인덱스로 변환되는 것인데 보통은 이럴때 체이닝 이라고 해서, 같은 인덱스에 중복되는 데이터를 저장하기도 한다. 잘 만들어진 해시함수는 충돌이 적게 발생하고, 그래서 같은 인덱스에 데이터가 중첩되어 있다고 해도 그렇게 많은 시간이 소요되지는 않는다.

%%