Hash Table

Hash Table이란?

키 -> 값을 빠르게 찾기 위한 자료구조로, 배열의 빠른 접근(random access)과 원하는 키로 값을 찾는 맵(map) 개념을 합친 것이다.

 

다음과 같은 연산들을 보자.

1. 키 k에 값 v를 저장

2. 키 k에 해당하는 값 조회

3. 키 k에 해당하는 값 삭제

위 연산들 모두 일반적으론 키 k를 찾기위해 순회를 해야한다(O(n)). 하지만 해시 테이블은 이런 작업들을 O(1)에 수행할 수 있게 해준다.

How?

해시 테이블의 핵심 아이디어는 이름에서도 할 수 있듯이 해시 함수(Hash Function)이다. 그 중 기본은 나머지 연산을 활용한 해시 함수로 다음과 같이 작동한다.

 

1. 내부에 고정 길이 배열을 확보 (크기 m)

2. 키 k가 들어오면 해시 함수로 k를 정수 h(= hash(k))로 변환

3. index = h % m 과 같은 modulo(나머지) 연산으로 배열의 인덱스를 계산

4. 해당 인덱스 칸에 (k, v)를 저장

키 k -> hash(k) -> h % m -> 배열의 인덱스 i

복잡해 보이지만 사실 키 k에 대해 hash 연산과 modulo 연산 단 두 개로 원하는 키(인덱스)에 접근할 수 있게 되는 것이다.

해시 테이블의 작동

해시 함수(Hash Function)

위에서 알 수 있듯이 해시 테이블의 핵심은 해시 함수(Hash Function)이다. 해시 함수는 명확히 따지자면 두 단계로 나누어진다.

1. 키 -> 큰 정수로 만드는 해시 함수 (예: hashCode(), SHA-256, MurmurHash 등)

2. 그 정수 -> 테이블 인덱스(0 ~ m-1)로 줄이는 단계

 

 

해시 함수는 동일한 키에 대해 항상 동일한 해시 값을 내야한다. 또한 가능한 균등하게 분포하도록 해야하고(특정 인덱스에 몰리지 않도록), 빠르게 계산할 수 있어야 한다.

 

* Java에서는 모든 객체의 최상위 부모인 Object 객체의 hashCode() 메서드가 인스턴스의 주소 혹은 객체 헤더(mark word)에 심어놓은 pseudo-random 값 등 객체 identity를 구분하기 위한 어떤 정수 값을 기반으로 해시를 기본으로 정의하고 있다.(equals가 같은 인스턴스인 경우 True를 반환하기 때문) 이후 Hash를 사용하는 자료구조들(HashMap, TreeSet, HashSet 등)은 hashCode()의 결과를 한 번 더 섞어서 인덱스로 사용(bucket 분포를 좋게 하기 위해)한다. 추후 객체의 equals()를 재정의한다면 그에 맞게 hashCode()도 재정의해주어야 한다.

 

해시 충돌(Hash Collisions)

해시 함수는 서로 다른 키에 대해서 같은 값을 도출할 수도 있다. 수학적으로 해시 충돌은 피할 수 없기 때문에 효율적으로 처리하는 것이 중요하다.

+ 왜 피할 수 없는가? 비둘기 집의 원리로 인해 테이블의 크기보다 더 많은 값들이 들어오는 경우, 혹은 hash(k1) == hash(k2)인 경우, hash(k1) % M == hash(k2) % M인 경우가 존재하기 때문이다.

 

이런 문제를 처리하기 위해 다음과 같은 두 가지 방법을 사용한다.

1. Separate Chaining (분리 연결법; 체이닝)

분리 연결법은 보편적으로 사용되는 방법으로 배열의 각 칸을 연결 리스트(컨테이너)의 시작점으로 보는 방식이다. 이름에서도 알 수 있듯이 해시 충돌이 나는 경우 Chaining하여 같은 칸에 줄줄이 다는 방법이다.

Separate Chaining

이 방법으로 해시 테이블을 구성하게 되면 탐색할 때 인덱스를 계산 후 해당 버킷의 리스트를 순회하며 찾는 값인지 비교하는 연산이 필요하다. Java에서는 한 버킷에 데이터가 8개가 넘어가면 Red-Black Tree로 전환하여 O(logN)으로 접근할 수 있도록한다.

 

장점

