Week 2 : 해시테이블(Hash Table)

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

{key: value} 값으로 저장하는 자료구조 중 평균적으로 매우 빠른 삽입, 삭제, 탐색 속도를 제공하는 자료구조이다.

해시테이블은 key값에 해시함수(hash function)를 이용해 매핑하고 데이터(value)의 값을 key값과 함께 저장한다. 해시테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 hashing(해싱)이라고 하며, 이때 데이터가 저장되는 곳은 slot 혹은 bucket이라고 한다. 전체적인 구조는 그림과 같다.

해시테이블에 슬롯을 할당할 때 일반적으로 가장 많이 사용하는 방법은 division이다. key % hashtable size 기준으로 저장하는 것인데, 이와 같이 저장하게 되면 {Sarah : 918-512} 라는 key:value 값은 % 10되어 슬롯 2에 저장된다.

근데 이러한 방식으로 저장하게 된다면, 나중에 들어오는 value 중 또 나머지가 2인 값이 생길 수 있다. 나머지가 2이기 때문에 슬롯 2에 저장되어야 하는데 이미 슬롯이 차있기 때문에 저장을 할 수가 없는 것이다. 이를 충돌(collision)이 일어났다고 한다. 그래서 우리는 collison resolution method, 즉, 충돌 해결 방법을 고안해 충돌을 피하고 다른 곳에 데이터를 저장해야한다. 충돌이 할당되어있는 슬롯의 수보다 많이 발생하게 되면 더 이상 슬롯에 저장할 수 없는 overflow 현상이 발생한다.

해시테이블은 삽입, 삭제, 제거 3가지의 평균 연산 시간이 0(1)로 상당히 빠르지만, 최악의 경우 0(n)으로 늘어날 수도 있다. 따라서 해시테이블은 해시 함수를 어떠한 기준으로 매핑할지, 그리고 어떤 충돌 해결 방법을 쓸지 잘 고안해 설계해야한다. 좋은 해시테이블은 충돌이 적고 빠른 계산을 할 수 있어야하는데, 보통 충돌이 적으면 계산 속도가 느려지고 계산 속도가 빠르면 빠른 속도에 비례해 충돌이 많아지기 때문에 좋은 해시테이블을 만드는 것은 정말 어렵다.

좋은 해시함수란?

정말 이상적인 해시함수는 완전 해시 함수(Perfect Hash function) 라고 하는데, 하나의 슬롯에 하나의 키가 각각 중복없이 배치되는 완전한 해시 함수이다. 하지만 이것은 말 그대로 '이상적인' 것이며, 거의 찾아볼 수 없다. 키값 자체를 슬롯번호로 사용하면 충돌이 일어나지 않게 구현할 수 있으나 저장공간이 매우 커서 굉장히 비효율적이다.

그래서 대체재로 Universal Hash Function을 사용하는데, 다음과 같다.

pr(f(x) == f(y)) = 1/hashtable_size

x와 y라는 서로 다른 입력값이 충돌할 확률(pr)이 전체 해시테이블의 사이즈에 반비례하는 해시함수이다. 하지만 이조차 구현하기 어렵기 때문에 C-universal Hash Function, 즉 C / hashtable_size로 만들기도 한다.

충돌 해결 방법(Collision Resolution Method)

Open Addressing(개방 주소법)

한 슬롯 당 하나의 키만 저장하며, 메모리 문제는 없으나 충돌이 발생할 수 있다. 충돌하면 해당 슬롯 대신 주위 슬롯에 저장하는 방법이다. 해시 충돌은 탐사(probing)방식으로 해결할 수 있다.

1. Linear Probing(선형 탐사) - 선형 탐사는 충돌이 발생하면 바로 밑칸에 저장된다. 밑에 있는 슬롯도 차있다면, 계속 밑으로 내려가면서 저장할 수 있는 슬롯을 체크한다.

2. Quadratic Probing(제곱 탐사)- 충돌이 일어날 시 1^2, 2^2, 3^2의 방식으로 이동할 폭이 제곱으로 늘어난다. 다만, 초기값이 같은 여러 개의 데이터가 있을 때 취약하다. 초기 해시값이 같으면 다음 탐사 위치가 동일하기 때문에 탐사를 여러 번 반복해야 하는 것이다.

3. Double Hashing(이중 해싱) - 해시 함수를 2개 사용해 탐사의 규칙성을 없애는 방식이다. 한 함수는 처음 해시값을 얻을 때, 다른 함수는 해시 충돌이 일어났을 때 탐사의 이동폭을 얻기 위해 사용한다. 처음 해시값이 같아도 탐사 이동폭이 달라지고, 탐사 이동폭이 같더라도 최초 해시값이 달라지기 때문에 clustering을 완화할 수 있다.

Rehashing(리해싱)

리해싱에 대해 설명하기 전에, 클러스터에 대해 먼저 설명하겠다. 키들이 군집해있는 형태를 cluster라고 하는데, 이는 최대한 피해야한다. 키들이 밀집해있으면 충돌할 가능성 또한 높아지기 때문이다.
클러스터의 크기에 영향을 미치는 건 해시함수, 충돌 해결 방법 그리고 load factor가 있다. load factor란 해시테이블에 값을 얼마나 수용하고 있는지에 대한 것을 나타낸다.

 load factor = n/m
 n = 저장된 item 개수
 m = abs(hashtable_size) - slot 개수
 0 < n/m < 1

고로 load factor는 항상 0보다는 크고 1보다는 작은 수이다. 1에 가까울수록 수행시간이 길어지므로 비효율적이다. 선형 탐사는 충돌이 일어났을 때 밑칸에 저장하기 때문에 계속 cluster + 1이 된다. 고로 별로 좋은 해시테이블은 아니다.

load factor을 줄이기 위해서는 리해싱을 사용하면 좋은데, 기존 테이블에 비해 2배 큰 테이블로 데이터를 옮기는 방식이다. 예를 들어 최소 50% 이상 빈 슬롯을 유지하고싶다면, 슬롯이 50% 이상 찼을 때 2배 큰 테이블을 만들어 데이터를 옮기면 된다. 이렇게 하면 평균적인 클러스터 사이즈가 O(1), 항상 상수 정도의 크기밖에 되지 않는 것이다. 그 기준은 30%나 70%가 되어도 상관이 없다. 얼마가 기준이던 간에 상수정도의 크기를 유지할 수 있게 만들어준다. 단, 해시테이블은 70~80%정도 차게 되면 성능이 저하되기 때문에 그 전에 테이블을 교체하는 것이 바람직하다.

Seperate Chaining (분리 연결법)

분리 연결법은 하나의 슬롯에 데이터를 여러 개 저장할 수 있다. 각 슬롯에 한방향 연결 리스트를 추가하여 어떠한 데이터가 들어오는지에 상관없이 리스트의 개수를 계속 늘려서 값을 받을 수 있는 것이다. 1:1로 받는 방식이 아니기 때문에 해시 테이블의 확장이 불필요하며 쉽게 구현하고 데이터를 삭제할 수 있다.

사진 출처 : https://www.krivalar.com/data-structures-open-hashing

참고자료 : 한국외대교수님 강의
https://mangkyu.tistory.com/102
https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/