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

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

해시 테이블(Hash Table)이 뭔가요?

해시 테이블은 어떤 특정 값을 받으면 그 값을 해시 함수에 통과시켜 나온 인덱스(index)에 저장하는 자료구조이다. 보통 배열을 사용해서 구현하는 경우가 많은 것 같다. 일단 해시 함수가 뭐길래 사용한다는 건지 해시가 뭔지 설명하기 전에 해시 테이블이라는 개념이 어디서부터 출발한 것인지 알아보자.

직접 주소 테이블(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());

만약 데스크톱으로 이 포스팅을 보고 있다면 이 코드를 복붙한 후 브라우저 콘솔이나 NodeJS로 실행해보자.(물론 IE에서는 안돌아간다) 그러면 콘솔에 우리의 이쁜 테이블이 출력된다.

[ <3 empty items>, 3, <6 empty items>, 10, <79 empty items>, 90 ]

우리가 3을 테이블에 넣으면 이 값은 배열의 3번 인덱스의 요소가 되고 90을 넣으면 90번 인덱스의 요소가 된다. 그야말로 초 심플하다. 이렇게 직접 주소 테이블을 사용할때는 들어오는 값이 뭔지 알면 이 값이 저장된 인덱스도 함께 알 수 있기 때문에 저장된 데이터에 바로 접근해서 값을 가져올 수 있다.

myTable.getValue(3); // 3

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

보통 이런 단순한 자료구조에서 값을 탐색, 삽입, 수정, 삭제하는 알고리즘이 시간을 잡아먹게 되는 이유는 대부분 비슷비슷하다.

1. 내가 찾고 싶은 값이 어디 있는지 모른다. 일단 효율적으로 뒤져보자.(이진트리탐색 같은 경우)

2. 내가 이 값을 삽입하거나 삭제하면 다른 값이 영향을 받는다.(링크드 리스트 같은 경우)

   ---

이렇게 직접 주소 테이블은 내가 보고 싶은 값이 어디 있는지 알고 있기 때문에 바로 접근해서 이후 작업을 수행할 수 있다는 점에서 굉장히 편리하다고 할 수 있다.

하지만 직접 주소 테이블도 당연히 단점이 있다. 바로 공간의 효율성이 좋지 않다는 것이다. 방금 선언했던 myTable의 테이블 상태를 한번 보면 이해가 바로 된다. 이 테이블에는 3, 10, 90의 값을 넣었고 이 값들은 크기 차이가 꽤나 큰 편이다.

그 결과 우리의 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으로 채워진 나머지 공간은 값은 없지만 메모리 공간은 할당되어 있는 상태인 것이다. 즉, 사용하지 않는 아까운 공간이다. 즉 테이블에 넣고자 하는 데이터의 값의 범위보다 값의 개수가 작다면 공간적인 효율이 떨어지는 것이다.

이런 상황을 적재율이 낮다라고 표현하는데, 적재율은 값의 개수/테이블의 크기로 나타내게 된다. 필자가 방금 만든 이 테이블의 현재 적재율은 3/91 = 0.03296...으로 약 3% 정도이므로 높은 적재율은 아니라고 볼 수 있다.

만약 1000과 같이 큰 값이 하나만 더 테이블에 들어온다고 해도 테이블의 크기는 1001이 되고 적재율은 0.003996...으로 약 0.4%가 된다. 즉, 직접 주소 테이블이 큰 힘을 발휘할 수 있는 순간은 1, 2, 3과 같이 연속적인 값을 저장하거나 혹은 값들의 범위 차이가 크지 않은 데이터라고 할 수 있다.

직접 주소 테이블의 단점을 해시 함수로 보완하자!

이렇게 직접 주소 테이블은 값에 접근하기는 편하지만 공간 효율이 좋지 않다는 단점이 있다. 그래서 이 단점을 보완한 게 바로 해시 테이블인 것이다.

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

