[알고리즘, 자료구조] 자바스크립트로 해시테이블(Hash Table) 구현하기 (+개념이해)

 

지난 스택(Stack)편에 큐(Queue)편에 이어 해시테이블 (Hash Table)의 개념을 알고, 자바스크립트로 구현해보고자 한다. 

 

 

스택(Stack) 편 link

[알고리즘, 자료구조] 자바스크립트로 스택(Stack)구현하기

 

큐(Queue) 편 link

[알고리즘, 자료구조] 자바스크립트로 큐(Queue)구현하기 (+개념이해)

 

 

---

해싱(Hashing)

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

Hash-generator

위 사이트를 통해서 직접 해시를 생성해볼 수도 있다. 

 

해시 테이블 (Hash Table)

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

https://yourbasic.org/algorithms/hash-tables-explained/

속성

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

 

해시 테이블 (Hash Table) 사용 사례

중복 확인, 빠른 탐색,삽입,삭제 속도를 가진다. 

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

 

---

해시 충돌 (Hash Collision)

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

 

 

---

 

- 분리 연결법 (Separate Chaining)

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

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

 

장점 

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

 

단점

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

 

시간 복잡도 (Time complexity)

• 최악의 경우
  
  • O(n)
  • 모든 key가 하나의 slot으로 해싱되는 경우 길이가 n인 연결 리스트가 생성될 수 있다.
• 평균 수행 시간
  • O(1+α) (α = 적재율(Load factor))
  • 테이블 slot에 접근하기 위해 O(1)의 시간이 걸리고 해당 슬롯에 있는 리스트를 검색하기 위해 O(α)의 시간이 걸린다.

 

---

 

- 개방 주소법 (Open Addressing)

 

Open Addressing이란 추가적인 메모리를 사용하는 Chaining 방식과 다르게 연결리스트와 같은 추가적인 메모리 공간을 사용하지 않고,비어있는 해시 테이블의 공간을 활용하는 방법이다. 따라서 분리연결법 보다 메모리가 덜 차지하게 된다. 

해시 테이블은 해시 1개와 값 1개가 일치하는 형식으로 유지된다. 버킷에서 충돌이 발생하면 index(해시가 변경되어 다른 버킷에 저장된다.

 

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

 

1. Linear Probing

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

 

장점

• 구현이 쉽다.

 

단점

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

 

 

2. Quadratic Probing

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

장점

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

단점

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

 

 

3. Double Probing

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

장점

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

단점

• Secondary clustering 문제가 있음.
• 만약 두 key의 처음 probe 값이 동일하다면 빈 slot을 찾는 과정이 동일하므로 같은 slot을 탐색한다.

 

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

 

시간 복잡도 (Time complexity)

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 미만으로 유지하는게 좋다.

 

 

---

Resizing

 

 

 

---

 

자바스크립트로  해시테이블(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;
}

 

resize 함수로 배열이크기가 80%가 차면 새로운 배열을 만들어주어  table.length가 두배로 변한 것을 볼 수 있다.

// 생성자 함수 생성 new HashTable();
const myTable = new HashTable();
myTable.setItem("firstName", "Kelly");
console.log(myTable.table.length); // 3
console.log(myTable.getItem("firstName")); // Kelly

myTable.setItem("lastName", "Park");
console.log(myTable.table.length); // 3
console.log(myTable.getItem("lastName"));

myTable.setItem("age", 29);
console.log(myTable.table.length); // 6
console.log(myTable.getItem("age"));

myTable.setItem("birth", "2000-00-00");
console.log(myTable.table.length); // 6
console.log(myTable.getItem("birth"));

 

 

 

 

---

빼놓을 수 없는 스택(Stack) 자료구조 이해 & 구현하기!

https://algoroot.tistory.com/54

[알고리즘, 자료구조] 자바스크립트로 스택(Stack)구현하기

 

 

빼놓을 수 없는 큐(Queue) 자료구조 이해 & 구현하기!

https://algoroot.tistory.com/55

[알고리즘, 자료구조] 자바스크립트로 큐(Queue)구현하기 (+개념이해)

 

 

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)