HashTable

해시 테이블?

 - 해시 테이블이란 어떤 특정 값을 입력 받으면 그 값을 해시 함수에 통과 시켜 나온 값을 인덱스 ( Index )에 저장하는 

   자료 구조이다.

   

1. 직접 주소 테이블 ( 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 HashTable = new DirectAddressTable();

HashTable.setValue(3);
HashTable.setValue(10);
HashTable.setValue(90);

console.log(HashTable.getTable());
// [ <3 empty items>, 3, <6 empty items>, 10, <79 empty items>, 90 ]

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

   이렇게 직접 주소 테이블을 사용할 때는 들어오는 값이 뭔지 알면 이 값이 지정된 인덱스도 함께 알 수 있기에

   저장된 데이터에 바로 접근해서 값을 가져 올 수 있다.

console.log(HashTable.getValue(3)); // 3

 

 - 찾고자 하는 값과 테이블의 인덱스가 동일하므로 테이블을 뒤적거릴 필요 없이 값이 저장된 공간에 바로 접근하여

   값을 가져올 수 있으므로 시간 복잡도는 O(1)이다. 

   값의 수정, 삭제, 삽입하는 행위도 마찬가지로 값이 어디 있는지 알고 있으면 한방에 해결할 수 있으므로 O ( 1 )의 시간

   복잡도를 갖는다.

 

 - 하지만 직접 주소 테이블의 단점은 공간의 효율성이 좋지 못하는 점이다. 위의 HashTable에 3, 10, 90의 값을 넣었고

   이 테이블은 아래와 같은 구조를 가지게 된다.

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]

console.log(HashTable.getValue(4)); // undefined

 - 저장된 값을 제외하고는 undefined가 나오게 된다. 값이 없지만 메모리 공간은 할당 되어 있는 상태인 것이다.

   즉, 사용하지 않는 아까운 공간으로 공간적인 효율이 떨어지게 된다.

 

 - 이런 상황을 적재율이 낮다라고 표현하는 데, 적재율은 값의 개수 / 테이블의 크기로써 위 테이블은 3 / 91 = 0.3296..

   으로 3%의 낮은 적재율을 갖게 된다.

 

 - 만약 1000과 같은 테이블이 들어온다고 하면 테이블의 크기는 1001이 되고 적재율은 0.4%로 현저하게 떨어지게 된다.

  => 직접 주소 테이블이 큰 힘을 발휘할 수 있는 공간은 1, 2, 3과 같은 연속적인 값을 저장하거나 값들의 범위 차이가

        크지 않은 데이터라고 할 수 있다.

 

2. 해시 테이블

 - 직접 주소 테이블은 값에 접근하기 편하지만 공간 효율이 좋지 못하다.

   이 단점을 보완하기 위한 것이 해시 테이블이다!

 

 - 해시 테이블은 직접 주소 테이블처럼 값을 바로 테이블의 인덱스로 사용하는 것이 아니라 해시 함수 ( Hash Function )에

   한 번 통과시켜 사용한다.

※ 해시 함수는 임의의 길이를 가지는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.

   => 이 함수가 리턴하는 결과물을 해시 ( Hash ) 라고 부른다. Hash : 잘게 썬 요리

 

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

console.log(hashFunction(102943)); // 3
console.log(hashFunction(12)); // 2
console.log(hashFunction(424687)); // 7
console.log(hashFunction(3597)); // 7

 - 단순한 해시 함수이지만 해싱이라는 본연의 역할을 잘 수행한다.

   위의 해시 함수는 무조건 들어온 값을 10으로 나눈 후의 나머지를 반환할 뿐이다. 이를 통해 그 값의 1자리의 값만 

   반환할 것이기에 반환값은 0 ~ 9 사이의 값이다.

 

 - 해시 함수의 특징 중 하나는 해싱만 보고는 인자로 어떤 값을 받았는지 추측하기 힘들다는 것이다.

   => 1의 자리만 보고서는 원래 수가 얼마 였는 지 맞추긴 힘들 것이다.

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

 - 직접 주소 테이블의 단점은 10000이라는 값이 하나만 들어와도 10000번 인덱스에 값을 저장하기 위해 10000 크기를

   가진 테이블을 생성해야 하기에 나머지 9999개의 버리는 공간이 생기지만

 - 해시 함수를 사용하면 100은 0을 10001은 1을 반환 0~ 9사이의 값을 가지게 된다.

  => 고정된 테이블의 길이를 정해둘 수 있고 그 안에만 데이터를 저장할 수 있게 된다.

const Tablesize = 5;

const Table = new Array(Tablesize);

function hashFunction2(key) {
  return key % Tablesize;
}

Table[hashFunction2(19398)] = 19398;
Table[hashFunction2(1234)] = 1234;
Table[hashFunction2(767)] = 767;

console.log(Table);
// [ <2 empty items>, 767, 19398, 1234 ]

 - 고정된 테이블 길이를 가지며 그 안에만 데이터를 저장할 수 있는 해시 함수의 예!

   각 입력된 값들은 5보다 큰 값들이지만 해쉬 함수를 거치게 되면 0 ~ 4 사이의 값만 반환 되이게  정해진 테이블 안에

   값을 입력할 수 있게 된다.

 

3. 해시의 충돌 ( Collision )

 - 해시 테이블의 단점은 해시의 충돌이다.

console.log(hashFunction2(6));  // 1
console.log(hashFunction2(1991)); // 1

