Hash Table

해싱이란?(Hashing)

해싱이란 임의의 길이의 값을 해시 함수(Hash Function)을 사용하여 고정된 크기의 값으로 변환하는 작업을 말한다. 이 함수에 의해 반환된 값을 hashcode라고 한다.

어설픈 해시 함수를 통해서 key 값들을 결정하면 동일한 값이 도출될 수가 있다. 이렇게 되면 동일한 key 값에 복수개의 데이터가 하나의 테이블에 존재할 수 있게 되는 것인데 이를 Collision이라고 한다.

좋은 해시 함수는 키의 일부분을 참조하여 해쉬 값을 만들지 않고 키 전체를 참조해서 해쉬 값을 만들어 낸다. 하지만 좋은 해쉬 함수는 키가 어떤 특성을 가지고 있느냐에 따라 달라지게 된다.

해시 함수를 무조건 1:1로 만드는 것보다 Collision을 최소화하는 방향으로 설계하고 발생하는 Collision에 대비해 어떻게 대응할 것인가가 더 중요하다. 1:1 대응이 되도록 만드는 것이 거의 불가능하기도 하지만 그런 해시 함수를 만들어봤자 그건 배열과 다름이 없고 메모리를 너무 차지하게 된다.

충돌이 많아질수록 검색에 필요한 시간 복잡도가 O(1)에서 O(n)에 가까워진다. 어설픈 해시 함수는 해시를 해시답게 사용하지 못하도록 한다. 좋은 해시 함수를 선택하는 것은 해시 테이블의 성능 향상에 필수적인 것이다.

해시 테이블

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

hash는 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다.
특정한 값을 찾는데 데이터 고유의 인덱스에 접근하게 되므로 average case에 대하여 O(1)의 시간 복잡도를 갖는다.(average case에 대하여 O(1)인 것은 충돌 때문이다.)

Direct Address Table(직접 주소 테이블)

가장 간단한 형태의 해시 테이블로 이름 뜻대로 키 값을 주소로 사용하는 테이블을 말한다. 이는 키 값이 10이라고 했을 때 배열의 인덱스 10에 원하는 데이터를 저장하는 것이다.

위 그림에서 키 값이 10이고 인덱스 10에 원하는 데이터를 저장하였다. 코드를 통해 확인해보자.

class DirectAddressTable {
  constructor() {
    this.table = [];
  }

  setValue(value = -1) {
    this.table[value] = value;
  }

  getValue(value = -1) {
    return this.table[value];
  }

  getTable() {
    return this.table;
  }
}

const myTable = new DirectAddressTable();
myTable.setValue(3);
myTable.setValue(10);
myTable.setValue(90);

console.log(myTable.getTable());

찾고자 하는 값과 테이블의 인덱스가 동일하므로 테이블을 뒤적거릴 필요없이 값이 저장된 공간에 바로 접근해서 값을 가져올 수 있으므로 시간복잡도는 O(1)이다. 마찬가지로 테이블에 있는 값을 삽입, 수정, 삭제하는 행위도 값이 어디 있는지만 알고 있으면 모두 한방에 해결할 수 있으므로 역시 O(1)의 시간복잡도로 해결할 수 있다.

하지만 직접 주소 테이블도 당연히 단점이 있다. 바로 공간의 효율성이 좋지 않다는 것이다. 방금 선언했던 myTable의 테이블 상태를 보자.

Array(91) [
 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 90]

위에서도 볼 수 있듯이 저장된 데이터를 제외하고 0으로 채워진 나머지 공간은 값은 없지만 메모리가 할당되어 있는 상태이다. 즉, 사용하지 않는 아까운 공간이다. 즉 테이블에 넣고자 하는 데이터의 값의 범위보다 값의 개수가 작다면 공간적인 효율이 떨어지는 것이다. 그래서 이런 단점을 보완한게 바로 해시 테이블이다.

해시 테이블은 직접 주소 테이블처럼 값을 바로 테이블의 인덱스로 사용하는 것이 아니라 해시 함수에 한 번 통과 시켜서 사용한다. 해시 함수는 임의의 길이를 가지는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.

해시의 충돌(Collision)

다른 값을 해시 함수에 넣었지만 같은 값이 튀어나오는 것이 바로 충돌(Collision)이다. 사실 상식적으로 생각해보면 직접 주소 테이블은 동적으로 테이블을 늘려갔지만 해시 테이블은 처음부터 고정적인 공간을 할당하고 값을 계속 우겨넣는 방식이다. 그렇다면 테이블의 크기를 100으로 잡고 그 테이블에 200개의 데이터를 넣는다면 100개만 저장되고 100개는 남을텐데 얘네는 어떻게 되는걸까?

