자바스크립트의 해시테이블

해시테이블에 대해 공부하게 된 사연..

백준에서 알고리즘 문제를 풀다 똑같은 로직인데, 배열로 value에 접근할 때와 object를 사용해 구현한 Map 을 통해 value에 접근했을때 속도차이가 유의미하게 나는 것을 경험했다.

자바스크립트에서 배열은 객체 보다 더 나은 성능을 가진다.

자바스크립트의 배열은 배열을 흉내낸 객체이다. 따라서 배열 요소에 접근할 때 일반적인 배열보다 느릴 수밖에 없는 구조적인 단점을 보완하기 위해 모던 자바스크립트 엔진은 배열을 일반 객체와 구별하여 좀 더 배열처럼 동작하도록 최적화하여 구현했다.

위 자료를 근거로 배열과 객체를 모두 사용할 수 있는 경우가 있다면 배열을 통해 value에 접근하는 편이 더 성능상 유리하다는 것을 알았다. (나는 객체를 Map 처럼 만들어서 사용할때 이도 O(1) 의 시간 복잡도를 가지기에 비슷할 줄 알았다.)

또한 이를 공부를 하면서 자바스크립트 객체는 해쉬테이블을 사용하여 구현한다는 것을 알게되었다.

하지만 해쉬테이블에 대해서는 자세하게 알지 못했고 이번기회에 설명할 수 있을 정도로 공부를 해보자고 생각했다.

지금 부터의 글은 아래 글을 요약한 내용이다. 자세한 내용은 아래 글을 참고하면 좋을 것 같다.

https://evan-moon.github.io/2019/06/25/hashtable-with-js/

JavaScript와 함께 해시테이블을 파헤쳐보자

이번 포스팅에서는 많이 사용되는 자료구조 중 하나인 에 대해서 정리하려고 한다. 먼저 이 무엇인지, 왜 사용하는지 알아보자!

evan-moon.github.io

해쉬 테이블 (Hash Table)

해시 테이블은 어떤 특정 값을 받으면 그 값을 해시 함수에 통과시켜 나온 인덱스(index)에 저장하는 자료구조이다.

이는 직접 주소 테이블(Direct Address Table)의 단점을 보완하기 위해 만들어졌다.

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

직접 주소 테이블은 입력받은 value가 곧 key가 되는 데이터 매핑 방식이다.

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());

// 코드 출처: https://evan-moon.github.io/2019/06/25/hashtable-with-js/

즉, 5 라는 값이 들어간다면 5번 인덱스에 매핑이 되는 것이다.

이는 O(1)의 시간복잡도를 가진다. 하지만 직접 주소 테이블(Direct Address Table)은 공간 복잡도에 관한 단점을 가진다.

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

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]

 // 코드 출처: https://evan-moon.github.io/2019/06/25/hashtable-with-js/

위 처럼 데이터 듬성듬성한 데이터 구조를 가질 수 있다.

만약 index 가 10000 인 값이 직접 주소 테이블에 들어가게 되면 0 ~ 9999 까지의 공간에는 값이 없고 10000 인덱스에만 값이 존재하는 비효율적인 데이터가 생길 수 있다.

해시 함수(Hash Function)

위와 같은 직접 주소 테이블의 비효율을 막기 위해 해시 테이블은 해시 함수를 사용하여 의도된 데이터에 input value 를 매핑한다.

* 해쉬 함수가 리턴하는 값을 해시(Hash) 라고 부른다.

아래는 해쉬 함수의 예시이다.

function hashFunction (key) {
  return key % 10;
}

console.log(hashFunction(102948)); // 8
console.log(hashFunction(191919191)); // 1
console.log(hashFunction(13)); // 3
console.log(hashFunction(997)); // 7

// 코드 출처: https://evan-moon.github.io/2019/06/25/hashtable-with-js/

위 해쉬 함수에서 반환되는 값은 0~9 사이의 값이라는 것이 보장된다.

이를 이용하면 직접 주소 테이블에 5000 값이 들어올 경우 0~4999까지 빈 값을 할당하는 것이 아닌 해쉬함수를 통해 5000을 0 으로 바꾸어 사용함으로써 직접 주소 테이블의 공간 복잡도 문제를 해결할 수 있다.

const myTableSize = 10;
const myHashTable = new Array(myTableSize);

function hashFunction (key) {
  // 들어온 값을 테이블의 크기로 나눠주고 나머지를 반환하면 된다.
  return key % 5;
}

myHashTable[hashFunction(1991)] = 1991;
myHashTable[hashFunction(1234)] = 1234;
myHashTable[hashFunction(5678)] = 5678;

console.log(myHashTable); // [empty, 1991, empty, 5678, 1234]

// 코드 출처: https://evan-moon.github.io/2019/06/25/hashtable-with-js/

해시의 충돌(Collision)

하지만 해시함수를 사용해도 문제점이 발생하는데, 해시 충돌이 발생한다는 것이다.

hashFunction(1991) // 1
hashFunction(6) // 1

// 코드 출처: https://evan-moon.github.io/2019/06/25/hashtable-with-js/

