해시 테이블 완전 이해: 버킷, 해시 함수, 충돌 처리까지

제가 가장 좋아하는 자료구조 중 하나는 바로 해시 테이블입니다. 단순하면서도 강력하기 때문인데요.

키-값(key-value) 쌍을 효율적으로 저장할 수 있는 방법이기 때문에 여러분도 이미 여러 번 사용해 보셨을 겁니다.

그런데 해시 테이블의 구현에는 공부해 볼 가치가 충분한 흥미로운 컴퓨터 과학 개념들이 숨어 있습니다. 바로 지금부터 그 내부 원리를 하나씩 파헤쳐 보겠습니다!

버킷(Bucket)과 해시 함수

해시 테이블의 기본 아이디어는 키로 색인된 데이터를 효율적으로, 즉 O(1) 시간에 검색할 수 있게 하는 것입니다.

간단히 복습하자면, Ruby에서 해시 테이블을 사용하는 모습은 다음과 같습니다:

prices = {
  apple: 0.50,
  ice_cream: 3,
  steak: 10
}

해시 테이블을 구현하려면 두 가지 구성 요소가 필요합니다:

테이블의 항목(entry)을 저장할 공간
키/값 쌍을 데이터 저장소의 특정 위치(인덱스)에 할당하는 방법

다시 말해, 배열과 해시 함수, 이 두 가지가 필요한 것입니다.

간단한 해시 함수 구현하기

해시 함수는 해시 테이블의 핵심 구성 요소입니다.

이 함수는 키를 인덱스로 변환해 주며, 이 인덱스를 통해 해당 값의 조회나 업데이트가 이루어집니다.

해시 테이블 완전 이해: 버킷, 해시 함수, 충돌 처리까지

이것이 일반 배열과 해시 테이블의 가장 큰 차이점입니다.

배열에서는 오직 숫자 인덱스로만 값에 접근할 수 있습니다. 반면 해시 테이블에서는 키를 통해 값에 접근하며, 키는 무엇이든 될 수 있습니다(문자열, 심볼, 정수 등). 물론 그 키에 대한 해시 함수를 작성할 수 있다는 전제가 필요합니다.

문자열이라면 모든 글자를 ASCII 값으로 변환한 뒤 모두 더하는 간단한 해시 함수를 만들 수 있습니다.

예시는 다음과 같습니다:

BUCKETS = 32

def hash(input)
  input.to_s.chars.inject(0) { |sum, ch| sum + ch.ord } % BUCKETS
end

이 메서드에서는 먼저 to_s를 호출해 입력값이 문자열임을 보장합니다. 이렇게 하면 'undefined method' 오류를 예방할 수 있습니다. 이후 chars(문자열을 문자들의 Array로 변환)와 inject(각 값을 누산)를 조합해 사용합니다.

블록 내부에서는 ord 메서드를 통해 각 문자를 서수(ordinal) 값으로 변환했습니다.

마지막으로 나머지 연산자 %를 적용해 결과값이 항상 배열 범위 안에 들어오도록 했습니다. 이 배열의 각 칸을 우리는 '버킷(bucket)'이라고 부릅니다.

버킷 분포 확인하기

이상적인 상황은 모든 버킷이 고르게 채워지는 것입니다. 그래야 값을 검색할 때 최상의 성능을 얻을 수 있습니다.

다음 코드로 해시 함수를 직접 테스트해 보겠습니다:

# BUCKETS 크기의 배열을 생성하고 모든 요소를 0으로 초기화
table   = Array.new(BUCKETS) { 0 }
letters = Array('a'..'z')

10_000.times do
  # 무작위 문자열 생성
  input = Array.new(5) { letters.sample }.join

  # 해시 분포 집계
  table[hash(input)] += 1
end

실행 결과는 다음과 같습니다:

[302, 290, 299, 309, 321, 293, 316, 301, 296, 306, 340, 321, 313, 304, 318, 296, 331, 306, 348, 330, 310, 313, 298, 292, 304, 315, 337, 325, 325, 331, 319, 291]

키들이 꽤 고르게 분포된 것처럼 보입니다...

...그렇다면 버킷 수를 늘리면 어떻게 될까요?

이번에는 버킷 크기를 128로 설정해 보았습니다(이전에는 32였습니다):

