해시 테이블

해시 테이블은 key,value로 데이터를 저장하는 자료 구조 중 하나로, 데이터를 빠르게 검색하는 자료 구조이다. key와 해시 함수를 이용해 변환한 값을 인덱스로 삼아 value를 저장한다.

해시 함수

해시 함수는 데이터를 효율적으로 관리하기 위해 임의의 길이의 데이터를 고정된 길이의 데이터로 맵핑하는 함수로 원래 데이터 값을 키(key), 매핑 후 값을 해시 값(Hash value), 매핑하는 과정 차레를 해싱이라고 한다.

예를 들어 (key,value)가 (“John Smith”,“521-1234”)인 데이터를 크기가 16인 해시 테이블에 저장한다고 하면, hash function을 이용해 key값으로 index 값을 먼저 계산한다.

이후 arr[index] = “521-1234”로 데이터를 저장하게 된다.

이렇게 해시 테이블을 이용하면 key 값으로 데이터를 바로 찾을 수 있기 때문에 매우 빠르게 데이터를 조회/저장/삭제 할 수 있으며, 해시 테이블의 시간 복잡도는 O(1)이다.

서로 다른 입력 값에서 동일한 해시 값이 발생하는 해시 충돌이 일어날 수 있다.

해시 충돌을 해결하는 방법에는 여러 가지가 있는데 그 중에서 체이닝과 선형 탐사 방법을 살펴보면

체이닝(Chaning)

버켓에 데이터를 삽입하다가 해시 충돌이 발생하면 연결 리스트로 데이터를 연결하는 방식

위의 그림에서 John Smith와 Sandra Dee의 인덱스가 152로 충돌이 발생하게 되어 Sandra Dee를 John Smith 뒤에 연결 함으로써 충돌을 처리하고 있다.

체이닝을 통해 해시 테이블을 구현할 때의 시간 복잡도는 다음과 같다.

• 삽입 : 연결 리스트에 추가하기만 하면 되기 때문에 O(1)
• 삭제/탐색 : 최악의 경우 키 값의 개수(n) 만큼 반복해야하기 때문에 O(n)

선형 탐사(Linear Probing)

최소 해시 값에 해당하는 버킷에 이미 데이터가 저장되어 있으면 다음 버켓 또는 몇 개를 건너 뛰어 데이터를 삽입하는 방식

선형 탐사는 특정 해시 값 주변에 데이터가 밀집되는 클러스터링 문제가 발생하고 이로 인해 탐색과 삭제가 느려지게 되는 문제점이 있다.

특정 데이터를 찾기 위해서는 순차적으로 접근해야 하기 때문에 시간 복잡도는 O(n)이다.

해시 테이블 구현하기(JS)

class HashTable {
  constructor(size = 7) {
    this.dataMap = new Array(size);
  }

  // 암호화 해줄 함수
  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash = (hash + key.charCodeAt(i) * 23) % this.dataMap.length; // 랜덤하게 암호화
    }
    return hash; // 0~6 값을 반환
  }

  set(key, value) {
    let index = this.hash(key);
    // 해당 인덱스에 배열 없으면 새로운 배열 만들어줌
    if (!this.dataMap[index]) {
      this.dataMap[index] = [];
    }
    this.dataMap[index].push([key, value]);
    return this;
  }

  get(key) {
    let index = this._hash(key);
    if (this.dataMap[index]) {
      for (let i = 0; i < this.dataMap[index].length; i++) {
        if (this.dataMap[index][i][0] === key) return this.dataMap[index][i][1];
      }
    }
    return undefined;
  }

  key() {
    let allKeys = [];
    for (let i = 0; i < this.dataMap.length; i++) {
      if (this.dataMap[i]) {
        for (let j = 0; j < this.dataMap[i].length; j++) {
          allKeys.push(this.dataMap[i][j][0]);
        }
      }
    }
    return allKeys;
  }
}