해시(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

이게 끝이다. 물론 허접한 해시 함수이지만 그래도 해싱이라는 본연의 역할을 잘 수행하는데는 별로 문제가 없다. 필자의 허접한 해시 함수는 무조건 들어온 값을 10으로 나눈 후의 나머지를 반환하는 일을 할 뿐이지만 어떤 값이 들어오든 그 값의 1의 자리만 반환될 것이기 때문에 반환되는 값은 무조건 0~9 사이의 값이라는 것이 보장된다.

그리고 해시 함수의 특성 중 하나가 해싱만 보고는 인자로 어떤 값을 받았는지 추측하기 힘들다는 것이다. 1의 자리만 보고 원래 수가 얼마였는지 맞출 수는 없을 것이다. 이러한 해시 함수의 특징은 암호학에서도 아주 잘 사용하고 있다.

자, 하지만 우리에게 중요한건 암호학이 아니라 바로 이것이다.

어떤 값이 해시 함수로 들어오든 무조건 0~9사이의 값이 반환된다!

직접 주소 테이블의 단점이 바로 10000이라는 값이 하나만 들어오더라도 10000번 인덱스에 값을 저장하기 위해 10000의 크기를 가진 테이블을 생성해야하기 때문에 나머지 9999개의 버리는 공간이 생기는 것이다.

그러나 필자의 해시 함수를 사용하면 100이 들어오면 0을 반환할 것이고 10001이 들어오면 1을 반환, 심지어 8982174981274가 들어와도 4를 반환한다.

즉, 고정된 테이블의 길이를 정해둘 수 있고 그 안에만 데이터를 저장할 수 있게 된 것이다. 해시 함수의 이러한 성질을 이용해서 아주 간단한 해시테이블을 한번 작성해보겠다. 필자는 해시 테이블 크기를 5로 설정하고 어떤 값이 들어와도 이 테이블 안에 저장될 수 있도록 해시 함수를 작성할 것이다.

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

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

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

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

들어온 값들은 1991, 1234, 5678로, 해시 테이블의 사이즈인 5보다 훨씬 큰 값이지만 해시 함수를 거친 결과 0~4 사이의 값만 반환되기 때문에 필자의 작고 귀여운 해시 테이블 안에 값이 차곡차곡 저장될 수 있다.

내 해시 테이블...자그마해 귀여워

해시의 충돌(Collision)

이렇게 해피 엔딩으로 끝나면 좋겠지만 해시 테이블의 단점도 있다. 그 단점은 바로 해시의 충돌이다. 충돌이 뭔지 설명하기 전에 필자의 해시 함수를 가지고와서 한번 충돌을 일으켜보고 직접 확인해보자.

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

다른 값을 해시 함수에 넣었지만 같은 값이 튀어나오는 것이 바로 충돌(Collision)이다.

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

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

충돌 해결하기

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

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

그 중 이 포스팅에서는 충돌이 발생하더라도 우회해서 해결하는 방법 중 몇가지를 설명하려고 한다.

개방 주소법(Open Address)

개방 주소법은 해시 충돌이 발생하면 테이블 내의 새로운 주소를 탐사(Probe)한 후, 비어있는 곳에 충돌된 데이터를 입력하는 방식이다. 해시 함수를 통해서 얻은 인덱스가 아니라 다른 인덱스를 허용한다는 의미로 개방 주소(Open Address)라고 한다.

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

1. 선형 탐사법(Linear Probing)

선형 탐사법(Linear Probing)은 말 그대로 선형으로 순차적으로 탐사하는 방법이다. 위에서 해시 충돌의 예로 들었던 1991과 6의 상황을 한번 예시로 알아보자.

• 0
• 1
  1991
• 2
• 3
• 4
• 5
• 6

처음에 1991을 해시 함수에 통과 시킨 후 해시 테이블에 넣었을 때에는 테이블의 1번 인덱스에 위치했을 것이다. 그 이후 6을 해시 함수에 통과시켰더니 또 1이 나왔다. 하지만 이미 1번 인덱스에는 1991이 들어가 있기 때문에 6은 더 이상 해시 테이블에 들어갈 자리가 없게 되었다. 충돌이 발생한 것이다!

선형 탐사법은 이렇게 충돌이 났을 때 정해진 $n$ 칸만큼의 옆 방을 주는 방법이다. 만약에 $n = 1$이라면 2번 인덱스를, $n = 3$이라면 4번 인덱스에 6을 저장할 것이다.

• 0
• 1
  1991
• 2
  6
• 3
• 4
• 5
• 6

이런 식으로 충돌이 났을 때 순차적으로 정해진 만큼의 옆 방을 주는 것이 바로 선형 탐사법이다. 만약 여기서 또 충돌이 발생한다면 이번에는 그 값을 3번 인덱스에 저장할 것이다. 이런 방식으로 빈 공간이 나타날 때까지 순차적으로 탐사를 한다.

선형 탐사법의 단점은 특정 해시 값의 주변이 모두 채워져있는 일차 군집화(Primary Clustering)문제에 취약하다는 것이다.

• 0
• 1
  1991
• 2
  6
• 3
  13
• 4
  21
• 5
• 6

같은 해시가 여러 번 나오는 경우 선형 탐사법을 사용하면 데이터가 연속되게 저장될 가능성이 높아진다. 즉, 데이터의 밀집도가 높아진다는 것이다. 이런 경우 해시의 값이 1이 나왔을 때 뿐만 아니라 2나 3이 나왔을 때도 충돌이 발생한다.

이게 진짜 악순환의 반복인데, 이런 식으로 충돌이 계속 될 수록 데이터가 연속되게 저장되기 때문에 나중에 가면 데이터가 밀집되어 있는 거대한 덩어리가 생긴다. 그럼 해시로 어떤 값이 나오더라도 그 덩어리가 차지한 인덱스와 충돌이 날 확률이 올라가고, 충돌난 값은 또 그 덩어리 뒤에 저장되게 되므로 데이터 덩어리가 더 커진다.

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

이런 식으로 눈물나는 무한 반복 사이클이 발생한다. 이것이 Primary Clustering이다. 이제 이 눈물나는 문제점을 그나마 보완한 다른 방법을 알아보자.

2. 제곱 탐사법(Quadratic Probing)

제곱 탐사법(Quadratic Probing)은 선형 탐사법과 동일하지만 탐사하는 폭이 고정폭아닌 제곱으로 늘어난다는 것이 다르다.

첫번째 충돌이 발생했을 때는 충돌난 지점으로 부터 $1^2$만큼, 두번째 충돌이 발생했을 때는 $2^2$, 세번째는 $3^2$과 같은 식으로 탐사하는 스텝이 빠르게 커진다. 선형 탐사법때와 동일한 상황에서 제곱 탐사법을 사용하면 해시 테이블은 아래와 같은 모양이 된다.

• 0
• 1
  1991
• 2
  6
• 3
• 4
• 5
  13
• 6
• ...
• 10
  21

첫번째 충돌이 났을 때 6은 충돌이 난 1번 인덱스로 부터 $1^2 = 1$만큼의 옆 방에 들어간다. 두번째 충돌이 났을 때 13은 충돌이 난 1번 인덱스로 부터 $2^2 = 4$만큼의 옆 방에 들어간다. 세번째 충돌이 났을 때 21은 충돌이 난 1번 인덱스로 부터 $3^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];
    }
  }
}