걱정하지 말자. 애초에 해시 테이블은 담고자 하는 데이터의 개수보다 테이블의 크기를 작게 하고 싶다는 의지에서 나온 자료구조이기 때문에 충돌을 해결할 수 있는 방법 또한 같이 고안되었다.

충돌 해결하기

해시 테이블은 해시의 충돌이라는 단점이 있기 때문에 해시 테이블을 운용할 때 가장 중요한 것은 사실 해시 함수가 얼마나 균일하게 값을 퍼트릴 수 있느냐이다. 어떤 값을 넣어도 같은 인덱스만 주구장창 나올 확률이 높다면 좋은 해시 함수가 아니라는 것이다.

그러나 해시 함수를 아무리 잘 짜더라도 근본적으로 충돌을 완전히 방지한다는 것은 힘든 일이다. 그렇기 때문에 어느 정도 충돌을 감안하되 최소화하기 위해 해시 함수의 알고리즘을 개발하거나, 혹은 충돌이 발생하더라도 우회해서 해결할 수 있는 방법을 사용한다.

Open Address 방식(개방주소법)

해시 충돌이 발생하면, (즉 삽입하려는 해시 버킷이 이미 사용 중인 경우) 다른 해시 버킷에 해당 자료를 삽입하는 방식이다. 버킷이란 바구니와 같은 개념으로 데이터를 저장하기 위한 공간이라고 생각하면 된다.

해시 함수를 통해서 얻은 인덱스가 아니라 다른 인덱스를 허용한다는 의미로 개방 주소(Open Address)라고 한다. 이러한 Open Addressing 방식은 3가지 방법을 통해서 해시 충돌을 처리한다.

선형 탐사(Linear Probing)

선형 탐사는 가장 기본적인 충돌 해결기법으로 바로 인접한 인덱스에 데이터를 삽입해가기 때문에 데이터가 밀집되는 클러스터링(Clustering) 문제가 발생하고 이로인해 탐색과 삭제가 느려지게 된다.

충돌 -> 데이터 덩어리 뒤에 충돌난 값 저장 -> 충돌 발생 확률 증가 -> 충돌 -> 또 저장. 덩어리 더 커짐 -> 충돌 발생확률 증가 -> 충돌..

이런 식으로 무한 반복 사이클이 발생한다.

제곱 탐사법(Quadratic Probing)

제곱 탐사법(Quadratic Probing)은 선형 탐사법과 동일하지만 폭이 고정폭이 아닌 제곱으로 늘어난다는 것이 다르다. 제곱 탐사법을 사용하면 충돌이 발생하더라도 데이터의 밀집도가 선형 탐사법보다 많이 낮기 때문에 다른 해시값까지 영향을 받아서 연쇄적으로 충돌이 발생할 확률이 많이 줄어든다.

이중 해싱(Double Hashing)

말 그대로 해시 함수를 이중으로 사용하는 것이다. 하나는 기존과 마찬가지로 최초 해시를 얻을 때 사용하고, 다른 하나는 충돌이 났을 경우 탐사 이동폭을 얻기 위해 사용 한다. 이렇게 하면 최초 해시로 같은 값이 나오더라도 다시 다른 해시 함수를 거치면서 다른 탐사 이동폭이 나올 확률이 높기 때문에 매번 다른 공간에 값이 골고루 저장될 확률도 높아진다.

Separate Chaining 방식(분리 연결법)

일반적으로 Open Addressing은 Seperate Chaining보다 느리다. Open Addressing의 경우 해시 버킷을 채운 밀도가 높아질수록 Worst Case 발생 빈도가 더 높아지기 때문이다. 반면에 Seperate Chaining 방식의 경우 해시 충돌이 잘 발생하지 않도록 보조 해시 함수를 통해 조정할 수 있다면 Worst Case에 가까워지는 빈도를 줄일 수 있다.

테이블 크기 재할당(Resizing)

해시 테이블은 고정적인 공간을 할당해서 많은 데이터를 담기 위한 자료구조인 만큼 언젠가 데이터가 넘치기 마련이다.

그렇기 때문에 해시 테이블은 꽉꽉 아낌없이 채우기보다는 어느 정도 비워져 있는 것이 성능상 더 좋으며, 해시 테이블을 운용할 때는 어느 정도 데이터가 차면 테이블의 크기를 늘려줘야한다.

이건 특별한 알고리즘이라기보다는 그냥 기존 크기의 두 배정도로 새로운 테이블을 선언해서 기존 테이블의 데이터를 그대로 옮겨 담는 방법을 사용한다. 분리 연결법을 사용한 해시 테이블의 경우 재해싱(Rehashing)을 통해 너무 길어진 리스트의 길이를 나누어서 다시 저장하는 방법을 사용하기도 한다.