이러한 충돌을 해결하기 위해서는 얼마나 균일하게 값을 퍼트리냐가 관건이 된다.

개방 주소법(Open Address)

개방 주소법은 해시 충돌이 발생하면 테이블 내의 새로운 주소를 탐사 한 후, 비어있는 곳에 충돌된 데이터를 입력하는 방식이다.

이러한 개방 주소법은 어떤 방식으로 비어있는 공간을 탐사할 것이냐에 따라 3가지로 나누어진다.

1. 선형 탐사법

위에서 충돌이 발생했던 1991 과 6의 상황을 예시로 선형탐사법을 알아보자.

0	1	2	3	4	5
	1991

처음에 1991을 해시 함수에 통과시킨 인덱스는 1 일 것이다. 그 후 6 또한 해시 함수를 통과했을 때 값이 1이 되므로 충돌이 발생한다.

선형 탐사법은 이렇게 충돌이 났을때 정해지 n칸 만큼 옆 방을 주는 방법이다.

만약 n = 1 이라면 충돌을 다음과 같이 처리할 것이다.

0	1	2	3	4	5
	1991	6

하지만 선형 탐사법은 같은 해시가 여러번 나오는 경우 데이터가 연속되게 저장될 가능성이 높아진다. 이를 Primary clustering 이라고 한다.

또한 아래와 같은 데이터 구조에서는 연속적인 탐사가 발생한다.

0	1	2	3	4	5
	1991	6	11	21

1번 인덱스 탐사 -> 2번 인덱스 탐사 -> 3번 인덱스 탐사 -> 4번 인덱스 탐사

극단적인 경우에 굉장히 많은 횟수의 탐사를 진행해야할 것이다.

2. 제곱 탐사법(Quadratic Probing)

제곱 탐사법은 선형 탐사법의 단점을 그나마 보완한 방법이다. 제곱 탐사법은 탐사하는 폭이 고정폭이 아닌 제곱으로 늘어난다.

첫번째 충돌이 발생했을 때는 충돌난 지점으로 부터 1² 만큼, 두번째 충돌이 발생했을 때는 2² , 세번째는 3² 과 같은 식으로 탐사하는 스텝이 빠르게 커진다.

0	1	2	3	4	5	6	...	10
	1991	6			11			21

첫번째 충돌이 났을 때 6은 충돌이 난 1번 인덱스로 부터 1² = 1만큼의 옆 방에 들어간다. 두번째 충돌이 났을 때 11 은 충돌이 난 1번 인덱스로 부터 2² = 4만큼의 옆 방에 들어간다. 세번째 충돌이 났을 때 21은 충돌이 난 1번 인덱스로 부터 3² = 9만큼의 옆 방에 들어간다.

이렇게 제곱 탐사법을 사용하면 충돌이 발생하더라도 데이터의 밀집도가 선형 탐사법보다 많이 낮기 때문에 다른 해시값까지 영향을 받아서 연쇄적으로 충돌이 발생할 확률이 많이 줄어든다.

그래도 결국 해시로 1이 여러번 나오면 계속 충돌이 나는 것은 피할 수 없다. 결국 데이터의 군집은 피할 수 없는 숙명이므로 이 현상을 이차 군집화(Secondary Clustering)이라고 부른다.

3. 이중해싱(Double Hashing)

이중해싱은 제곱 탐사법을 개선한 방법이다. 말 그대로 해시 함수를 이중으로 사용하는 것이다.

하나는 기존과 마찬가지로 최초 해시를 얻을 때 사용하고, 다른 하나는 충돌이 났을 경우 탐사 이동폭을 얻기 위해 사용한다.

이때 테이블 사이즈와 두번째 해시함수에 사용될 수는 둘 다 소수를 사용하는 것이 좋다. 둘 중에 하나가 소수가 아니라면 결국 언젠가 같은 해싱이 반복되기 때문이다.

const myTableSize = 23; // 테이블 사이즈가 소수여야 효과가 좋다
const myHashTable = [];

const getSaveHash = value => value % myTableSize;

// 스텝 해시에 사용되는 수는 테이블 사이즈보다 약간 작은 소수를 사용한다.
const getStepHash = value => 17 - (value % 17);

const setValue = value => {
  let index = getSaveHash(value);
  let targetValue = myHashTable[index];
  while (true) {
    if (!targetValue) {
      myHashTable[index] = value;
      console.log(`${index}번 인덱스에 ${value} 저장! `);
      return;
    }
    else if (myHashTable.length >= myTableSize) {
      console.log('풀방입니다');
      return;
    }
    else {
      console.log(`${index}번 인덱스에 ${value} 저장하려다 충돌 발생!ㅜㅜ`);
      index += getStepHash(value);
      index = index > myTableSize ? index - myTableSize : index;
      targetValue = myHashTable[index];
    }
  }
}

// 코드출처: https://evan-moon.github.io/2019/06/25/hashtable-with-js/

console.log(setValue(1991));
console.log(setValue(6));
console.log(setValue(11));
console.log(setValue(21));

