해시 테이블(Hash Table)

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

해시 테이블(Hash Table)이란?

키를 값에 매핑할 수 있는 구조인 "연관 배열 추가"에 사용되는 자료구조이며 해시 테이블은 해시함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 사용한다. - 위키피디아

연관 배열이란

키 하나와 값 하나가 연관되어 있으며 키를 통해 연관된 값을 얻을 수 있다. 맵(Map), 사전(Dictionary)라고 부르기도 한다. 연관 배열은 CRUD(Create, Read, Update, Delete) 연산을 지원한다.

버킷(bucket)과 슬롯(slot)

일반적으로 데이터를 저장하는 공간으로 일컫지만 엄밀하게 버킷은 데이터가 저장되는 전체 공간, 슬롯은 그 버킷 내부에 데이터가 저장되는 단위 객체를 의미하는 듯하다.

시간복잡도

특정 해시함수로 해싱한 index 값에 저장하므로 해시충돌 등의 이슈가 없다면 키-값의 대응은 1:1 관계이다. 따라서, 최적의 경우 O(1)을 만족한다.

해시 함수(Hash Function)

해시 테이블의 고유 인덱스를 결정하는 중요한 함수이다. 정확히는 임의 크기 데이터를 고정 크기 값으로 매핑하기 위해 사용할 수 있는 함수다. 해시함수를 사용해 인덱스를 구성하는 과정을 해싱(Hashing)이라고 한다. 정보에 대해 빠른 CRUD연산을 지원하기 위해 사용하는 중요한 기법이다.

좋은 해시 함수의 조건

• 해시 함수 값 충돌의 최소화
• 쉽고 빠른 연산
• 해시 테이블 전체에 해시 함수 값이 고르게 분포
• 입력된 키의 모든 정보를 사용
• 해시 테이블 사용 효율이 높을 것

해시의 충돌

해시 함수의 결과 값이 N일 때, N + 1가지의 데이터 입력이 들어오면 필연적으로 충돌이 발생한다. 그렇지만 생각보다 충돌은 $\cfrac{1}{N}$이 아니라 더 높은 확률로 발생한다. 생일 문제에 따르면 전체 365일에 대해 23명이 있을 때 생일이 겹칠 확률은 50% 이상이고 57명부터는 99%를 넘어선다. 이에 대해 짤막하게 코드로 검증한다.

import random

CASES = 100000 # 10만 회 실험
same_birth = 0 # 생일이 같은 사람이 발생한 실험의 개수
n = 23 # 23명에 대해
for _ in range(CASES):
    birthdays = []
    for _ in range(n):
        birthday = random.randint(1,366) # 1부터 365까지의 난수
        if birthday in birthdays: # 생일 충돌 시
            same_birth += 1 # count 1 추가
            break
        birthdays.append(birthday)
print(f'n: {n}, {same_birth / CASES * 100}%')

same_birth = 0
n = 57 # 57명에 대해
for _ in range(CASES):
    birthdays = []
    for _ in range(n):
        birthday = random.randint(1,366)
        if birthday in birthdays:
            same_birth += 1
            break
        birthdays.append(birthday)
print(f'n: {n}, {same_birth / CASES * 100}%')        

비둘기의 집 원리에 따라 충돌이 필연적으로 발생함은 익히 알고 있지만 그 확률이 생각보다 상당하다는 점을 비춰봤을 때 해시 테이블에서 충돌은 꽤 중요한 문제이다.

적재율(로드팩터, load factor)

해시 테이블에 저장된 키의 개수를 K, 해시 테이블의 키를 저장할 수 있는 공간의 크기를 N이라 할 때, 로드 팩터는 $\cfrac{K}{N}$로 정의된다.

이 값은 해시 함수가 키를 잘 분산하고 있는지 보여주는 지표가 될 수 있다. 보통 로드 팩터가 증가할 수록 해시 테이블의 성능은 충돌을 피하기 위해 점점 감소한다.

해시 충돌에 따른 구조적 개선 방안

개별 체이닝(Seperate Chaining)

그림에 따르면 John Smith와 Sandra Dee 간의 해시값 충돌이 발생했다. 개별 체이닝 방식은 충돌이 발생했을 때 기존에 저장된 데이터 뒤로 연결함으로써 문제를 해결한다. 이에 대한 시간 복잡도는 다음과 같다.

