해시 테이블(Hash Table)이란

해시 테이블은 해시 함수와 배열을 사용하여 Map을 구현한 자료 구조이다.

배열에 보관한 데이터에 접근하는데 걸리는 시간복잡도는 O(n)이다. Map은 key와 value로 쌍을 이루고 있는 ADT(추상자료구조)로, key를 통해 O(1)의 시간복잡도로 데이터에 빠르게 접근 할 수 있다.

문제는 value와 매칭이 되는 key를 생성하는 방법인데, 직접 주소 테이블(Direct Address Table)이라는 자료구조에서 시작된다. 직접 주소 테이블은 value를 key(Index)로 사용하여 key, value가 동일하다. 이렇게되면 내가 원하는 데이터의 위치를 알고 있기 때문에 상수 시간으로 데이터 접근이 가능하다.

하지만 자료구조에 저장되는 데이터의 값이 1, 22, 333, 4444과 같이 값의 범위가 넓을 경우에는 값을 제외한 나머지 공간은 값이 없지만 메모리를 차지하여 메모리 낭비가된다.

이와같이 직접 주소 테이블은 값의 접근은 쉽지만 공간을 낭비하는 단점이 있다. 이러한 문제를 해결하기 위해 해시 함수를 사용한다.

해시 함수(Hash Function)

해시 함수는 value를 key(Index)로 바로 사용하지 않고, 임의의 과정을 거쳐 임의의 데이터를 생성하여 값에 접근한다. 이때 생성한 임의의 데이터를 해시(Hash)라고 하고, 임의의 데이터를 생성하는 함수를 해시 함수라고 한다. 해시 함수는 key와 hash를 mapping 해준다.

function hashFunc(key) {
  return (key ** 2) % 10;
}

/** 
위의 hashFunc는 매우 단순하지만 key로 일정 범위 내에서 항상 같은 해시를 생성해준다.
*/
hashFunc(1) // 1
hashFunc(22) // 4
hashFunc(333) // 9
hashFunc(4444) // 6

해시 테이블은 해시 함수가 생성하는 해시의 범위만큼 값이 들어갈 수 있는 공간을 가지기 때문에, 값의 범위가 크더라도 공간을 낭비하지 않을 수 있다. 그렇기 때문에 해시 함수는 해시의 범위가 너무 넓지 않으면서 잘 분포될 수 있게 동작되어야 한다.

해시 충돌(Hash Collision)

해시가 골고로 분포되지 않는다면 하나의 해시에 두개 이상의 값이 할당될 수 있다. 해시 테이블은 모든 값을 축소된 공간에 보관하는 목적이기 때문에, 하나의 해시에 하나의 value가 mapping 될 수 는 없다. 그렇기 때문에 key가 달라도 해시 함수를 거쳤을 때, 같은 해시가 나올 수도 있다. 이런 경우를 해시 충돌(Hash Collision)이라고 한다.

해시 충돌을 해결하는 방법은 크게 2가지가 있다.

1. 분리 연결법(Seperate Chaining)

해시 테이블의 value가 보관되는 곳을 버킷(bucket), 빈(bin), 슬롯(slot)이라고 한다. 버킷에는 하나의 값이 아닌 여러 값이 보관될 수 있다. 값들은 링크드 리스트(Linked List)나 트리(Tree)를 사용한다.

새로운 값을 보관하기 위해 해시 함수로 해시를 통해, 해시 테이블에 접근했는데 이미 기존의 값이 있다면 기존 값과 함께 새로운 값을 저장한다. 해시값이 같은 경우에 나중에 값에 접근할 때 다른 값을 구분하기 위해 키도 같이 저장해야 한다.

링크드 리스트나 트리의 경우에는 데이터에 접근하는 시간 복잡도가 상수시간이 아니므로, 해시 함수는 하나의 버킷에 데이터가 많이 몰리지 않게 분산시켜줘야 한다.

2. 개방 주소법(Open Address)

해시가 같은 경우, 버킷에 기존 값이 존재하면 주소 주변을 탐사하여 새로운 공간을 찾는다. 개방 주소법 내에서도 새로운 공간을 찾는 방법은 3가지가 있다.

1. 선형 탐사법(Linear Probing)

• 선형 탐사법은 충돌이 난 주소의 바로 옆의 주소부터 선형으로 탐사한다. 선형 탐사법의 경우, 특정 해시의 주변에 데이터가 연속되게 저장될 가능성이 높아진다. 이렇게 되면 해시가 계속 충돌될 확률이 높아진다.
  (1차 군집화)

2. 제곱 탐사법(Quadratic Probing)

• 제곱 탐사법은 선형 탐사법과 방식은 동일하지만, 바로 옆의 주소가 아닌 제곱한 주소를 탐색한다. 제곱으로 주소를 탐색하기 때문에 선형 탐사법에 비해 데이터가 연속되게 저장될 가능성은 낮지만, 제곱 탐사법으로 같은 해시 값으로 인해 계속 충돌이 나는 것까지 해결할 수는 없다.
  (2차 군집화)

3. 이중 해싱(Double Hashing)

• 이중 해싱은 해시 주소에 기존 값이 있을 경우, 두번째 해시 함수를 사용하여 기존 해시에 새로운 해시를 더하여 탐색한다. 해시를 두번 사용하기 때문에 기존의 방법들보다 데이터가 골고루 분포될 확률이 높아진다.

테이블 리사이징(Table Resizing)

해시 테이블은 고정된 공간에 데이터를 담기 위한 자료구조로 데이터가 고정된 공간을 넘칠 수 있다. 분리 연결법의 경우에 하나의 버킷에 저장되는 데이터가 너무 많아 접근하는데 시간을 많이 사용하거나, 개방 주소법의 경우에는 실제 테이블의 공간이 일정 수준 이상으로 찼을 때이다.

테이블 리사이징은 기존 테이블 크기의 2배 크기의 테이블 선언하여, 기존 테이블의 데이터를 옮긴다. 자바의 경우, 테이블 공간의 3/4 이상을 차지하면 리사이징을 한다. 이는 사용하는 언어에 따라 리사이징 되는 수치는 다르다.

테이블 리사이징을 하게 되면, 중첩되는 해시의 경우 다시 해시하여 다른 해시로 값을 이동하기도 한다.