[알고리즘 자료구조] JavaScript 해시테이블(HashTable) 구현 및 개념 이해하기

해싱 (Hashing)

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

해시 테이블 (Hash Table)

• key와 value가 쌍을 이룬 형태로 데이터가 저장되어 있는 자료구조형이다.
• 배열에서의 key는 오직 index만 지칭한다면, Hash Table에서는 문자열 또한 key가 될 수 있다.
• 기존 자료구조인 이진탐색트리나 배열에 비해 굉장히 빠른 속도이다.
• 중복확인, 빠른탐색, 삽입, 삭제 속도를 가진다.

속성

• insert(A) : key A를 해쉬테이블에 넣는다.
• search(A) : Key A를 해쉬테이블에서 찾는다.
• remove(A) : Key A를 해쉬테이블에서 삭제한다.

사용 예시

• 전화번호 조회
• 중복된 항목 방지
• 해시 테이블을 캐시로 사용하기
• 어떤 항목과 다른 항목의 관계를 모형화하기 좋음

이슈

해시충돌

key와 value로 이루어져 있는 해쉬테이블은 뛰어난 성능을 발휘하는 자료구조임은 맞지만, 모든 경우에서 사용하지 못하는 이유는 바로 해시충돌(Collision) 때문이다. 해시충돌(Hash Collision)이란 해시 함수를 통해 각각의 다른 key가 동일한 HashCode가 되는 것을 말한다.(중복이 일어남)
해시테이블에서는 충돌에 의한 문제를 분리 연결법(Separate Chaining)과 개방 주소법(Open Addressing) 크게 2가지로 해결하고 있다.

해결 방안

1. 분리 연결법 (Separate Chaining)

분리연결법(Separate Chaining) 이란 동일한 버킷의 데이터에 대하 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터의 주소를 저장하는 방법이다. 위의 그림과 같이 key가 동일한 버킷으로 중복으로 접근을 한다면 데이터들을 연결하여 관리하여 주는 것이다. 링크드리스트 데이터 구조를 활용한다.

이러한 분리연결법(Separate Chaining) 방식은 해시테이블의 확장이 필요없고 간단하게 구현이 가능하며, 손쉽게 삭제할 수 있다는 장점이 있지만, 데이터의 수가 많아지면 동일한 버킷에 chaining되는 데이터가 많아지게 되어 캐시의 효율성이 감소한다는 단점이 존재한다.

1-1.장점

• 제한된 buket을 효율적으로 사용할 수 있다.
• 공간을 미리 할당할 필요가 없어 메모리 사용량을 줄여준다.
• 연결리스트를 사용하면 추가할 수 있는 데이터의 제약이 줄어든다.

1-2. 단점

• 다양한 key에 동일한 hash가 있고, 하나의 buket에 여러 항목이 있는 경우 검색 효율성이 저하된다.
• 연결리스트를 사용하려면 추가 메모리가 필요하다.
• 최악의 경우 모든 노드가 동일한 버킷에 삽입될 수 있다.

1-3. 시간복잡도

1-3-1. 최악의경우

• O(n)
• 모든 key가 하나의 buket으로 해싱되는 경우 길이가 n인 연결리스트가 생성될 수 있다.

1-3-2. 평균수행시간

• O(1+α) (α = 적재율(Load factor))
• 테이블 slot에 접근하기 위해 O(1)의 시간이 걸리고 해당 슬롯에 있는 리스트를 검색하기 위해 O(α)의 시간이 걸린다.

2. 개방 주소법 (Open Addressing)

개방주소법 (Open Addressing)이란 추가적인 메모리를 사용하는 Chaining방식과 다르게 연결리스트와 같은 추가적인 메모리 공간을 사용하지 않고, 비어있는 해시테이블의 공간을 활용하는 방법이다. 따라서 분리연결법 보다 메모리가 덜 차지하게 된다.
해시테이블은 해시 1개와 값 1개가 일치하는 형식으로 유지되며, 버킷에서 충돌(중복)이 발생하면 indexs 해시가 변경되어 다른 버킷에 저장된다.

개방주소법 (Open Addressing)을 구현하기 위한 대표적인 방법으로는 3가지 방식이 존재한다.

2-1. Linear Probing 선형탐색

현재의 버킷 index로부터 주어진 고정폭 만큼 이동하여 차례대로 검색해 비어있는 버킷에 데이터를 저장한다.

2-1-1. 장점

• 구현이 쉽다.

2-1-2. 단점

• Primary clustering 문제
• 연속된 데이터 그룹이 생기는 현상을 클러스터링 (Clustering) 이라고 합니다. 클러스터링은 탐색 시간을 오래 걸리게 하여 해싱 효율을 떨어트리는 현상을 야기할 수 있습니다.
• 탐색 간격을 1 이외에 다른 값으로 정할 수 있는데 테이블의 크기 값과 서로소 관계에 있는 소수로 정해야 클러스터링 현상을 줄일 수 있다.

2-2. Quadratic Probing

해시의 저장순서 폭을 제곱으로 저장하는 방식이다. 예를들어 처음 충돌이 발생한 경우에는 1만큼 이동하고 그 다음 계속 충돌이 발생하면 2^2, 3^2칸씩 옮기는 방식이다.

