자료구조 해시테이블

자료구조 해시테이블 (hash table)

해시테이블

해시테이블은(해시 맵) 키를 값에 매핑할 수 있는 구조인 연관 배열을 구현하는 자료구조이다.
(객체와 같은 키, 값 구조)

해시테이블에 30개의 칸이 존재하는 경우,
데이터가 31개라면 어떻게 될까?

마지막 데이터는 연결 리스트의 형태로 저장된다.
즉, 29개의 칸에는 1개의 데이터가 저장되고, 1개의 칸에는 2개의 데이터가 저장될 수 있는 것이다.

그렇다면 그 1개의 칸은 어떻게 정하게 될것인가?

이때 해시(hash)라는 개념이 등장한다.

-> 해시테이블은 이러한 해시들을 활용한 테이블이다.

해시테이블은 해시함수를 사용해 원하는 값을 담을 수 있는 버킷 또는 슬롯 배열의 인덱스를 계산한다.

넣을 데이터를 어떤 알고리즘을 통해 1~30 까지의 숫자로 변경하는 것이 바로 해시이다.
최대한 데이터가 고르게 나오는 알고리즘이어야 한 칸에 31개의 데이터가 저장되고 나머지 29칸은
비어있는 것과 같은 불상사를 막을 수 있다.

이상적으로, 해시 함수는 각 키들을 고유 버킷에 할당하지만 대부분의 해시 테이블은 불완전한 해시 함수를 사용하기
때문에 해시 함수를 통해 두 개 이상의 키에 대해 동일한 인덱스를 생성하는 해시 충돌이 발생할 수 있다.

function stringToInteger(str, mod) {
  return str.split('').reduce((a, c) => a + c.charCodeAt(), 0) % mod
}

stringToInteger('dog', 30); // 14

위 해시 함수는 각 단어의 charCode를 찾아 모두 더한 후 30으로 나눈 나머지를 구하는 함수이다.
d의 코드는 100, o의 코드는 111, g의 코드는 103이니 다 더하면 314, 30으로 나눈 나머지는 14가 된다.

이 경우 coh라는 단어를 위 해시함수를 거치면 14가 나온다.

이러한 해시 충돌은 어떤 방법으로든 해결되어야 하며,
해시 충돌이 최소한으로 일어나는 알고리즘이 좋은 알고리즘이다.

자바스크립트로 구현하기

class Node {
  next = null;
  constructor(key, data) {
    this.key = key;
    this.data = data;
  }
}
class Hashtable {
  arr = [];
  constructor(mod) {
    this.mod = mod;
  }
  
  get(key) {
    const index = stringToInteger(key, this.mod);
    let target = this.arr[index];
    let found = null;
    while (target) {
      if (target.key === key) {
        found = target.data;
        break;
      }
      target = target.next;
    }
    return found;
  }
  set(key, data) {
    const index = stringToInteger(key, this.mod);
    if (this.arr[index]) {
      let target = this.arr[index];
      while (target.next) {
        target = target.next;
      }
      target.next = new Node(key, data);
    } else {
      this.arr[index] = new Node(key, data);
    }
    return index;
  }

  remove(key) {
    const index = stringToInteger(key, this.mod);
    let prev = null;
    let target = this.arr[index];
    let found = null;
    while (target) {
      if (target.key === key) {
        found = target.data;
        if (prev) {
          prev.next = target.next;
        } else {
          this.arr[index] = null;
        }
        target.next = null;
        break;
      }
      prev = target;
      target = target.next;
    }
    return found;
  }
}

해시테이블의 시간 복잡도

삽입, 조회, 제거 : O(n)
! 해시충돌이 발생해 최악의 경우에는 O(n)이 된다.