• 구현이 직관적이고 단순
• 원소의 삭제가 간단: 아래에서 설명하겠지만, 개방 주소법에서는 원소의 삭제와 비어있는 칸을 구분하기 위한 추가적인 표시가 필요하다.
• 부하율(Load Factor)에 민감하지 않음: 테이블이 거의 다 찼어도, 데이터에 접근하는 시간은 해시 함수 한 번 거친 후버킷을 탐색하기만 하면 되기 때문에 테이블의 부하율에 성능이 크게 좌우되지 않고, 테이블의 확장에 대한 부담이 적다.

단점

• 캐시 친화도가 떨어진다: 포인터(참조) 타고 리스트/트리 쫓아가는 구조로 데이터가 흩어져 있어 cache miss가 많이 나게 된다.
• 추가 메모리 오버헤드: 각 버킷에 연결되는 컨테이너를 위한 포인터, 객체 헤더가 필요하고, GC 관점에서도 작은 객체가 많이 만들어진다.

2. Open Addressing (개방 주소법)

개방 주소법은 해시 충돌이 난 경우 다른 빈 칸을 찾아서 넣는 방법이다. 대표적으론 다음과 같은 방법들이 있다.

• 선형 탐사(Linear Probing): 이름처럼 충돌이 발생했을 때 index + 1, + 2, ... 로 선형적으로 빈 칸을 탐색하는 방법이다. 하지만 Primary Clustering 이라는 특정 버킷 근처에 값들이 몰리는 현상이 발생할 수 있다. 클러스터의 크기가 커질수록 해시 값에 대한 충돌도 많이 일어나니 몰리는 값들이 점점 많아진다. 탐색에서는 단점으로 작용하지만, 캐시적인 측면에서는 캐시 히트율이 올라가는 상황이 생길 수도 있다.
• 이차 탐사(Quadratic Probing): index + 1 ^ 2, 2 ^ 2, ... 로 제곱하여 빈 칸을 탐색하는 방법이다.
• 이중 해싱(Double Hashing): 충돌이 발생했을 때 해시 함수를 한 번 더 돌려 빈 칸을 탐색하는 방법이다.

Open Addressing

장점

• 캐시 친화적: 모든 데이터가 하나의 큰 배열에 연속으로 있기 때문에 CPU 캐시 히트율이 좋다.
• 작은 테이블에서 효과적
• 가벼움: 정보를 그대로 배열에 저장하기 때문에 메모리 효율이 좋고, 할당/해제 오버헤드도 적다.

단점

• 부하율(Load factor)에 민감: 테이블이 꽉 차갈수록 탐색 길이가 기하급수적으로 늘어난다.
• 삭제의 불편함: 그냥 원소를 비워버리면 탐사 경로가 끊겨서 검색이 실패할 수 있어, 삭제 마커를 남겨놓거나 재삽입 트릭이 필요한다.
• 해시 함수 품질에 민감: 나쁜 해시 + 선형 탐사로 primary clustering이 심해지면 결국 길게 쭉 훑게 되어 효율이 나빠진다.
• 동시성 제어가 어려움: 한 원소 삽입/삭제가 주변 슬롯들의 탐사 체인 전체에 영향을 미칠 수 있어 버킷 단위 lock으로 깔끔하게 자르기 어렵다.

부하율(Load Factor)과 리사이징(Re-Sizing)

해시 테이블은 테이블이 얼만큼 채워져 있는지에 따라 성능이 좌우된다. 위에서 말한 것처럼 원소가 많아질 수록 해시 충돌의 확률이 올라가기 때문인데, 이것을 관리하기 위해 부하율(Load Factor)에 따른 리사이징(확장)을 진행한다. 배열에서도 비슷한 개념이 있었는데, 해시 테이블에서도 마찬가지이다. 차이점은 꽉 차지 않아도 정책에 따른 부하율 기준을 넘으면 확장을 진행한다.

Load Factor(부하율) = (저장된 원소 수 N) / (배열 크기 M)

 

해시 테이블에서의 확장은 더 큰 배열로 확장하고 모든 원소를 다시 해시해서 새 배열로 옮기는 방식으로 진행된다. 배열에서 본 것과 같이 한 번 확장이 일어날 땐 O(n)의 시간 복잡도가 들지만 결국 분할 상환(Amortized Analysis)으로 인해 삽입 연산의 시간 복잡도는 O(1)로 수렴한다.

Hash Table의 구조적 단점

데이터의 저장이 해시 함수를 거쳐 일어나기 때문에 연속적으로 저장되지 않고 흩어져서 저장되게 된다. 따라서 정렬이 불가능하며(순서 보장X) 캐시 친화적이지 않다는 구조적인 단점이 존재한다.