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

강좌30 - Algorithm - 일 년 전 등록

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

이번 시간에는 해시테이블에 대해 한 번 알아보도록 하겠습니다. 해시테이블은 객체같은 키-값 구조라고 보면 됩니다.

자바스크립트에서는 굳이 해시테이블을 쓸 필요가 없습니다. 이미 객체나 배열이라는 훌륭한 자료구조가 있기 때문이죠. 속성을 원없이 넣을 수 있습니다. 하지만 자료구조를 배울 때는 항상 데이터의 양(또는 길이)을 사전에 정의해야한다는 것을 기억해야 합니다. 배열이나 객체 모두 넣을 수 있는 양이 처음부터 정해져 있는 것이죠. C같은 언어를 할 때는 처음에 자료구조를 만들 때부터 데이터 길이를 명시해줘야하는 경우가 있어서 그렇습니다.

예를 들어 해시테이블에 30개의 칸만 존재한다고 해봅시다. 그런데 데이터는 31개면 어떻게 될까요? 마지막 데이터는 연결 리스트의 형태로 저장됩니다. 즉, 29개의 칸에는 1개의 데이터가 저장되고, 1개의 칸에는 2개의 데이터가 저장될 수 있는 것이죠. 그렇다면 그 1개의 칸은 어떻게 정하게 될까요? 이 때 해시(hash)라는 개념이 나옵니다. 해시테이블을 해시들을 활용한 테이블이라서 해시테이블인 것입니다.

넣을 데이터를 어떤 알고리즘을 통해 1~30까지의 숫자로 변경하는 것이 해시입니다. 최대한 데이터가 고르게 나오는 알고리즘이어야 한 칸에 31개의 데이터가 저장되고 나머지 29칸은 텅텅 비어있는 것과 같은 불상사를 막을 수 있습니다. 예를 들어 dog는 14으로, cat은 12로 horse는 5로 변경되게 만드는 알고리즘이면 됩니다. 이 때, dog는 알고리즘을 수행할 때마다 매 번 같은 14으로 변경되어야 합니다. 그래야 데이터를 항상 해시테이블에서 찾을 수 있습니다. 해시테이블의 구조가 키-값이라고 했는데 정확히는 키->해시-값 구조입니다. 키를 해시로 바꿔서 저장하거든요.

해시 함수를 만들어보겠습니다.

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라는 단어도 stringToInteger를 거치면 14가 나옵니다. dog와 결괏값이 같은데 이렇게 해시가 겹치는 현상을 해시 충돌(hash collision)이라고 부릅니다. 해시 충돌이 최소한으로 일어나는 알고리즘이 좋은 알고리즘입니다.

이제 해시테이블을 구현해봅시다. 연결 리스트 의 코드를 기억해야 합니다.

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;
  }
}

const hashtable = new Hashtable(30);
hashtable.set('dog', 'bowwow');
hashtable.set('cat', 'meow');
hashtable.set('coh', 'bowwow2');
hashtable.set('boi', 'bowwow3');
hashtable.get('coh'); // bowwow2
hashtable.remove('coh'); // bowwow2
hashtable.get('coh'); // null
hashtable.get('boi'); // bowwow3

hashtable을 조회해보면 12, 14 인덱스에 데이터가 들어있는 것을 확인할 수 있습니다. dog, coh, boi는 index가 모두 14라서 연결리스트로 구성되어 있습니다.

해시 테이블의 시간 복잡도는 삽입, 조회, 제거 모두 O(1)입니다. 정말 대단한 자료구조이죠! 하지만 해시 충돌이 발생하는 경우에는 최악의 경우 O(n)이 됩니다. 한 칸에 모든 데이터가 몰려있는데 찾고자 하는 데이터가 연결리스트의 마지막에 위치한 경우를 생각해보면 됩니다. 그래서 해시테이블에서는 충돌이 발생하지 않게 만드는 것이 매우 중요합니다.

공간 복잡도는 O(n)입니다.

조회수:

ZeroCho Blog

게시글

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

댓글