해시 테이블(Hash Table)이란?

해시 맵(Hash Map)이라고도 한다.
맵이라는 자료구조, 즉 딕셔너리에(딕셔너리 문서 참고) 해싱(해시처리)를 추가한 자료구조이다.
딕셔너리라는 자료구조에, 해시함수라는 논리구조를 조합한 것이다.

말이 어려우니 차근차근 풀어보자.

해싱(hasing)은 입력 값을 처리하여 새로운 값을 만드는 작업이다.

해시 브라운(hash browns)이라는 음식을 떠올려보자.
이것은 감자를 다지고 으깨고 섞고 튀긴 음식이다.

마찬가지로 해싱이란 입력값(감자)에 대해 특별한 연산(해싱알고리즘, 다지고 으깨고 섞고 튀기기)을 적용하여 새로운 값(해시 브라운)을 만드는 작업이다.

이런 처리를 하는 함수를 해시함수라고 한다.

해시함수가 반환하는 해시값을 index로 사용한다.

해시함수는 입력으로 KEY를 받아 해싱처리를 거쳐 만들어진 해시값을 출력으로 반환하는 함수이다.
반환되는 해시값는 해시테이블의 index로 사용된다.

따라서 해시 테이블이라는 자료구조는 인터페이스는 [KEY, VALUE]로 관리되는 딕셔너리의 모습이지만, 내부적으로 구현되는 방식은 배열에 해시함수가 결합된 구조라고 볼 수 있다.

해시함수는 특정 조건들을 갖추어야한다.

아래 조건들을 갖추었을때 해시함수로 사용 할 수있다.

• 일관성이 있어야 한다

  • 같은 값을 넣으면 항상 같은 값이 나와야 한다.

• 다른 값이 들어가면 다른 숫자가 나와야 한다.

  • 서로 다른 데이터에 대해 모두 다른 숫자가 나오면 BEST다.

• 유효한 인덱스만을 반환해야한다.

  • 해시함수는 해시테이블(배열)의 크기를 알고 있어야 하며, 그 배열에서 사용가능한 index만을 반환해야한다.

• 키를 해시테이블 전체에 고르게 할당해야 한다.

  • 모든 데어터가 다른 해시값을 가지면 최선이지만, 그렇지 않을 경우 중복을 최소화 해야하고 중복이 특정 키에 몰려있어선 안 된다.

해시 테이블은 속도가 매우 빠르다.

데이터를 조회할 때 해시함수를 사용하면 한 번의 해시함수 실행으로 그 데이터의 index를 알 수 있다.
따라서 index를 알고 있는 배열데이터를 조회하는 것과 같은 실행시간(평균 O(1))으로 검색이 가능하다.

또한 이미 크기가 정해진 배열을 사용하므로 요소를 변경할때 다른 요소들을 이동시켜야 하는 등의 작업이 필요없으므로 추가/삭제시의 속도도 빠르다.

따라서 평균적인 경우 해시테이블은 탐색, 삽입, 삭제 각각 O(1)시간으로 가능하다.

그러나 최악의 경우(안 좋은 해시함수를 사용하는 경우)에는 탐색, 삽입, 삭제에 각각 O(n)의 시간이 걸리게 될 수있으므로 유의해야한다.

해시테이블은 충돌할 수 있다.

해시테이블 충돌(collision)이란?

해시테이블 배열의 크기가 한정적이고, index를 반환하는 해시함수에 한계가 있을수 있으므로 KEY는 다른데 해시값이 같은 경우가 생길 수 있다.

그럴 경우 다른 KEY가 같은 index를 할당 받게된다는 것이므로, 나중에 입력된 값이 이전의 값을 덮어쓰게되어 이전 값이 삭제되는 문제가 생긴다.

이를 충돌(collision)이라고 한다.

충돌을 해결하는 방법

충돌이 발생했을때 해결할 수 있는 방법들이 있다.

체이닝 Separate Chaining

가장 단순한 해결법으로, 해시테이블의 인덱스 별로 연결 리스트(Linked List)를 생성하는 것으로 해결하는 방법이다.

배열의 각 요소로 값이 아닌 연결 리스트를 넣는 방식이다.

그러나 연결리스트가 길어질수록 (연결리스트의 검색은 O(n)이므로) 속도가 느려질 수 있고(최악의 경우 연결리스트의 데이터를 검색하는 속도 O(n)이 나올 수 있음), 연결리스트를 위한 별도의 메모리공간이 소모된다는 단점이 있다.

선형 탐색법 Linear Probing

