Sonji-log
[자료구조] 해시 테이블(Hash table) 정의/원리/충돌처리 + 조사 본문
정의
Key-Value(키-값) 쌍을 저장하고, 빠르게 데이터를 검색, 삽입, 삭제할 수 있게 만든 자료구조.
해시 함수를 이용해 데이터를 특정 key에 매핑하여 효율적으로 검색할 수 있도록 설계되었다.
e.g., 전화번호부(Key : Value = 이름 : 전화번호)
Q1. 왜 빠른가요?
A1. 해시 함수를 사용해서 키를 고유 배열 인덱스로 매핑하기 때문. 배열은 인덱스만 알고 있다면 순차적으로 탐색할 필요 없이 원하는 위치에 바로 액세스할 수 있으므로, 검색, 삽입, 삭제에서 모두 시간복잡도가 O(1)로 동작해 빠른 속도를 보임.아래 동작원리의 기본 구조와 동작 과정 참조.
동작 원리
기본 구조
해시 테이블은 내부적으로 배열을 사용해서 데이터를 저장한다.
데이터를 해시 함수를 통해 특정 인덱스로 변환하고, 그 인덱스에 직접 액세스해서 데이터를 처리하는 방식이다.
Q2. 키가 겹쳐서 인덱스에 이미 데이터가 차있으면 어떡하죠?
A2. 아예 배열 한 칸에 다른 리스트를 집어넣거나, 다른 비어있는 칸에 저장하는 방식을 채택함. 자세한 방법은 아래 충돌 처리 내용 참조.
동작 과정
● 삽입 단계
- 키를 해시 함수에 입력해 배열 인덱스를 계산한다.
e.g., index = h(key)
h(key) = key % 10 - 계산된 인덱스 위치에 데이터를 저장하고, 만약 해당 인덱스에 이미 다른 데이터가 저장되어 있다면 충돌 해결 방법*을 사용해서 데이터를 저장한다.
*충돌 해결 방법 : 특정 인덱스에 이미 키가 존재하고, 다시 그 키에 액세스해서 저장하려고 하는 경우를 충돌(collision)이라고 함. 충돌은 이론상 피할 수 없기 때문에, 충돌 자체를 회피하기보다 충돌했을 경우 대처법을 미리 만들어두는 편(관련 자세한 내용은 아래 충돌처리 부분 참고)
● 검색 및 삭제 단계
- 검색하려는 키를 해시 함수에 입력해 해당 키가 저장된 배열 인덱스를 획득한다.
- 계산된 인덱스에 직접 액세스하여 데이터를 가져오거나 삭제한다.
만약 충돌로 인해 여러 데이터가 동일한 인덱스에 저장되어 있다면, 사용하는 충돌 방지 정책에 맞는 2차 탐색 알고리즘을 사용한다(체이닝이라면 순차적으로 리스트를 탐색하고, 오픈 어드레싱이라면 사용하는 알고리즘에 따라 달라짐).
충돌 처리
충돌의 원인
비둘기집 원리로 간략하게 설명할 수 있다.
만약 9개의 비둘기집(=버킷)이 있고, 10마리의 비둘기가 있다면, 필연적으로 하나 이상의 비둘기집에는 비둘기가 두 마리 이상 들어가게 된다.(참고자료)
비둘기집 원리 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 비둘기집 원리는 n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형
ko.wikipedia.org
이를 조금 더 일반화해서 적어보자면,
해시값을 저장하는 배열(=버킷)의 크기는 유한한데 반해 저장하려는 데이터는 무한하기 때문에 필연적으로 충돌이 발생할 수밖에 없다. 다만, 해시 함수 품질이 좋지 않아 키가 균등하게 분배되지 못한다면 특정 인덱스에 데이터가 몰리는 등 같은 충돌이어도 대처하기가 더 까다로운 충돌이 생길 수 있다.
Q3. 버킷 자체를 무한대로 늘려버리면 되는 문제 아닌가요? 유한한 버킷에 핸들링하는 여러 요소(해시 함수, 체이닝 기법, 인덱싱 메모리 등)들이 추가로 고려되면서까지 데이터를 저장하려는 의도를 잘 모르겠어요. 합당한 트레이드오프인가요?
A3. 궁극적으로 말하면, 이러한 데이터 컨트롤을 위한 트레이드오프는 탐색 속도를 끌어올리기 위함. 따라서 탐색이 많거나, 삽입/삭제의 속도가 중요한 경우에 한해서는 그 요소들이 매우 저렴한 트레이드오프라고 볼 수 있음. 내용이 너무 길어져 자세한 내용은 아래 부록 참조.
충돌 해결법
체이닝(Chaining)
해시 함수로 계산한 인덱스에 이미 데이터가 존재한다면, 해당 인덱스에 연결리스트를 생성하고 그 뒤에 데이터를 사슬처럼 연달아 저장하는 방식이다.
그림으로 표현하면 아래와 같다.
대다수의 언어에서는 위처럼 연결 리스트로 사용되지만, Java 8에서는 특정 버킷에 일정 threshold 이상 요소가 존재하는 경우, 해당 버킷의 체이닝 구조가 연결 리스트가 아닌 균형 이진 트리로 전환해서 탐색 속도를 개선한다.
(jdk github 참조).
...
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
...이처럼 체이닝 아키텍처를 바꾸는 이유는, 아래 서술할 장단점과 연관된다.
● 체이닝 방식의 장점
- 충돌이 많이 발생하더라도 단순히 연결 리스트에서 사용하는 삽입/삭제 연산과 구조적으로 완전히 같으므로, 삽입/삭제 연산이 평균O(1)로 빠르고 간단함.
- 해시 테이블이 꽉차더라도 새로운 데이터를 추가하기가 쉬움. 단순히 연결 리스트를 확장하는 것으로 끝낼 수 있기 때문.
● 체이닝 방식의 단점
- 충돌이 많으면 리스트가 길어져 탐색 속도가 O(n)으로 늘어날 수 있음.
(*이런 이유로 인해 Java 8에서는 리스트가 너무 길어질 경우 균형 이진 트리로 체이닝 구조를 변경함. 균형 이진 트리는 탐색 속도가O(log n)으로 감소하기 때문.) - 저장할 데이터가 많지 않은 경우, 데이터를 관리하기위한 데이터(포인터)가 늘어나는 꼴이 되므로 메모리 낭비가 심할 수 있음.
오픈 어드레싱(Open Addressing)
충돌이 발생했을 때, 다른 빈 슬롯을 찾아서 데이터를 저장하는 방식이다.
결과적으로, 모든 데이터는 배열 자체에 저장되기 때문에 추가 메모리가 필요하지 않다.
하지만 어떤 슬롯에 저장했는지 탐색해야 하는 전략이 추가로 필요하고, 탐색은 연속적인 검색을 수행하기 때문에 어떤 한 부분의 데이터를 삭제한다면 이후 데이터를 탐색할 때 제대로 된 동작이 수행되지 않을 수 있다.
Q4. 왜 제대로 된 동작이 수행되지 않을 수 있는건가요?
A4. 오픈 어드레싱 기법에서 탐색은 정해진 알고리즘으로 빈 슬롯을 '순차적'으로 탐색하고, 데이터를 삽입할 때 사용된 탐사 경로가 탐색 과정에서도 그대로 유지됨. 따라서 삽입 당시에 빈 슬롯을 만나면 그 뒤에는 해당 키가 삽입될 수 없다는 것이 보장되기 때문에, 삭제 단계에서도 빈 슬롯을 만나면 불필요한 연산을 줄이기 위해 이후 내용은 탐사하지 않음.
이러한 성질 때문에, 실제로 데이터가 존재할 수도 있는 뒷부분을 직접 탐색하지 않아 데이터가 있음에도 불구하고 없다고 출력할 수 있는 것.
● 탐색 전략의 종류
- 선형 탐사(Linear Probing)
- 충돌이 발생했을 경우, 다음 슬롯(index + 1)을 순차적으로 탐색해서 빈 슬롯을 찾는 방법.
e.g., $ \text{index} = (h(\text{key}) + i) \mod \text{table_size} $
(i = 시도 횟수) - 장점 : 구현이 매우 간단함
- 단점 : 클러스터링 문제*가 발생하여 성능 저하를 초래할 수 있음.
(클러스터링 문제(Clustering) : 해시 테이블에서 충돌이 발생했을 경우, 특정 영역에 데이터가 몰리는 현상)
(자세한 내용은 아래 부록 참조)
- 충돌이 발생했을 경우, 다음 슬롯(index + 1)을 순차적으로 탐색해서 빈 슬롯을 찾는 방법.
- 제곱 탐사(Quadratic Probing)
- 충돌이 발생했을 경우, 점점 더 멀리 떨어진 슬롯을 탐색하는 방법.
e.g.,
$ \text{index}_i = \left( h(k) + c_1 \cdot i^1 + c_2 \cdot i^2 \right) \mod m $
$ \text{일반적으로 } c_1 = 0, c_2 = 1 \text{ 로 단순화하므로,} $
$ \text{index}_i = \left( h(k) + i^2 \right) \mod m $
$ h(k) : \text{ 키의 초기 해시값}, \quad i : \text{ 충돌 횟수}, \quad m : \text{ 테이블 크기} $
(이에 대한 수학적 정의는 아래 부록 참조) - 장점 : 클러스터링 문제를 경감할 수 있음.
- 단점 : 테이블이 가득 차면 무한루프를 돌기 때문에 테이블 크기를 소수로 설정해야 함.
- 충돌이 발생했을 경우, 점점 더 멀리 떨어진 슬롯을 탐색하는 방법.
- 이중 해싱(Double hashing)
- 두 개의 서로다른 해시 함수를 사용해 새로운 슬롯을 탐색하는 방법.
e.g.,
$ \text{index} = \left( h_1(\text{key}) + i \cdot h_2(\text{key}) \right) \mod \text{table size} $ - 장점 : 클러스터링 문제를 효과적으로 방지함
- 단점 : 구현이 복잡하고, 성능이 보장된 두 번째 해시 함수가 필요함.
- 두 개의 서로다른 해시 함수를 사용해 새로운 슬롯을 탐색하는 방법.
모든 경우에서 공통적으로, 오픈 어드레싱 방식에서는 삭제 시 더미 노드로 처리해야 모든 슬롯을 탐색할 수 있기 때문에 삭제 후처리가 필요하다.
결론
- 해시 테이블은 데이터의 탐색이 많고, 삽입/삭제 연산 속도가 중요한 경우에서 사용하는 편이 좋다.
- 보통 유한한 버킷에 무한대의 데이터를 가정하므로, 충돌 문제는 필연적으로 발생한다.
- 충돌 문제는 피할 수 없으므로 회피보다는 발생했을 경우 어떻게 대처할지를 크게 2가지 방법으로 구분해서 사용한다.
- 체이닝 방법은 같은 키의 저장소에 연결 리스트를 만들어 데이터를 사슬처럼 이어붙인다.
- 데이터를 관리하기위한 오버헤드가 발생하고, 최악의 경우 탐사속도 증가를 막기 위해 Java 8에서는 균형 이진 트리로 구조를 바꾸기도 한다
- 오픈 어드레싱 방법은 다른 비어있는 칸을 탐사하는 방법으로, 추가 저장 공간을 요구하지 않는다
- 하지만 클러스터링 문제가 발생할 수 있으며, 삭제 연산에 추가 후처리가 필요하다.
- 체이닝 방식은 데이터셋이 크고 충돌이 많이 발생하며 삽입/삭제가 자주 발생할 때 사용하기 좋다.
- 오픈 어드레싱 방식은 메모리가 제한적이고 데이터셋이 작은 경우 사용하기 좋다.
| 특징 | 체이닝(Chaining) | 오픈 어드레싱(Open Addressing) |
| 메모리 사용량 | 추가 메모리 필요(연결 리스트 등) | 테이블 크기만큼만 사용(추가 없음) |
| 충돌 해결 | 연결 리스트를 사용해 충돌이 많아도 확장 가능 | 충돌 시 테이블 내 빈 공간만 탐색함 |
| 탐색 속도 | O(1) (충돌이 많으면 O(N)) | O(1) (충돌이 많으면 O(N)) |
| 삽입 속도 | O(1) (리스트 앞에 추가) | 충돌이 많으면 O(N) |
| 삭제 속도 | O(1) (노드 삭제만 하면 끝) | O(N) (더미처리 필요) |
| 충돌처리 효율성 | 유연함 | 충돌시 성능저하 가능성 높음 |
| 클러스터링 문제 | 없음 | 선형 탐사에서는 발생 가능 |
부록
버킷을 무한대로 늘리면 안되는 이유
무엇보다, 실제로 메모리는 유한하기 때문에 무한대로 늘릴 수 없다.
그래도 만약 가능하다고 가정하고 무한대로 늘리더라도, 아래 3가지 단점이 대두된다.
- 실제로 버킷을 매우 크게 설정하더라도, 실제로 저장된 데이터가 상대적으로 소수라면 메모리 효율성이 급락한다.
- 버킷이 무한히 커지면, 데이터가 메모리 전역에 분산 저장되고, 이는 지역성이 악화되어 탐색 성능이 떨어진다.
- 버킷의 크기가 커진다는 의미는 곧 해시값의 결과 범위가 마찬가지로 커져야 함을 의미한다. 이를 위해 해시 함수를 지나치게 복잡하게 설계하면 계산 시간이 증가해 성능이 나빠진다.
결과적으로, 무한대의 버킷은 결국 Direct Addressing 방식과 같아지기 때문에 해시 테이블을 쓰는 본래 목적(속도, 공간 효율성)을 상실한다.
※Direct Addressing : 삽입하고자 하는 모든 데이터를 담을 수 있는 배열을 미리 준비하고, 각 데이터마다 1:1로 인덱스에 접근하고자 하는 방식.
보통 실제로 해시 테이블이 구현되어있는 코드를 살펴보면, Load Factor를 계산해 이 지표가 0.7가량일때 해시 테이블의 성능이 가장 안정적으로 동작한다고 간주한다.
로드 팩터(Load Factor)
해시 테이블에서 사용중인 버킷의 비율을 나타낸다. 주로 해시 테이블의 충돌 가능성과 성능을 조절하는 데 사용한다.
계산하는 방법은 아래와 같다.
$ \text{Load Factor} = \frac{\text{저장된 원소 개수}}{\text{해시 테이블 크기}} $
예를 들어, 해시 테이블의 크기가 100이고 현재 75개의 원소가 저장되어 있다면,
$ \text{Load Factor} = \frac{75}{100} = 0.75 $
만약 로드 팩터가 높다면 충돌 가능성이 증가해 탐색, 삽입, 삭제 성능이 저하될 우려가 있다.
반대로 로드 팩터가 너무 낮다면 충돌이 적어 검색은 빠르지만, 메모리 낭비가 커질 수 있다.
주요 언어별 로드 팩터는,
- Java : 기본적으로 0.75의 load factor를 사용하고, 이를 초과하면 해시 테이블의 크기를 두 배 늘리고 모든 요소를 재해싱한다 (참고)
- Python : 공식 문서에 명확한 값을 제시하지는 않았으나, 통상 2/3(=약 66.6%)정도를 권장 수준으로 설정한다 (참고)
해시 테이블이 일반 데이터셋보다 특정 환경에서 효율적인 이유
해시 테이블에서 추가로 요구하는 추가 공간은 아래 리스트로 설명할 수 있다.
- 해시 값 저장 : 충돌이 필요한 경우 별도저장
- 해시 테이블 버킷 배열
- 충돌 해결을 위한 추가공간
- 체이닝 : 연결 리스트 or 트리 필요
- 오픈 어드레싱 : 일부 버킷이 비어있어야 정상적으로 동작하므로 미사용 공간에 대한 코스트
따라서 일반 Direct Addressing 보다는 요구하는 공간이 많다.
하지만, 다른 탐색 자료구조+알고리즘과 비교해보면 해시 테이블이 가지는 탐색 속도상 이점을 파악할 수 있다.
| 자료구조 + 알고리즘 | 저장 공간 | 탐색 성능 |
| 단순 리스트(배열) | O(N) | O(N) (순차 탐색) |
| 정렬된 리스트 + 이진 탐색 | O(N) | O(log N) |
| 이진 탐색 트리 | O(N) + 노드 추가 공간 | O(log N) |
| 해시 테이블 | O(N) + 버킷 배열과 충돌해결 공간 | O(1) |
통상 시간복잡도 순서상 O(log N)보다 O(1)이 대형 데이터에 대해 우수하기 때문에, 해시 테이블은 추가 공간을 사용하지만 탐색 성능을 극대화할 수 있으므로 합당한 트레이드오프라고 볼 수 있다.
클러스터링(Clustering)
해시 테이블에서 충돌이 발생했을 때, 특정 영역에 데이터가 몰리는 현상을 말한다.
주로 충돌 해결 방법을 수행한 이후에 발생하는 일이 잦으며, 충돌 이후 대책이 고른 데이터분포를 보이지 못했을 경우 수반된다.
e.g., 선형 탐사의 경우, 별도 연산 없이 다음 인덱스를 탐색하기 때문에 탐색 시간도 선형으로 길어지며 데이터 분포 또한 밀집된 가능성이 높아진다.
클러스터링 종류
● 1차 클러스터링
- 선형 탐사와 비슷한 시스템에서 주로 발생한다.
- 연속된 슬롯들이 점점 채워지며 긴 클러스터를 형성하고, 클러스터가 거대해질수록 새로운 충돌 발생 확률이 높아지며, 이로인해 계속 클러스터가 커지는 악순환이 반복된다.
- "WKW : Winner Keeps Winning" 현상 : 한 슬롯이 충돌을 여러 번 겪으면, 이후 새로운 충돌도 그 슬롯이 겪은 충돌만큼 많은 연쇄 충돌이 발생할 수 있다. 이런 현상이 심해지면 특정 슬롯이 계속해서 새로운 키를 수용하고, 탐색 및 삽입 성능이 급격히 저하되는 현상을 Winner Keeps Winning 현상이라고 한다. (참고)
- 예시)
Hash Function : h(key) = key % 10
Key : 12, 22, 32
Result
Index 2 -> [12]
Index 3 -> [22] (충돌 후 다음 슬롯 사용)
Index 4 -> [32] (충돌 후 다음 슬롯 사용)
● 2차 클러스터링
- 제곱 탐사나 이중 해싱과 같은 방식에서 주로 발생한다.
- 동일한 해시 값을 가진 키들이 동일한 탐사 순서를 따르기 때문에, 서로 다른 키들이 동일한 위치를 이동하며 새로운 클러스터를 형성한다.
- 첫 키에 동일한 해시 함수를 적용했을 경우, 도출되는 값도 같으므로 이후 연산의 횟수와 방식에 관계없이 동일한 루트를 따르기 때문(= 탐사 경로 중복)이다.
- 예시)
Hash function : h(key) = key % 10
Quadratic Probing : i^2 (i = 시도 횟수)
Key : 12, 22
Result
Index 2 -> [12]
Index 6 -> [22] (충돌 후 제곱탐사로 이동)
이와 같이 클러스터링 문제가 발생하면, 클러스터 크기에 비례해 더 많은 슬롯을 확인해야 하므로 시간복잡도가 O(N)에 가까워질 수 있다.
제곱 탐사가 데이터 분산을 유도해서 1차 클러스터링을 방지하는 수학적 근거
선형 탐사는 다음 인덱스 순서로 빈 공간을 탐색하기 때문에, 이미 충돌이 발생한 위치 근처에서 계속 새로운 충돌이 발생한다.
반면, 제곱 함수는 비선형 증가 특성을 가지기 때문에 충돌 시 탐사 위치를 예측하기가 어렵다.
e.g., $ i^2 = 1, 4, 9, 16, 25, 36, ... $
따라서 특정 영역에 키가 몰리는 현상이 줄어들어 1차 클러스터링이 완화된다.
또한, 테이블 크기가 소수일 경우 탐사 위치가 중복되지 않고 넓게 퍼진다.
이를 실제 예시로 살펴보면 아래처럼 나타낼 수 있다.
해싱 함수 : $ index_{i} = (h(k) + i^2) \text{ } mod \text{ } \text{m} , \text{m(=table size)} = 11, k = 27$
| 충돌 횟수 $ i $ | 탐사 위치 계산 | 최종 인덱스 |
| 1 | (5 + 1^2) mod 11 = 6 | 6 |
| 2 | (5 + 2^2) mod 11 = 9 | 9 |
| 3 | (5 + 3^2) mod 11 = 3 | 3 |
| 4 | (5 + 4^2) mod 11 = 10 | 10 |
| 5 | (5 + 5^2) mod 11 = 7 | 7 |
| 6 | (5 + 6^2) mod 11 = 2 | 2 |
| 7 | (5 + 7^2) mod 11 = 0 | 0 |
| 8 | (5 + 8^2) mod 11 = 1 | 1 |
| 9 | (5 + 9^2) mod 11 = 4 | 4 |
최종 인덱스는 테이블 크기가 소수(11)일때 같은 키에 대해 균등한 분포를 보인다.
반면, 테이블 크기가 합성수일 경우를 살펴보면 아래처럼 나타낼 수 있다.
해싱 함수 : $ index_{i} = (h(k) + i^2) \text{ } mod \text{ } \text{m} , \text{m(=table size)} = 12, k = 27$
| 충돌 횟수 $ i $ | 탐사 위치 계산 | 최종 인덱스 |
| 1 | (3 + 1^2) mod 12 = 4 | 4 |
| 2 | (3 + 2^2) mod 12 = 7 | 7 |
| 3 | (3 + 3^2) mod 12 = 0 | 0 |
| 4 | (3 + 4^2) mod 12 = 7 | 7 (중복) |
| 5 | (3 + 5^2)mod 12 = 4 | 4 (중복) |
| 6 | (3 + 6^2)mod 12 = 3 | 3 (중복) |
이같은 결과는, 소수 m에 대해 모듈러 연산을 수행할 때, 모든 숫자가 서로 다른 독립적인 시드로 작용하기 때문에 탐색 경로가 반복되지 않기 때문에 발생한다.
즉, 제곱수를 이용한 탐사 과정이 특정 패턴으로 고정되지 않음을 의미한다.
반면, 합성수에 대한 모듈러 연산을 수행하면 합성수 m의 약수가 영향을 미쳐 특정 탐사 간격이 반복된다. 이는 곧 특정 값들이 같은 나머지를 생성하는 패턴을 형성하기 때문에, 탐사 위치가 제한되는 결과를 낳는다.
코멘트
필자가 실제로 공부하면서 찾아본 질문을 달았다. 개념적인 부분을 알아 두되, 활용하기만 하느라 몰랐던 부분에 대한 질문 위주로 제시했다.
적고 보니 부록에 대한 내용이 거의 본문 이상으로 길어졌다. 하지만 질문에 대한 답을 찾는 과정에서 얻은 지식들도 많으므로 분량 상관없이 모두 메모해둔다.
앞으로 더 궁금한 점이 생기면 부록에 업데이트할 예정이다.