[22, 24, 33, 36, 41, 58, 61, 66, 97, 77, 88, 110, 89, 82, 123, 121, 119, 111, 147, 178, 136, 176, 144, 180, 190, 193, 185, 192, 223, 209, 208, 196, 215, 251, 233, 226, 231, 236, 219, 218, 227, 221, 206, 220, 208, 213, 201, 191, 182, 165, 188, 141, 160, 135, 130, 117, 139, 106, 121, 85, 70, 93, 74, 61, 57, 54, 40, 46, 32, 36, 30, 21, 25, 17, 14, 16, 16, 14, 8, 11, 5, 5, 1, 1, 2, 1, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 4, 3, 6, 0, 2, 9, 13, 11, 12, 14, 12, 23, 12, 22]

이번에는 좋은 분포라고 보기 어렵네요! 대체 무슨 일이 일어난 걸까요?

원인은 해시 함수의 품질에 있습니다. 현재 함수로는 길이가 같은 문자열들이 특정 범위 안에만 머물게 되기 때문입니다. 그래서 중간에 빈 버킷이 대량으로 발생하는 것이죠.

더 나은 해시 함수 만들기

문자열을 인덱스로 변환하는 더 나은 방법이 필요합니다. 한 가지 가능한 구현을 살펴보겠습니다.

BUCKETS = 256

def hash(input)
  input.to_s.each_char.inject(0) do |sum, ch|
    (sum << 8) ^ (ch.ord) ^ (sum >> 4)
  end % BUCKETS
end

여기서 핵심은 비트 시프트(bit shifting)입니다(>>와 << 연산자 사용). 그리고 각 값들은 "배타적 OR 연산자"(^)로 결합됩니다.

비트 시프트가 값들을 잘 섞어주기 때문에 훨씬 균등한 키 분포를 얻을 수 있습니다. 완벽하지는 않지만, 앞서 만든 단순 ASCII 기반 함수보다는 확실히 낫습니다 🙂

실무 수준의 해시 함수가 필요하다면 MurmurHash 같은 알고리즘을 참고하세요. 제가 알기로 Ruby 내부에서도 이 방식을 사용하고 있습니다.

충돌(Collision) 처리하기

하지만 아직 실용적인 해시 테이블이라고 하기엔 부족합니다.

왜일까요?

눈치채셨겠지만, 서로 다른 두 키가 동일한 인덱스로 해시되면 기존 값이 새 값에 의해 덮어써져 버립니다. 이건 심각한 문제죠!

이런 현상을 해시 충돌(hash collision)이라고 부르며, 이를 처리하기 위한 몇 가지 전략이 존재합니다.

대표적인 방법은 다음과 같습니다:

이중 해싱(Double Hashing)
선형 조사(Linear Probing)
분리 연결(Separate Chaining)

그중 분리 연결(Separate Chaining) 방식을 살펴보겠습니다. 이 방식은 연결 리스트(linked list)를 활용해 하나의 "버킷"에 여러 항목을 저장합니다.

예를 들어 :abc와 :ccc가 같은 인덱스로 해시된다고 가정하면, 해시 테이블은 대략 다음과 같은 모습이 됩니다:

3: [:abc, 100] -> [:ccc, 200]
4: nil
5: [:yx, 50]

이 경우 원하는 키를 찾으려면 선형 검색(linear search)이 추가로 필요합니다.

이는 성능에 영향을 미칩니다. 조회 시간이 기대했던 O(1)에서 점차 O(n)으로 저하될 수 있기 때문입니다.

O(something) 형태의 표기법이 낯설다면, 이것은 알고리즘의 효율을 나타내는 "Big-O 표기법"입니다.

연결 리스트가 너무 깊어져 해시 테이블 전체 성능이 저하되는 것을 방지하려면, 더 많은 버킷을 가진 새로운 해시 테이블을 다시 생성해야 합니다(rehashing).

Ruby는 이 과정을 자동으로 처리해 주지만, 내부 동작을 이해하고 있다면 큰 도움이 됩니다.

마무리

이 글의 목적은 여러분이 직접 해시 테이블을 구현하게 하는 것이 아니라, 그 내부 동작 원리를 제대로 이해하도록 돕는 것입니다. 재미있게 읽으셨기를 바랍니다!

블로그 운영에 큰 힘이 됩니다. 글 공유 잊지 마세요 🙂