이때 테이블 사이즈와 두번째 해시함수에 사용될 수는 둘 다 소수를 사용하는 것이 좋다. 둘 중에 하나가 소수가 아니라면 결국 언젠가 같은 해싱이 반복되기 때문이다. 딱 보기에 뭔가 좀 복잡해보이지만 하나하나 뜯어보면 별 거 없다. 한번 순서대로 살펴보자.

1. 저장할 인덱스를 getSaveHash 해시 함수로 얻는다.
2. 반복문 시작

3. 거기 비었니?
   3-1. 비었어? 오케이 저장!
   3-2. 사람 있어? 다음 인덱스 내놔! 다시 3으로…
   3-3. 풀방이야? 종료합시다.
   

   ---

위 코드를 브라우저 콘솔이나 NodeJS로 실행시켜보면 출력되는 문자열을 통해 이 과정이 어떤 방식으로 흘러가는 지 대략적으로 알 수 있다.

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

// 13번 인덱스에 1991 저장!
// 6번 인덱스에 6 저장!
// 13번 인덱스에 13 저장하려다 충돌 발생!ㅜㅜ
// 17번 인덱스에 13 저장!
// 21번 인덱스에 21 저장!

아까 선형 탐사법과 제곱 탐사법을 사용했다면 모두 해시의 결과가 1이어서 연쇄적으로 충돌이 발생해야 할 값들이지만 이중 해싱을 사용함으로써 한번의 충돌만으로 모든 값을 저장할 수 있게 되었다. 위에 코드를 복붙해서 함수를 선언해놨다면 저 콘솔을 여러 번 돌려보고 저장할 값도 바꿔보면서 어떤 식으로 해쉬테이블에 값들이 저장되는지 살펴볼 수 있다. 테이블이 꽉 차면 풀방입니다가 출력되니까 그때까진 신나게 돌려봐도 된다.

분리 연결법(Separate Chaining)

분리 연결법은 개방 주소법과는 다른 개념으로 접근하는 충돌 우회 방법이다. 분리 연결법은 해쉬 테이블의 버킷에 하나의 값이 아니라 링크드 리스트(Linked List)나 트리(Tree)를 사용한다. 사실 트리를 쓰던 링크드 리스트를 쓰던 개념은 동일하니 링크드 리스트로 설명을 진행하겠다.

위에서 계속 사용했던 예시를 또 가져와보자. 테이블 크기가 5일때 해시로 1을 반환하는 1991, 6, 13, 21을 저장할 때 분리 연결법을 사용하면 이렇게 된다.

• 0
• 1
  [21, 13, 6, 1991]
• 2
• 3
• 4

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

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

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

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

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

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

문제는 새 노드를 리스트에 붙히기 위해서 메모리 4에 저장된 노드를 찾는 과정이다. 먼저 리스트의 머리인 메모리 1부터 찾은 다음에 다음 메모리 주소 값을 확인하고 2로 이동해서 또 다음 메모리 주소를 확인하고…

이게 지금 4번이니까 할만하지, 리스트의 길이가 길어질수록 수행 시간도 비례해서 늘어나기 때문에 확실히 좋은 느낌은 아니다. 하지만 순서를 반대로 뒤집으면 데이터 삽입이 한결 쉬워진다.

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

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

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

• 0
• 1
  [21, 13, 6, 1991, 7, 11, 25, ...]
• 2
• 3
• 4

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

테이블 크기 재할당(Resizing)

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

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

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

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

이상으로 JavaScript와 함께 해시테이블을 파헤쳐보자 포스팅을 마친다.

• 해시 테이블(Hash Table)이 뭔가요?

  • 직접 주소 테이블(Direct Address Table)
  • 직접 주소 테이블의 단점을 해시 함수로 보완하자!

• 해시의 충돌(Collision)

  • 충돌 해결하기
• 테이블 크기 재할당(Resizing)