13번 인덱스에 1991 저장! 
6번 인덱스에 6 저장! 
11번 인덱스에 11 저장! 
21번 인덱스에 21 저장! 

// https://evan-moon.github.io/2019/06/25/hashtable-with-js/

위 예시에선 이중 해싱을 사용하여 해시 충돌이 없어진 것을 확인할 수 있다. 따라서 클러스터링을 효과적으로 피할 수 있다.

분리 연결법(Separate Chaining)

분리 연결법은 개방 주소법과는 다른 개념으로 접근하는 충돌 우회 방법이다.

분리 연결법은 해쉬 테이블의 버킷에 하나의 값이 아니라 링크드 리스트(Linked List)나 트리(Tree)를 사용한다.

위의 value 를 5로 나눈 나머지를 반환하는 HashFunction 사용한 예제를 그대로 사용해보자.

1991, 6, 11, 21을 저장할 때 분리 연결법을 사용하면 이렇게 된다.

0	1	2	3	4
	[21, 11, 6, 1991]

자세히 보면 [1991, 6, 13, 21]의 순서가 아니라 [21, 13, 6, 1991]의 순서로 뒤집혀 있다. 이는 데이터를 삽입할 때 조금이라도 수행 시간을 줄이기 위해서 사용하는 방법이다.

왜 그런지 설명하기 위해서 우리 테이블의 1번 인덱스에 저장된 링크드 리스트가 [1991, 6, 13, 21] 순서일때를 살펴보자.

1	2	3	4
{값: 1991, 다음 노드:2}	{값: 6, 다음 노드:3}	{값: 13, 다음 노드: 4}	{값: 21, 다음 노드:null}

만약 이번에 추가할 값이 26이라고 해보자. 일단 메모리 주소가 99인 곳이 남길래 여기에 { 값: 26, 다음 노드: null }을 저장했다. 그 후 이 새로운 노드를 리스트에 붙혀야 하니까 해당 리스트의 마지막 노드인 메모리 4에 저장된 노드까지 찾아가야 한다.

그 다음에 메모리 4에 저장된 값을 { 값: 21, 다음 노드: 99 }로 바꿔준다.

1	2	3	4	99
{값: 1991, 다음 노드:2}	{값: 6, 다음 노드:3}	{값: 13, 다음 노드: 4}	{값: 21, 다음 노드:99}	{값: 11, 다음 노드:null}

문제는 새 노드를 리스트에 붙히기 위해서 메모리 4에 저장된 노드를 찾는 과정이다.

먼저 리스트의 머리인 메모리 1부터 찾은 다음에 다음 메모리 주소 값을 확인하고 2로 이동해서 또 다음 메모리 주소를 확인하고… 리스트의 길이가 길어지면 수행 시간도 비례해서 늘어나기 때문에 확실히 비효율적일 것이다.

하지만 순서를 뒤집으면 데이터 삽입이 한결 쉬워진다.

99	1	2	3	4
{ 값: 11, 다음 노드:1 }	{ 값: 1991, 다음 노드: 2 }	{ 값: 6, 다음 노드: 3 }	{ 값: 13, 다음 노드: 4 }	{ 값: 21, 다음 노드: null }

앞에 노드를 추가하는 것이기 때문에 다른 노드를 탐색할 필요없이 그냥 메모리에 밀어넣고 { 값: 11, 다음 노드: 1 }이라고 저장해주면 되기 때문이다. 그래서 해시 테이블에 저장할 때도 리스트의 꼬리(Tail)로 데이터를 붙히기보다는 머리(Head)에 붙히는 방법을 보통 많이 사용한다.

대신 이렇게 분리 연결법을 사용하려면 해시 함수의 역할이 굉장히 중요하다. 결국 균일하지 못한 해시를 사용해서 특정 인덱스에 데이터가 몰리게 된다면 다른 곳은 텅텅 비어있는데 한 버킷에 저장된 리스트의 길이만 계속 길어지기 때문이다.

0	1	2	3	4
	[21, 11, 6, 1991, 26, 31]

결국 내가 찾고자 하는 값이 리스트의 맨 마지막에 위치하고 있다면 링크드 리스트를 처음부터 끝까지 다 탐색해야하기 때문에 O(n)의 시간복잡도를 가지게 된다. 그렇기 때문에 최대한 저장하고 하는 데이터를 균일하게 퍼트려서 리스트의 길이를 어느 정도로 유지해주는 해시 함수의 역할이 중요하다.

테이블 크기 재할당(Resizing)

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

개방 주소법을 사용하는 경우에는 위에서 예시로 작성했던 코드에서 풀방입니다가 출력되는 상황, 즉 테이블이 실제로 꽉 차서 더이상 저장을 못하는 상황이 발생할 것이고, 분리 연결법을 사용하는 경우에는 테이블에 빈 공간이 적어지면서 충돌이 발생할 수록 각각의 버킷에 저장된 리스트가 점점 더 길어져서 리스트를 탐색하는 리소스가 너무 늘어난 상황이 발생할 것이다.

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

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

참고자료