자료 구조 - 해시 테이블(HashTable)

Key, Value 로 데이터를 저장하는 자료구조

빠르게 데이터를 검색할 수 있는 자료구조이다.

빠른 검색속도를 제공하는 이유는 내부적으로 배열(버킷)을 사용하여 데이터를 저장하기 때문이다.

 

해시 테이블의 평균 시간복잡도는 O(1)

해시 테이블은 각각의 Key 값에 해시 함수를 적용해 배열의 고유한 index를 생성하고, 이 index를 활용하여 값을 저장하거나 검색하게 된다.

 

 

자바스크립트 HashTable 구현하기

 

class HashTable {
  table = new Array(16);
  constructor() {}

  // key와 value를 받아 해시 테이블에 저장한다.
  setItem = (key, value) => {
    table[key] = value;
  };

  // key를 통해 value를 가져온다.
  getItem = (key) => {
    return "";
  };
}

16 칸 짜리 HashTable class를 생성하였고 배열에 값을 설정하는 setItem 메서드를 생성하였다.

HashTable의 배열에 접근하기위해서는 인덱스로 접근해야한다. 위에 선언한것 처럼 String 타입을 key로 사용할 수 없다.

그렇기 때문에 String 값을 number 형태로 바꾸어 number index에 데이터가 저장 되도록 해야한다.

이렇게 자료형을 변환하여 저장시켜주는 함수를 hash function 이라고 한다.

 

굳이 해시 함수를 사용하여 배열에 값을 할당하는 이유

해시 함수를 사용하지 않고 배열에 직접 저장한다면 최대 키 값에 대해서 알고 있어야한다. 또한 키 값이 매우 많아진다면 전체 탐색을 해야할 수도 있기 때문에 실용성이 떨어진다. 
일정하게 키 값이 정해진게 아니라면 키 값들이 배열에 넓게 분포되어 배열의 크키가 커지고 그에 따른 메모리 낭비도 발생할 수 있다. 따라서 해시 함수를 사용해서 데이터를 추가하는 사용자와 데이터를 추출해서 사용하는 사용자 모두 인덱스를 고려할 필요 없게 만든다면, 단순히 키 값만을 갖고 원하는 요소를 추가하거나 삭제할 수 있다는 장점이 있다.

 

class HashTable {
  table = new Array(71);
  constructor() {}

  // key와 value를 받아 해시 테이블에 저장한다.
  setItem = (key, value) => {
    // table[key] = value;
    const index = this.hashToIndex(key);
    this.table[index] = value;
  };

  // key를 통해 value를 가져온다.
  getItem = (key) => {
    const idx = this.hashToIndex(key);
    return this.table[idx];
  };

  // 문자열을 받아 인덱스로 변호나
  hashToIndex = (key) => {
    let hash = 17;
    for (let i = 0; i < key.length; i++) {
      hash = (13 * hash * key.charCodeAt(i)) % this.table.length;
    }
    return hash;
  };
}

해시 함수를 작성하는 방법 중 하나는 key로 들어오는 문자열을 charCode로 변환한 값을 사용한다.

 

const hashTable = new HashTable();

hashTable.setItem("firstName", "jeon");
hashTable.setItem("lastName", "dahoon");

console.log(`성은 ? ${hashTable.getItem("firstName")}`);
console.log(`이름은 ? ${hashTable.getItem("lastName")}`);