연결리스트를 사용하면 삽입/삭제는 O(1)이겠지만 탐색에 O(k)가 소요될 가능성이 있다. 다만, 가장 기본적인 형태이고 구현의 난이도가 높지 않아 널리 쓰인다. 적재율을 $\alpha$라고 하면 평균적인 시간복잡도는 O($\alpha+1$)정도가 되겠다.

오픈 어드레싱(Open Addressing)

이전 Seperate Chaining 방식은 데이터의 해시값을 변경시키지 않고 연결리스트로 추가해 depth를 증가시켰다. 그러나 오픈 어드레싱 방식은 탐사(probe)를 해 빈 공간을 찾아 데이터를 저장한다. 그래서 무한정 저장할 수 있는 체이닝 방식에 비해 전체 슬록의 개수 이상 저장할 수 없다. 따라서, 1개의 해시와 1개의 값의 매칭을 보장하지만 그 해시값이 저장된 데이터의 해시값과 일치하는 주소에 저장됨은 보장하지 못한다.

위 그림처럼 152번 index에서 충돌이 일어나 빈 공간 탐색 후 Sandra Dee가 153번 index에 저장되고 Ted Baker가 153번 index에서 충돌이 일어나 탐색 후 154번 index에 저장되는 방식이다.

오픈 어드레싱 기법의 충돌 처리기법

• 선형 탐사(Linear Probing)

  충돌이 발생한 인덱스의 인접 인덱스부터 탐색을 진행하여 빈 공간을 찾는다. 문제는 충돌 지점 주변으로 데이터가 쌓여나가 충돌 범위가 늘어나게 되고 그에 따라 데이터들이 고르게 분포되지 못해 뭉쳐진다. 해시 테이블 곳곳에 연속된 데이터 그룹이 생성되는 현상을 Clustering이라 하며 점점 커지면서 인근 클러스터들과 합쳐지고 빈 공간을 위한 탐색시간을 증가시킨다. 따라서, 해싱 효율이 감소되는 결과를 초래한다.

• 제곱 탐사(Quadaric Probing)

  $1^2,\ 2^2,\ 3^3, \cdots$의 간격을 띄워가면서 탐색을 진행해 클러스터 간의 간격을 벌린다. 다만 초기 해시값이 같으면 역시나 클러스터링의 문제가 있다.

• 이중 해싱(Double Hashing)

  해싱을 두 번 수행하지만 각각의 목적이 다르다. 첫 번째는 데이터의 해시값을 찾기 위해, 두 번째 해시 함수는 충돌 발생 시 분포를 고르게 만들기 위한 탐사폭을 계산하는 데 사용된다.

오픈 어드레싱 방식은 개별체이닝과 달리 탐색과 삭제의 경우 O(1)에 해결되지만 삽입의 경우 해시 테이블의 분포 상태에 따라 복잡도가 결정된다. 로드 팩터에 따라 삽입 시간이 결정되므로 로드 팩터를 $\alpha$라고 할 때 삽입은 O($\alpha + 1$)이지만 삭제, 탐색은 O(1)이 되어 사용함에 있어 시간 측면에서는 비교적 개별 체이닝보다 조금 유리하다.

개별 체이닝과 오픈 어드레싱 사용 현황

일반적으로 오픈 어드레싱이 개별 체이닝보다 성능이 좋지만 로드 팩터가 80%를 초과하는 시점부터 지수적으로 성능저하가 발생한다. 따라서, 각 언어마다 기준이 되는 로드팩터 비율을 정해두고 그걸 넘어서면 growth factor의 비율에 따라 더 큰 크기의 버킷을 생성한 뒤 복사하는 리해싱 작업을 한다. 이는 동적 배열에서 공간이 모두 찼을 때 수행되는 더블링(Doubling)과 흡사하다.

• 개별 체이닝 - 평균적으로 성능이 준수함, 로드 팩터 문제 X
• 오픈 어드레싱 - 임계값 이전까지는 성능 우위, 이후부턴 불리, 로드 팩터 임계값을 작게 잡아서 성능 이슈 해결