[자료구조] 해시테이블

1. 해시테이블이란

js의 객체와 같다고 생각하면된다.

해시테이블은 객체와 마찬가지로 키-값 쌍을 저장하는데 사용한다.

배열과는 다르게 해시테이블은 순서를 가지지 않는다.

값을 찾거나, 새로운 값을 찾거나, 값을 제거하는데 매우 빠르다.

 

모든 언어들은 해시테이블의 구조를 가지고 있다.

2. 해시함수 조건

(1) 속도

무언가를 찾아내거나 바꾸거나 제거하기 위해 접근할때마다 해시 함수를 실행시켜야 하기 때문에 

해시함수는 빨라야 한다.

(2) 일관성

일관된 방식으로 분배를 해서 다른 값들과 겹치지 않게 해야 한다.

(3) 결정론적

특정 입력값을 입력할때마다 같은 출력값이 나와야 한다.

3. 해시함수 구현

function hash(key, arrayLen) {
  let total = 0;
  let WEIRD_PRIME = 31; 
  for (let i = 0; i < Math.min(key.length, 100); i++) {
    let value = char.charCodeAt(0) - 96;
    total = (total * WEIRD_PRIME + value) % arrayLen;
  }
  return total;
}

WEIRD_PRIME 값은 소수로 설정하여 충돌을 줄인다.

연구 결과 소수인값을 이용할때 아닌경우보다 값이 겹칠 확률이 훨씬 더 적었다.

루프를 최대 100개만 돌게해서 속도를 높였다.

total값을 인덱스로 삼아 배열의 인덱스값에 넣어주려고 한다.

4. 중복값 충돌 해결 전략

(1) 개별 체이닝(Separate Chaining)

개별 체이닝은 기본적으로 같은 장소에 여러 데이터를 저장할때 배열이나 연결리스트 등과 같은 것을 활용하여

이중 데이터 구조를 쓰는것이다. ex) 2차배열사용

여러개의 키-값 쌍은 같은 자리에 지정할 수 있다.

(2) 직선 탐색법(Linear Probing)

각 위치에 하나의 데이터만 저장한다는 규칙을 그대로 살려서 지키다.

충돌이 발생하면 다음 빈칸이 어디인지 확인하고 빈칸에 넣는다.

5. 해시테이블 구현

(1) 클래스

class HashTable {
  constructor(size = 53) {
    this.keyMap = new Array(size);
  }
}

(2) hash

키 값을 해싱하는 메소드

_hash(key) {
    let total = 0;
    let WEIRD_PRIME = 31;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      let value = char.charCodeAt(0) - 96;
      total = (total * WEIRD_PRIME + value) % this.keyMap.length;
    }
    return total;
  }

(3) set

배열에 집어넣기

set(key, value) {
    let index = this._hash(key);
    if (!this.keyMap[index]) {
      this.keyMap[index] = [];
    }
    this.keyMap[index].push([key, value]);
}

(4) get

받은 키값을 해싱하여 해당하는 밸류값을 뽑아낸다.

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

(5) keys

모든 키값을 중복제거하여 뽑아낸다.

keys() {
    let keysArr = [];
    for (let i = 0; i < this.keyMap.length; i++) {
      if (this.keyMap[i]) {
        for (let j = 0; j < this.keyMap[i].length; j++) {
          if (keysArr.includes(this.keyMap[i][j][0])) {
            keysArr.push(this.keyMap[i][j][0]);
          }
        }
      }
    }
    return keysArr;
}

(6) values

모든 밸류값을 중복제거하여 뽑아낸다.

values() {
    let valuesArr = [];
    for (let i = 0; i < this.keyMap.length; i++) {
      if (this.keyMap[i]) {
        for (let j = 0; j < this.keyMap[i].length; j++) {
          // 중복된값 제거
          if (valuesArr.includes(this.keyMap[i][j][1])) {
            valuesArr.push(this.keyMap[i][j][1]);
          }
        }
      }
    }
    return valuesArr;
  }

6. 해시테이블 빅O

Insertion(삽입)	Deletion(삭제)	Access(접근)
O(1)	O(1)	O(1)

평균적으로 위 표와같은 빅O를 가지지만 해시함수에 따라 다르다.

실제로 빅O는 해시함수가 얼마나 좋은지에 달려있다.

해시 함수가 얼마나 빠른지, 얼마나 고르게 데이터를 분배하여 충돌의 횟수를 줄이는지가 관건이다.

 

7. 결론

해시함수 만들지말고 내장된 객체 쓰자.