3 Inseok Kong Schedule

Q-14. 해시 테이블이란 무엇인가요?

해시 테이블은 해시 함수로 키를 배열 위치로 바꿔 삽입, 삭제, 조회를 평균 O(1)에 처리하는 자료구조이다.

면접 답변

해시 테이블은 키를 해시 함수에 넣어 배열의 인덱스로 바꾸고, 그 위치에 값을 저장하는 자료구조입니다. 위치를 바로 계산하므로 삽입, 삭제, 조회가 평균 O(1)에 끝납니다. 다만 서로 다른 키가 같은 위치로 가는 충돌은 피할 수 없어서 체이닝이나 개방 주소법으로 처리하고, 원소가 많아지면 배열을 키워 다시 배치합니다. 충돌이 한곳에 몰리면 최악의 경우 O(n)까지 느려지고, 순서가 유지되지 않아 범위 검색에도 맞지 않습니다. 예를 들어 Python의 dict가 해시 테이블입니다. 이 자체는 자료구조 질문이지만 머신러닝에서도 고차원 범주형 변수를 고정 길이 벡터로 바꾸는 feature hashing이나, 근사 최근접 이웃 검색에 쓰는 LSH에서 같은 아이디어를 씁니다.

자세한 설명

구조

해시 함수(hash function) \(h\)는 임의의 키를 정수로 바꾼다. 크기 \(m\)인 배열(버킷 배열)에서 키 \(k\)의 위치는 다음과 같다.

\[\text{index}(k) = h(k) \bmod m\]

정렬된 배열의 이진 탐색이 \(O(\log n)\), 연결 리스트의 탐색이 \(O(n)\)인 것과 달리, 해시 테이블은 비교를 거듭하지 않고 위치를 계산한다. 좋은 해시 함수는 빠르고, 같은 키에 항상 같은 값을 내며, 키를 버킷에 고르게 퍼뜨린다.

충돌과 그 처리

키의 종류가 버킷보다 많으면 비둘기집 원리에 따라 충돌(collision)이 생긴다. \(h(k) = k \bmod 7\)이면 10과 17은 모두 3번 버킷으로 간다.

방식 동작 특징 사용 예
체이닝(separate chaining) 버킷마다 리스트를 두고 이어 붙인다 구현이 단순하고 부하율이 1을 넘어도 동작한다 Java HashMap
개방 주소법(open addressing) 규칙에 따라 배열의 다음 빈자리를 찾는다 포인터가 없어 캐시 효율이 좋지만 부하율에 민감하다 Python dict

부하율과 재해싱

원소 수를 \(n\)이라 할 때 부하율(load factor)은 \(\alpha = n / m\)이다. 해시가 균일하다는 가정에서 체이닝의 평균 조회 비용은 \(O(1 + \alpha)\)이다. 개방 주소법에서 없는 키를 찾을 때의 기대 탐사 횟수는 많아야 \(1 / (1 - \alpha)\)이다.

부하율 \(\alpha\) 0.5 0.75 0.9
기대 탐사 횟수의 상한 2 4 10

그래서 부하율이 임계값을 넘으면 더 큰 배열을 만들어 모든 키를 다시 넣는다(rehashing). 한 번의 비용은 \(O(n)\)이지만 배열을 배수로 키우면 삽입의 분할 상환(amortized) 비용은 \(O(1)\)이다. 임계값은 구현마다 다르며, Java HashMap의 기본값은 0.75이다.

복잡도와 한계

연산 평균 최악
조회, 삽입, 삭제 \(O(1)\) \(O(n)\)
최솟값, 범위 검색 \(O(n)\) \(O(n)\)

순서가 필요하면 균형 이진 탐색 트리처럼 범위 검색을 \(O(\log n + k)\)에 처리하는 구조가 낫다. 여기서 \(k\)는 결과의 개수이다.

머신러닝과의 연결: feature hashing

어휘가 수백만 개인 텍스트나 범주형 변수는 단어 사전을 만들어 두면 메모리가 많이 들고, 처음 보는 값도 처리하기 어렵다. feature hashing은 사전 없이 해시값을 바로 벡터의 인덱스로 쓴다.

import zlib
import numpy as np

def hash_features(tokens, dim=8):
    v = np.zeros(dim)
    for tok in tokens:
        h = zlib.crc32(tok.encode())
        sign = 1 if (h >> 31) == 0 else -1   # 충돌의 편향을 줄이는 부호
        v[h % dim] += sign
    return v

print(hash_features("free money free offer".split()))
# [ 2.  0.  0.  0. -1.  0.  1.  0.]

Python 내장 hash()는 문자열에 대해 프로세스마다 값이 달라질 수 있어 학습과 추론에서 인덱스가 어긋난다. 그래서 위처럼 고정된 해시 함수를 쓴다. 충돌하는 특징은 구별되지 않으므로 차원 수와 정확도 사이의 절충이 있고, 벡터에서 원래 단어를 되찾을 수 없어 해석도 어려워진다.

관련 개념

  • Locality-Sensitive Hashing(LSH): 일반 해시 테이블과 반대로 비슷한 입력이 일부러 같은 버킷에 충돌하도록 설계한 해싱이다. 후보를 빠르게 좁힐 수 있어 근사 최근접 이웃(approximate nearest neighbours) 검색에 쓴다.
  • 암호학적 해시 함수: SHA-256처럼 충돌을 찾거나 입력을 역산하기 어렵게 설계한 함수이다. 해시 테이블에는 보통 그보다 빠른 비암호학적 함수를 쓴다.
  • 블룸 필터(Bloom filter): 여러 해시 함수와 비트 배열로 집합 소속 여부를 판정하는 구조이다. 메모리가 적게 들지만 거짓 양성이 있을 수 있다.
  • 임베딩 테이블: 범주를 벡터로 바꾸는 조회 테이블이다. 범주가 매우 많을 때는 해시로 인덱스를 줄인 뒤 임베딩을 학습하기도 한다.

꼬리 질문

Q. 해시 테이블이 항상 O(1)인가요? 아니다. O(1)은 해시가 고르게 퍼진다는 가정 아래의 평균이다. 모든 키가 한 버킷에 몰리면 O(n)이 되며, Java 8 이후의 HashMap처럼 긴 체인을 트리로 바꿔 최악을 \(O(\log n)\)으로 낮추는 구현도 있다.

Q. 해시 테이블과 균형 이진 탐색 트리 중 무엇을 고르나요? 정확한 키 조회만 필요하면 해시 테이블이 유리하다. 정렬된 순회나 범위 검색이 필요하거나 최악의 경우 시간을 보장해야 하면 트리가 낫다.

Q. feature hashing에서 충돌은 얼마나 문제가 되나요? 차원이 특징 수에 비해 작을수록 충돌이 늘어 성능이 떨어질 수 있다. 부호 해시로 편향을 줄일 수 있지만 충돌 자체가 없어지지는 않으므로, 차원 수는 검증 집합에서 확인해 정한다.