19 해시 테이블

19.1 해시 테이블(해시 맵)

  해시 테이블이란 키와 값을 쌍으로 저장하는 자료 구조를 말한다. 많은 프로그래밍 언어에 내장되어 있는 자료 구조이다. python은dictionaries, Java Script는 Object와 Maps, Java는 Go, Scala 그리고 Maps, Juby는 Hashes로 알려져 있다. 이 처럼 언어마다 해시 테이블이 내장되어 있고 해시 테이블은 추상적인 개념이기 때문에 여러 가지 방법으로 코딩할 수도 있다. 해시 테이블은 일반적인 배열과는 다르다. 배열은 인덱스를 가지지만 해시 테이블은 순서를 가지지 않는다. 해시 테이블이 좋은 이유는 새로운 값을 추가하거나 제거하는데 아주 빠르고 데이터 그 자체가 해시 테이블 방법에 따라 저장되는 것이 편한 경우가 많다.

 

19.2 해시 함수

  해시 함수는 임의의 크기를 가지는 데이터를 입력하면 정해진 크기의 데이터를 출력해주는 함수이다. 즉, 입력값을 측정해서 정해진 크기의 출력값을 반환한다. 그래서 일정한 기준을 정해서 만들어야 하는데, 그게 매우 어렵기 때문에 해시 함수를 연구하는 많은 연구진들이 있다. 내가 공부한 해시 함수는 특정 데이터를 해시 함수에 넣으면 일정하게 배열의 인덱스 번호를 반환하는 것이다. 그리고 그 인덱스 번호를 기준으로 배열에 [키,값] 배열을 만들어서 저장한다. 반대로 정보가 필요한 경우에는 해시 함수에 필요한 정보의 키를 넣으면 인덱스 번호를 알려주고 그 인덱스 번호를 기준으로 배열에서 정보를 찾아내는 것이다. 이것이 바로 해시 함수의 역할이다.

 

※해시 함수의 특징

1) 동작이 매우 빠르다.(해시 함수는 반복적으로 사용되기 때문에 동작이 빨라야한다.)

2) 기본적으로 일관된 방식으로 분배 해서 다른 데이터들과 겹치지 않게 해야 한다.(그러므로 기준 설정이 매우 어렵다.)

3) 결정론적이다.(특정 입력값을 입력할 때마다 무조건 같은 출력값이 반환되어야 한다.)

 

19.3 해시 함수

//어떤 기준으로 만들든 상관 없지만, 중요한것은 빠르고, 항상 동일한 입력에 동일한 출력이 나와야한다는 점이다!
function hash(key, arrayLen) { // arrayLen은 배열의 길이를 의미함! 
    //몇개의 요소를 가지는 배열에서 어디에 저장할지를 찾기위해 배열의 길이도 인수로 받는것임!
  let total = 0;
  for (let char of key) {
    let value = char.charCodeAt(0) - 96 // 96을 빼면 알파벳 순서가 나온다!! 
    //charCodeAt() 메서드는 주어진 인덱스에 대한 UTF-16 코드를 나타내는 0부터 65535 사이의 정수를 반환한다
    total = (total + value) % arrayLen;
  }
  return total;
}

※ 위 해쉬 함수의 문제점

1) 문자열에 대해서만 해시 처리를 한다. 숫자나 불리언 값이나 배열 같은 데이터를 입력하면 제대로 작동하지 않을 것이다.

2) O(N)시간 복잡도를 갖는다. 즉, 문자열의 길이가 길어지면 계산하는 시간이 길어진다.

3) 무작위성이 떨어진다.(해시 함수의 반환 값이 동일한 경우가 많다.)

이러한 문제점들을 개선해서 다시 위의 해시 함수를 만들어 보자.

// 위 문제점들을 토대로 성능 향상시켜보기
function hash(key, arrayLen) {
  let total = 0;
  let WEIRD_PRIME = 31; // 소수를 하나 사용한다!(어떤 숫자로도 나눌 수 없는 수)
  //해시 함수는 거의 대부분 소수를 사용함
  //이렇게 하면 충돌이 줄어든다. 데이터들이 최대한 같은 바구니에 들어가지 않게하기 위해
  //수학적 원리는 제쳐주도 해쉬 함수에 보통 소수를 사용한다는것을 기억!
  //심지어 배열도 소수라면 충돌 가능성도 엄청나게 떨어짐!(소수 값의 테이블과 짝수 값의 테이블 충돌 횟수차이가 수십배에서 수천배까지도 남!)
  for (let i = 0; i < Math.min(key.length, 100); i++) { 
    // 즉 반복은 100이하로만 하게 됨!(아무리 데이터가 길어도 100번까지만 돌게됨 0~99) 속도를 빠르게 하기 위해
    let char = key[i];
    let value = char.charCodeAt(0) - 96
    total = (total * WEIRD_PRIME + value) % arrayLen;
  }
  return total;
}

19.4 해시 함수 충돌 처리

  임의의 데이터를 해시 처리 했는데 같은 값이 반환되는 경우의 해결방법에는 대표적으로 2가지가 있다. 첫 번째는 개별 체이닝(Separate Chaining) 방법과 직선 탐색법(Linear Probing)이 있다.

 

1) 개별 체이닝(Separate Chaining)

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

( [ [  ],[  ] ] )즉, 같은 공간에 같이 저장하는것이다. 이러한 방식의 장점은 배열의 길이 보다 더 긴 데이터를 저장할 수 있다.

 

2) 직선 탐색법(Linear Probing)

  각 위치에 하나의 데이터만 저장한다는 규칙을 그대로 지키려고 하는 것이다. 충돌이 발생하면 해당 위치를 기준으로 다음 비어있는 공간이 어디인지 확인하고 저장한다. 이렇게 하면 데이터가 같은 인덱스에 저장되는 것을 막을 수 있다. 딱 배열의 길이에 맞는 데이터 개수만 저장이 가능하다.

 

19.5 해시 테이블과 set & get 메서드

  set메서드는 임의의 데이터를 해시 처리 후 해시 테이블에 저장하는 기능을 하고, get 메서드는 이미 해시 테이블에 저장되어 있는 데이터를 찾기 위해 키를 인수로 받아 해당 데이터가 존재하는지 확인하는 기능을 한다. 

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

  _hash(key) { //키를 받아 해시 함수로 저장위치인 해시테이블의 인덱스 번호 받기
    let total = 0;
    let WEIRD_PRIME = 31;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      let char = key[i];
      let value = char.charCodeAt(0) - 96
      total = (total * WEIRD_PRIME + value) % this.keyMap.length;
    }
    return total;
  }
  
  set(key,value){ //키와 값을 받아 해시테이블에 저장
    let index = this._hash(key);
    if(!this.keyMap[index]){ // 배열안에 해당 인덱스가 없으면 undefined가 반환됨
        //참고로 빈 배열 자체는 truthy임!!! 
      this.keyMap[index] = [];
    }
    this.keyMap[index].push([key, value]); //해당 인덱스로 접근하면 또 다른 배열이 나오 
    //그 배열에 push메서드 활용
  }
  
  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] //배열 안에 배열 안에 배열 안의 1번 인덱스임
        }
      }
    }
    return undefined;
  }
}