[JS] 자바스크립트 hash Table

---

해시 테이블(Hash Table)

https://velog.io/@yunsungyang-omc/data-structure-Hash-Table

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

C++이나 자바 파이썬의 map, hashMap, dictionary와 같이 Hash처리하기 위해 마땅히 좋은 방법이 없다. 하지만 해쉬 매핑이 불가능한 것은 아니며, 몇 가지 방식으로 구현이 가능하다.

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

해시테이블의 아이디어는 직접주소 테이블이라는 자료구조에서 부터 출발한다. 직접주소 테이블은 입력받은 value가 곧 key가 되는 데이터 매핑 방식이다.

class DirecAddressTable {
  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());

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

3을 테이블에 넣으면 이 값은 배열의 3번 인덱스의 요소가 되고,
90을 넣으면 90번 인덱스의 요소가 된다.

직접 주소 테이블을 사용할때는 들어오는 값이 뭔지 알면 이 값이 저장된 인덱스도 함께 할 수 있기 때문에 저장된 데이터에 바로 접근해서 값을 가져올 수 있다.

myTable.getValue(3); // 3

찾고자 하는 값과 테이블의 인덱스가 동일하므로 테이블을 뒤적거릴 필요없이 값이 저장된 공간에 바로 접근해서 값을 가져올 수 있으므로 시간복잡도는 O(1)이다.

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

하지만 저장된 데이터를 제외하고는 채워진 공간을 제외한 나머지 공간은 값은 없지만 메모리 공간은 할당되어 있는 상태인 것이다. 이렇듯 직접주소 테이블은 공간의 효율성이 좋지 못하다는 단점이 있다.

적재율

위처럼 테이블에 데이터의 값의 범위보다 값의 개수가 작고 그로 인해 공간적인 효율성이 떨어지고 있다면, 적재율이 낮다라고 표현한다. 적재율은 값의 개수 / 테이블의 크기로 나타내게 된다.

---

직접 주소 테이블의 단점 극복하기

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

위 해시함수는 어떤 값이 해시함수로 들어오든 무조건 0~9사이의 값이 반환되고 있다.
즉, 고정된 테이블의 길이를 정해둘 수 있고 그 안에만 데이터를 저장할 수 있게 된 것이다.

//해시 테이블의 크기를 5로 설정 
const myTableSize = 5;
const myHashTable = newArray(myTableSize);

function hashFunction (key) {
  // 들어온 값을 테이블의 크기로 나눠주고 나머지를 반환한다. 
  return key % myTalbeSize;
}
myHashTable[hashFunction(1991)] = 1991;
myHashTable[hashFunction(1234)] = 1234;
myHashTable[hashFunction(5678)] = 5678;

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

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

---

해시 충돌(hash collision)

다른 값을 해시 함수에 넣었지만 같은 값이 튀어나오는 것이 바로 충돌(Collision)이다.
사실 상식적으로 생각해보면 직접 주소 테이블은 동적으로 테이블을 늘려나갔지만, 해시 테이블은 처음부터 고정적인 공간을 할당하고 값을 계속 우겨넣는 방식이다.
해시 테이블에는 해시의 충돌이라는 단점이 있기 때문에 해시 테이블을 운용할 때 가장 중요한 것은 사실 해시 함수가 얼마나 균일하게 값을 퍼트릴 수 있느냐이다.

해시 충돌을 우회해서 해결하는 방법 몇가지를 알아보자.

개방 주소법(Open Address)

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

개방 주소법은 다음 4자기로 나뉜다.

1.선형 탐사법

선형 탐사법(Linear Probing)은 말 그대로 선형으로 순차적으로 탐사하는 방법이다.
충돌이 났을때 정해진 n칸만큼의 옆 방을 홀드해서 데이터를 저장하는 방법이다.
선형 탐사법의 단점은 특정 해시 값의 주변이 모두 채워져있는 일차 군집화문제에 취약하다는 점이다.

같은 해시가 여러 번 나오는 경우 선형 탐사법을 사용하면 데이터가 연속되게 저장될 가능성이 높아진다. 즉, 데이터의 밀집도가 높아진다는 것이다. 악순환의 반복으로 데이터가 연속되게 저장되기 때문에 어느정도 후에 데이터가 밀집된 거대한 덩어리를 볼 수 있다.

충돌! → 데이터 덩어리 뒤에 충돌난 값 저장 → 충돌확률 증가! → 덩어리 뒤에 또 저장 → 충돌확률 증가!

이런식으로 악순환이 반복되는 것을 Primary Clustering이다.

2.제곱 탐사법(Quardratic Probing)

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

첫번째 충돌이 발생했을 때는 충돌난 지점으로부터 1의 제곱만큼, 두번째 충돌이 발생했을때는 2의 제곱만큼, 세번째는 3의 제곱만큼 탐사하는 스탭의 범위가 점점 커진다.

첫번째 충돌이 났을 때 6은 충돌이 난 1번 인덱스로 부터 1^2 = 11
2
=1만큼의 옆 방에 들어간다. 두번째 충돌이 났을 때 13은 충돌이 난 1번 인덱스로 부터 2^2 = 42
2
=4만큼의 옆 방에 들어간다. 세번째 충돌이 났을 때 21은 충돌이 난 1번 인덱스로 부터 3^3 = 93
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. 저장소가 가득차있으면 종료한다.
 

4. 분리 연결법(Seperate Chaining)

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

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

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

테이블 크기 재할당(Resizing)

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

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

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

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

---

출처

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