[자료구조] Hash Table

해시 함수

• 임의의 길이를 갖는 메시지를 입력받아서 고정된 길이의 해시값을 출력하는 함수
• 함수를 수행하기 전의 원래의 데이터를 키 [key], 해시 함수를 수행한 결과값을 해시 값 [hash value]라고 합니다.
• 키를 해시 값으로 매핑하는 전체적인 과정을 해싱 [Hashing]이라고 합니다.
• 만약 다른 키에 대해 해시값이 중복된다면, 이를 해시 충돌[Collision]이라고 합니다.

해시 테이블

• 해시 테이블이란 해시함수를 사용하여 변환한 값을 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조를 말한다.
• 기본연산으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있고 시간복잡도는 평균적으로 O(1)이다.

충돌 해결 방법

1. Open Addressing[개방 주소법]

• 원래라면 해시함수로 얻은 해시값에 따라서 데이터와 키값을 저장하지만 동일한 주소에 다른 데이터가 있을 경우 다른 주소도 이용할 수 있게 하는 기법이다.
• Open addressing 방식은 3가지 방법을 통해서 해시 충돌을 처리한다.

선형탐사[Linear Probing]

• 최초 해시값에 해당하는 버킷에 다른 데이터가 저장되어 있으면, 해당 해시값에서 고정 폭(ex. 1칸)만큼 옮겨가면서 다음 해시값에 해당하는 버킷에 데이터가 있다면 계속 반복하고, 데이터가 없는 버킷을 찾는다면 해당 버킷에 저장한다.
• 선형탐사는 바로 인접한 인덱스에 데이터를 삽입해가기 때문에 데이터가 밀집되는 클러스터링(Clustering) 문제가 발생하고 이로인해 탐색과 삭제가 느려지게 된다.

제곱탐사[Quadratic Probing]

• 선형 조사가 고정폭만큼 이동하며 조사한다면, 제곱 조사는 이동 폭이 제곱수로 늘어난다는 특징이 있습니다.
• 이는 초기 해시값이 같을 경우에 역시나 클러스터링 문제가 발생하게 된다.

이중해싱[Double Hashing]

• 이중해싱은 선형탐사와 제곱탐사에서 발생하는 클러스터링 문제를 모두 피하기 위해 도입된 것이다. 처음 해시함수로는 해시값을 찾기 위해 사용하고 두번째 해시함수는 충돌이 발생했을 때 탐사폭을 계산하기 위해 사용되는 방식이다.

2.Separate Chaining[분리 연결법]

• 분리 연결법은 개방 주소법과는 달리 한 버킷(슬롯) 당 들어갈 수 있는 엔트리의 수에 제한을 두지 않는다. 이때 버킷에는링크드 리스트(linked list)나 트리(tree)를 사용한다.
• 체이닝이란 충돌이 발생했을 때 이를 동일한 버킷(Bucket)에 저장하는데 이를 연결리스트 형태로 저장하는 방법이다.
• 해시 충돌이 일어나더라도 linked list로 노드가 연결되기 때문에 index가 변하지 않고 데이터 개수의 제약이 없다는 장점이 있다.
• 하지만 메모리 문제를 야기할 수 있으며, 테이블의 부하율에 따라 선형적으로 성능이 저하된다. 따라서 부하율이 작을 경우에는 open addressing 방식이 빠르다.

3. Open Address vs Separate Chaining

Open Address

• 데이터의 개수가 충분히 적을 때 사용한다.
• 연속된 공간에 데이터를 저장하기 때문에 Separate Chaining에 비해 캐시 효율이 높기 때문이다.

Separate Chaining

• 위의 경우를 제외하고 사용한다.
• 테이블의 확장을 Open Address 방식보다 줄일 수 있다.Open Address 방식은 버킷을 계속해서 사용하기 때문이다.

해시 버킷 동적 확장 [Resize]

• 해시 버킷의 개수가 적다면 메모리 사용을 아낄 수 있지만 해시 충돌로 인해 성능상 손실이 발생한다. 그래서 HashMap은 Key-Value 쌍 데이터 개수가 일정 개수 이상이 되면 해시 버킷의 개수를 두 배로 늘린다. 이렇게 늘리면 해시 충돌로 인한 성능 손실 문제를 어느 정도 해결할 수 있다.
• 해시 버킷의 크기를 두 배로 확장하는 임계점은 현재 데이터의 개수가 해시 버킷의 개수의 75%가 될 때이다. 0.75라는 숫자는 load factor 라고 불린다.