Hash Table

Hash Table

해시 테이블은 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블이다. 따라서 작은 크기의 캐시 메모리로도 프로세스를 관리하도록 할 수 있다. 삽입, 삭제, 탐색 시 평균적으로 O(1)의 시간 복잡도를 가지고 unordered_map으로 구현한다.

해시 테이블에 데이터를 삽입하기 위해서는 저장하고자 하는 자료와 연관된 키를 생성해야 하는데 이 키를 생성하기 위한 함수를 해시 함수라고 한다.

좋은 해시 함수를 사용하면 해시 테이블에 데이터가 고르게 분포되고, 이는 충돌이 발생할 가능성이 낮다는 뜻이다. 따라서 좋은 해시 함수는 충돌을 덜 일으켜야 하고 계산이 쉬워야 한다.

 

 

 

Hash Collision

서로 다른 두 개의 값 $i_{1}$과 $i_{2}$가 해시 테이블의 같은 주소로 맵핑되면 충돌(collision)이 발생한다고 말한다.
예를 들어, 해시 함수가 f(x) = x % 10인 경우, f(4)와 f(14)는 동일하게 4라는 주소를 갖게 된다. 

충돌을 피하기 위해 배열의 크기를 늘리는 방법도 있지만, 해시 테이블의 목적 자체가 좀 더 적은 메모리로 좀 더 빠르게 데이터에 접근하기 위함이기에 무작정 배열을 늘려나가는 것은 메모리만 잡아먹을 뿐 근본적인 문제를 해결해주지 못한다.
그리고 사실상 수많은 데이터는 1:1로 테이블에 매핑시키는 것도 불가능하다. 때문에 충돌은 '피해야 할 상황'이 아니라 '해결해야 할 상황'인 것이다.

 

 

 

Resolve Collision

해시 테이블의 충돌을 해결하는 방법은 크게 4가지가 있다.

1. 선형 탐색법(Linear Probing) 
2. 이차 탐색법(Quadratic Probing)
3. 재해싱(Rehashing)
4. 체이닝(Chaining)

 

1) 선형 탐색법(Linear Probing)

선형 탐색법은 충돌이 발생했을 때 그 옆자리가 비어있는지 살펴보고, 만약 비었다면 그 자리에 대신 저장하는 방법이다.

해시 함수가 f(x) = x % 7인 경우를 생각해보자.
이때 키가 9인 데이터를 삽입하면 아래와 같이 인덱스가 2인 위치에 저장된다.

다음으로 키가 2인 데이터를 삽입한다고 가정하면, 이미 인덱스가 2인 위치에는 9가 있기 때문에 충돌이 발생한다. 이때 바로 옆자리인 3번 자리가 비어있기 때문에 여기에 2를 삽입하는 것이 선형 탐색법이다.
만약 옆자리가 비어있지 않다면 그다음 자리, 이 자리가 또 비어있지 않다면 또 그다음 자리 이런 식으로 한 칸씩 이동하며 자리를 찾게 된다. 그래서 선형 탐색법에서의 탐색 순서는 아래와 같다.

f(x) -> f(x) + 1 -> f(x) + 2 -> f(x) + 3 -> ...

굉장히 편한 방법이다. 하지만 이러한 방식은 충돌의 횟수가 증가함에 따라 클러스터(cluster) 현상 즉, 데이터가 한 곳으로 몰리는 현상이 발생한다는 단점이 있다. 반드시 한 칸씩 이동하면서 빈칸을 찾아야 하기 때문.

 

2) 이차 탐색법(Quadratic Probing)

선형 탐색법의 단점을 보완하고자 등장한 것이 이차 탐색법이다. 한 칸씩만 이동하지 말고, 좀 더 넓은 간격으로 탐색을 해보자는 것이다. 이차 탐색법의 탐색 순서는 아래와 같다.

f(x) -> f(x) + 1 -> f(x) + 4 -> f(x) + 9 -> ...

하지만 이차 탐색법 역시 단점이 있다. 해쉬 값이 동일하면 탐색하는 위치가 항상 똑같다는 것이다.
예를 들어, 선형 탐색법에서의 예시를 보면 9과 2는 언제나 [2] -> [3] -> [6] -> [11] -> 칸 만을 탐색하게 된다.

 

3) 재해싱(Rehashing)

이차 탐색법의 단점을 보완한 것이 재해싱이다.
재해싱은 충돌이 발생했을 때 또 다른 해시 함수를 통해서 빈칸을 찾는 방법으로, 이중 해시(Double Hashing)라고 불리기도 한다.
이차 탐색법의 단점이 동일한 해시 값을 갖는 경우 다음 탐색 범위가 1^2, 2^2, 3^2 이런 식으로 규칙적이기 때문에 항상 똑같은 곳만 탐색하게 된다는 것인데, 재해싱은 탐색 범위를 불규칙하게 만든다는 것이 포인트이다.

재해싱에서 사용하는 두 개의 해시 함수 역할은 아래와 같다.

1차 해시 함수: 키를 근거로 저장위치를 결정
2차 해시 함수: 충돌 발생시 몇 칸 뒤를 탐색할지 결정

재해싱에서는 건너뛰는 범위가 키에 따라서 달라지기 때문에 클러스터 발생률을 상당히 낮출 수 있다.

 

4) 체이닝(Chaining)

체이닝은 위에서 소개한 방법들과는 완전히 다르다.
앞에서 알아본 선형 탐색법, 이차 탐색법, 재해싱은 열린 주소 방법(Open Addressing Method)의 한 종류이다. 충돌이 발생하면 다른 자리에 대신 저장한다는 의미가 담겨 있다.
체이닝과 같은 유형을 닫힌 주소 방법(Closed Addressing Method)라고 한다. 무슨 일이 있어도 자신의 자리에 저장한다는 의미가 담겨있다. 

체이닝을 구현하는 방법은 크게 배열 기반과 연결 리스트 기반이 있다.

 

배열로 구현하는 경우 해시 값 별로 다수의 키를 저장할 수 있게 된다.
하지만 충돌이 발생하지 않을 경우에 낭비되는 공간이 많아지고, 충돌의 최대 횟수를 미리 고려해서 배열을 선언해야 하기 때문에 쉽지 않다.

 

이러한 이유로 체이닝은 보통 연결 리스트를 기반으로 구현한다.

 

 

 

Hash Table 시간 복잡도

해시 테이블은 배열처럼 인덱스를 통해 키 값에 바로 접근할 수 있으므로 탐색, 삽입, 삭제 모두 평균적으로 $O(1)$의 시간 복잡도가 발생한다.
하지만 충돌이 발생한 경우 이를 해결하는 과정에서 최대 $O(N)$의 시간 복잡도가 발생할 수 있다.

통계적으로 해시 테이블의 공간 사용률이 70% ~ 80% 정도가 되면 해시의 충돌이 빈번하게 발생하여 성능이 저하되기 시작한다고 한다.
또한, 해시 테이블에서 자주 사용되는 데이터를 캐시에 적용하면 효율을 높일 수 있다. 

 

 

 

References

Interview_Question_for_Beginner/tree/master/DataStructure#hash-table

https://mangkyu.tistory.com/102

📖 윤성우의 열혈 자료구조

📖 자료구조 개념 및 구현