해시테이블에 새 요소를 추가할때 index가 이미 사용중이라면, 'index + 1'을 찾고, 역시 사용중이라면 'index + 2' 를 찾는 식으로 충돌을 피하는 방법이다.

그러나 선형 탐색이 누적되면, 선형탐색으로 할당된 뭉치가 커지는 집적화(clustering)문제가 발생하여 평균 탐색시간을 길게 만드는 문제가 생긴다.
또한 JavaScript처럼 연관배열을 사용하는 것이 아니라 배열의 크기를 미리 정해야하는 언어를 쓰는 경우라면, 배열 인덱스가 범위를 넘어서는 경우에 대한 처리를 해야한다.

이중 해싱 Double Hashing

2개의 해시함수를 사용하여, 충돌이 발생했을 경우 다른 해시함수로 다른 해시값을 만들어내는 방식이다.

좋은 해시함수와 리사이징으로 해시테이블의 성능을 관리해야한다.

"치료보다 예방이 먼저다"라는 말이 있다.

역시 충돌에 대비는 해야하지만, 최선은 애초에 충돌을 만들지 않는 것이다.

좋은 해시함수를 사용한다.

좋은 해시함수는 삽입/조회 속도가 빠르고 충돌 확률이 낮아야한다.
직접 해시함수를 만들 수 도 있겠지만, 오랜 시간과 많은 사람들에 의해 검증된 알려진 해시함수들이 있으니 잘 알려진 해시함수를 이용하는 것도 좋은 방법이다.

해시함수는 계속 연구/발전되어 연구/발전되어 암호화 등에도 사용되고 있다.(ex. SHA)
개발자라면 자주 사용하게되는 사용자 비밀번호 암호화에도 이러한 해시함수가 사용된다.

적절히 리사이징(resizing)한다.

리사이징이란 해시테이블의 배열크기를 조정하는 것이다.
리사이징으로 배열의 크기를 확장하면 index로 사용할 수 있는 범위가 늘어나므로 충돌이 줄어든다.

보통 사용률(해시테이블에 들어있는 루트배열의 사용률)이 0.7보다 커지면 리사이징한다.

인터페이스

• items - 데이터 목록
• put(key, value) - 해시테이블에 데이터를 추가한다 (이미 데이터가 있다면 수정한다).
• remove(key) - KEY에 해당하는 데이터를 삭제한다.
• get(key) - KEY에 해당하는 데이터의 값을 반환한다.

구현 - JavaScript에서의 해시 테이블

해시 테이블은 대부분의 프로그래밍 언어에서 자체 구현되어있다.
Python의 경우 Dictionary라는 이름으로, JavaScript에서는 Map객체가 해시테이블로 구현되어 있다.

JavaScript배열과 간단한 'lose lose 해시함수'를 이용하여 해시테이블을 구현해보았다.

class HashTable {
  constructor(size) {
    this._items = [];
    // JS의 배열은 자동으로 사이즈가 조절이 되므로 size를 굳이 받을 필요는 없지만, Hash값의 범위를 정하기 위해 받음.
    this._size = size;
  }

  put(key, value) {
    const index = this._loseLoseHash(key);

    this._items[index] = value;
  }

  remove(key) {
    const index = this._loseLoseHash(key);

    this._items[index] = undefined;
  }

  get(key) {
    const index = this._loseLoseHash(key);

    return this._items[index];
  }

  toString() {
    let result = "### Hash Table ###\n\n";
    this._items.forEach((val, index) => {
      result += `${index}: ${val}\n`;
    });

    return result;
  }

  // 성능이 좋지는 않지만, 구현이 단순한 lose lose 해시함수를 이용해서 구현한 해시함수
  _loseLoseHash(key) {
    let hash = 0;
    key.split("").forEach((_, index) => {
      hash += key.charCodeAt(index);
    });

    return hash % this._size;
  }
}

// Test
it("HashTable 클래스는 잘 동작한다.", () => {
  const hashTable = new HashTable(30);

  hashTable.put("monkey", "엉덩이가 빨갛다");
  hashTable.put("cat", "귀엽지만 도도하다");
  hashTable.put("elelphant", "코로 받아 먹는다");

  expect(hashTable.get("monkey")).toEqual("엉덩이가 빨갛다");
  expect(hashTable.get("cat")).toEqual("귀엽지만 도도하다");
  expect(hashTable.get("elelphant")).toEqual("코로 받아 먹는다");

  hashTable.remove("cat");
  expect(hashTable.get("cat")).toEqual(undefined);
});

활용 사례

• DNS 확인(DNS resolution): 도메인에 해당하는 IP주소를 찾아주는 작업
• 웹서버의 캐싱
• 데이터 중복 확인