다른 값을 해시 함수에 넣었지만 같은 값을 리턴하게 되는 것이 충돌 ( Collision )이다.

 - 이처럼 해시 테이블에는 해시 충돌이라는 단점이 있기 때문에 해시 테이블을 운용할 때 가장 중요한 점은

   해시 함수가 얼마나 균일하게 값을 퍼트릴 수 있느냐 하는 것이다.

   => 어떤 값을 넣어도 같은 인덱스가 나올 확률이 높은 해시 함수는 좋은 함수가 아닌 것이다.

 - 하지만 해시 함수를 아무리 잘 짜더라도 근본적으로 충돌을 완전히 방지한다는 것은 아주 힘들다.

   어느 정도 충돌을 최소화 하기 위해 해시 함수의 알고리즘을 개발하거나 충돌이 발생하더라도 우회해서 해결할 수 있는

   방법을 사용한다.

 

● 해시를 우회해서 해결하는 방법

 

1. 개방 주소법

 - 개방 주소법은 해시 충돌이 발생하면 테이블 내의 새로운 주소를 탐사 ( Probe ) 한 후 비어있는 곳에 충돌된 데이터를

   입력하는 방식이다. 해시 함수를 통해 얻은 인덱스가 아니라 다른 인덱스를 허용한다는 의미로 개방 주소

   ( Open Address) 라고 한다.

 

1 - 1. 선형 탐사법 ( Linear Probing )

 - 선형 탐사법은 말 그대로 선형으로 순차적으로 탐사하는 방법이다. 위의 예시대로 1991과 6의 상황을 보면

 - 첫 1991을 해시함수에 통과 시키면 1번 인덱스에 위치하고 6을 통과시키면 다시 인덱스가 1이 나오기에 

   해시 테이블 내에 들어갈 수 없게 되었다.

   선형 탐사법은 이렇게 충돌이 나게 되면 n 칸만큼 옆방을 주는 방법이다.

// n = 1이라면 2번 인덱스를 n = 3 이라면 4번 인덱스에 6을 저장하는 것이다.

 - 이런 식으로 충돌이 났을 때 순차적으로 정해진 만큼 옆 방을 주는 것이 선형 탐사법이다.

   만약 여기서 또 충돌이 일어나면( n = 1 일때 ) 그 값을 3번 인덱스에 저장할 것이며, 이런 방식으로 빈 공간을 만날

   때까지 순차적 탐사를 한다.

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

   것이다.

 - 같은 해시가 여러번 나올 때 선형 탐사법을 사용하면 데이터가 연속적으로 저장될 가능성이 높아진다.

   => 데이터의 밀집도가 높아지게 된다. 이 후 해시의 값이 1이 나왔을 때 뿐아니라 2 나 3 이 나왔을 때도 충돌이 발생!

 

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

 

1 - 2 제곱 탐사법 ( Quadratic Probing )

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

 - 첫 충돌은 충돌 지점부터 1^2 만큼, 두 번째 충돌은 2^2, 세번째는 3^3....

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

 - 제곱 탐사법을 이용하면 데이터의 밀집도가 선형 탐사법보다는 낮기에 연쇄적 충돌 가능성이 줄어든다.

 - 결국 해시로 1이 여러번 나오면 충돌을 피할 수가 없다. 이런 형상을 이차 군집화 ( Secondary Clustring )이라고 한다.

 

1- 3 이중 해싱 ( Double Hashing )

 - 위의 문제점들을 해결하기 위해 나온 방법이 이중 해싱이다.

 

 - 해시 함수를 이중으로 사용하는 것인데 하나는 기존과 마찬가지로 최초 해시를 얻을 때 사용 하고

   다른 하나는 충돌이 났을 경우 탐사 이동폭을 얻기 위해 사용한다.

  => 이를 통해 최초 해시로 같은 값이 나오더라도 다시 다른 해시 함수를 거치며 다른 탐사 이동폭이 나올 확률이 높기 

        때문에 매번 다른 공간에 값이 골고루 저장될 확률도 높아지게 된다!

 

const TableSize = 23; // 테이블 사이즈가 소수여야 효과가 좋다

const HashTable = [];

const getSaveHash = (value) => value % TableSize;

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

const setValue = (value) => {
  let index = getSaveHash(value);
  let targetValue = HashTable[index];

  while (true) {
    if (!targetValue) {
      HashTable[index] = value;
      console.log(`${index}번 인덱스에 ${value} 저장`);
      return;
    } else if (HashTable.length >= TableSize) {
      console.log("테이블 크기를 넘어섭니다.");
      return;
    } else {
      console.log(`${index}번 인덱스에 ${value} 저장 실패 충돌 발생`);
      index += getStepHash(value);
      index = index > TableSize ? index - TableSize : index;
      targetValue = HashTable[index];
    }
  }
};

setValue(1991);
setValue(6);
setValue(13);
setValue(21);
console.log(HashTable);
// [<6 empty items>, 6, <6 empty items>, 1991, <3 empty items>, 13, <3 empty items>, 21]

 - 이 때 테이블 사이즈와 두 번째 해시 함수의 수는 소수를 사용하는 것이 좋다.

   둘 중 하나가 소수가 아니면 결국 언젠가 같은 해싱이 반복되기 때문이다.

 

이중 해싱의 순서

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

3. 거기 비었니? => 비었다 저장 => 안비었어? 다음 인덱스 => 꽉찼다? 종료

 - 선형 탐사법과 제곱 탐사법을 이용하면 모든 해시의 결과가 1이기에 연쇄적 충돌이 발생하지만

   이중 해싱을 사용함으로써 한 번의 충돌만으로 값을 저장할 수 있게 되었다.!!

 

---

 

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