2-2-1. 장점

• 선형탐색보다 클러스터링이 적게 일어난다.

2-2-2. 단점

• Secondary clustering 문제가 있다.
• 만약 두개의 key의 처음 probe값이 동일하다면 빈 slot을 찾는 과정이 동일하므로 계속해서 같은 slot을 탐색하게 된다.
• 즉 처음 충돌한 위치가 같다면 다음 충돌할 위치에서도 반복적으로 계속 충돌이 나게 된다.

2-3. Double Probing

해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식이다. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하기 때문에 다른 방법들보다 많은 연산을 하게 된다.

2-3-1. 장점

• 선형탐색보다 클러스터링이 적게 일어난다.

2-3-2. 단점

• Open Addressing에서 데이터를 삭제하면 삭제된 공간은 Dummy Space로 활용되는데, 그렇기 때문에 Hash Table을 재정리 해주는 작업이 필요하다고 한다.

2-3-3. 시간복잡도

open addressing의 적재율(Load factor)은 배열의 크기가 한정되어 있기 때문에 1 이하이다.

open addressing에서 계산 복잡성은 탐사(probing) 횟수에 비례한다. 따라서 search 횟수로 시간 복잡도를 나타낼 수 있다.
적재율을 α라고 했을 때 선형 탐색(Linear probing)에서 시간 복잡도는 다음과 같다.

• successful search : 1/2∗1+1/(1−α)
• unsuccessful search : 1/2∗1+1/(1−α)2

선형 탐색에서 적재율이 0.5 이상이 되면 unsuceessful search 횟수는 급격히 늘어나게 된다.
따라서 적재율이 0.5 이상이 되면 해시 테이블의 크기를 늘리는 등의 작업으로 적재율을 0.5 미만이 되도록 해야 한다.
제곱 탐색, 이중 해시도 적재율을 0.5 미만으로 유지하는게 좋다.

---

자바스크립트로 해시테이블 구현 (Hash Table In JavaScript)

아직 많이 어렵고 이해도 덜 되는것 같지만 구글링으로 가장 이해가 쉬운 내용을 발췌하여 가져와 보았습니다.

//  string 자료형의 key에 해당하는 공간에 string 자료형의 value를 집어넣은 것
const person = {};
person["firstName"] = "Kelly";
person["lastName"] = "Park";

// 1. Hash Table 생성

class HashTable {
  table = new Array(3);
  // 해시 테이블 사이즈에 바로 접근 할 수 있도록 변수 생성, setItem 할 때마다
  // numItem++되어 table에 들어있는 개수를 그때 그때 반영
  //  이 값을 활용하여, table의 길이 대비 현재 들어있는 값의 개수를 연산해 
  // 특정 수준 이상으로 값이 할당이 되면 table의 길이를 늘림
  numItems = 0;

  setItem = (key, value) => {
    this.numItems++;

    // table 원소 개수가 80%이상 차있는 경우 resize()
    const loadFactor = this.numItems / this.table.length;
    if (loadFactor >= 0.8) {
      this.resize();
    }

    const idx = hashStringToInt(key, this.table.length);
    if (this.table[idx]) {
      this.table[idx].push([key, value]);
    } else {
      this.table[idx] = [[key, value]];
    }
  };

  // 만약 배열의 크기를 3에서 6으로 두 배를 했다면, 그보다 큰 소수인 7을 새로운 table의 크기로 설정해주는 것이다.
  resize = () => {
    const newTable = new Array(this.table.length * 2);
    this.table.forEach((item) => {
      if (item) {
        item.forEach(([key, value]) => {
          const idx = hashStringToInt(key, newTable.length);
          if (newTable[idx]) {
            newTable[idx].push([key, value]);
          } else {
            newTable[idx] = [[key, value]];
          }
        });
      }
    });
    this.table = newTable;
  };

  // getItem에서도 값을 가져오기 원하는 key를 해시 함수로 변환해서 table[3]의 값을 리턴하도록 한다.
  getItem = (key) => {
    const idx = hashStringToInt(key, this.table.length);
    // 값이 없는 경우 null;
    if (!this.table[idx]) return null;

    // 단순히 전체 table의 index로 접근 = O(1) but array.find를 사용하면 O(n)으로 증가함
    return this.table[idx].find((el) => el[0] === key)[1];
  };
}

// 2.  해시 함수(Hash Function)가 필요한 이유

function hashStringToInt(s, tableSize) {
  let hash = 17;
  // return 3; 항상 table[3] index 중복 해시 충돌 발생
  for (let i = 0; i < s.length; i++) {
    hash = (13 * hash * s.charCodeAt(i)) % tableSize;
  }
  return hash;
}

Reference

https://courses.csail.mit.edu/6.006/spring11/rec/rec05.pdf
https://eunjinii.tistory.com/88
https://soldonii.tistory.com/72
https://hyosup0513.github.io/data%20structure/2020/06/22/What-is-Hash-and-Hash-Table.html
https://mangkyu.tistory.com/102
https://yoongrammer.tistory.com/82#%EA%B0%9C%EB%B0%A9_%EC%A3%BC%EC%86%8C%EB%B2%95_(Open_Addressing)
출처: https://algoroot.tistory.com/56 [Algoroot's space:티스토리]