Hash Table

Hash Table이란?

해시 테이블은 해시 함수를 통해 Key 를 테이블의 인덱스로 변환하여 해당 인덱스에 Value 를 저장하는 자료구조입니다. 이때 해시 함수를 통해 변환된 Key 의 값을 Hash Value 라고 합니다.

해시 테이블은 넓은 범위를 가진 Key 를 한정된 범위를 가진 Hash Value 로 변환함으로써 데이터를 효율적으로 저장, 관리하기 위해 사용합니다.

해시 테이블은 넓은 범위의 Key 를 한정된 범위를 가진 Hash Value 로 변환하기 때문에 서로 다른 Key 가 동일한 Hash Value 로 변환되는 해시 충돌(Collision)이 발생할 수 있는데 이 충돌을 어떻게 관리하느냐에 따라 해시 테이블의 성능이 결정됩니다.

해시 함수

Division Method

h(k) = k mod n

Division Method에서 해시 함수는 Key 를 해시 테이블의 크기 n 으로 나누어 Hash Value 로 만드는 함수입니다. 간단하고 빠르게 Hash Value 를 계산해낼 수 있지만 해시 테이블의 크기가 결정되야 합니다. 이때 이 해시 테이블의 크기 n 은 2의 제곱수와는 거리가 먼 소수를 사용하는 것이 좋다고 알려져 있습니다.

Multiplication Method

h(k) = (kA mod 1) x n  (0 < A < 1)

Multiplication Method는 Division Method보다는 느리지만 해시 테이블 크기의 중요성을 낮춘 방식입니다. 일반적으로 해시 테이블의 크기 n 은 2의 제곱수로 정한다고 알려져있습니다.

해시 충돌 관리 - Chaining

Chaining

Chaining 기법은 해시 충돌이 발생했을 때 Value 를 동일한 Bucket 에 Linked list 형태로 저장합니다.

Chaining 기법을 이용한 해시 테이블의 삽입 연산은 Bucket 의 Linked list 맨 뒤에 데이터를 삽입하면 되므로 O(1) 의 시간복잡도를 갖습니다.

탐색 연산과 삭제 연산은 Linke list에서 해당 데이터를 찾아야 하므로 O(α) 의 시간복잡도를 갖습니다. 여기서 α는 적재율(Key 의 개수 ÷ 해시 테이블의 크기)를 말합니다.

해시 충돌 관리 - Open Addressing

Open Addressing

Open Addressing 기법은 해시 충돌이 발생했을 때 Value 를 해시 테이블의 다른 Bucket 에 저장합니다. 이때 데이터가 저장될 Bucket 을 선택하는 방법에는 여러가지가 존재합니다.

Linear Probing

Linear Probing 기법은 해시 충돌이 발생했을 때 Value 를 해당 Bucket 다음의 비어있는 Bucket 들 중 가장 인접한 Bucket 에 저장합니다.

Linear Probing 기법은 데이터가 밀집하게 되는 Clustering 이 발생할 수 있고 이는 해시 테이블의 탐색 성능을 저하시킵니다.

Quadratic Probing

Linear Probing 기법이 비어있는 Bucket 을 찾기 위해 한칸씩 선형적으로 탐색을 한다면 Quadratic Probing은 1, 4, 9, 16 등 제곱수만큼 떨어져있는 Bucket 을 탐색합니다. 하지만 이 방법 역시 Clustering 문제가 여전히 존재합니다.

Double Hashing

Double Hashing 기법은 두 개의 해시 함수를 사용하여 Clustering 을 방지하는 기법입니다.

첫번째 해시 함수는 다른 기법과 마찬가지로 Key 를 Hash Value 로 바꾸는 함수입니다. 두번째 해시 함수는 충돌이 발생하여 비어있는 Bucket 을 찾을 때 탐사 폭을 결정하는 함수입니다.