해시 테이블(HASH TABLES)

해시 테이블?

key-value 쌍을 저장하는데 사용

순서가 정해져 있지 않다(배열은 0,1,2... 인덱스가 있지만 해시는 아님)

값을 다루는데 매우 빠르다

거의 모든 프로그래밍 언어가 해시 테이블과 같은 데이터 구조를 가지고 있음(속도가 매우 빠르기에)

 

ex) 데이터를 저장하는 배열

0

1

2

3

4

5

6

7

8

9

아래 간단한 예시는 string으로 된 key를 배열에서 사용하는 유효한 인덱스, 즉 작은 숫자로 바꿔주는데 사용되는

해시 함수에 대한 예시를 보여준다

 

해시 함수에서는 숫자가 나옴, 아래 있는 pink,cyan,orangered를 해시함수에서 나온 번호대로 배열에 저장해준다

pink -> 0 | ["pink", "#ff69b4"]

cyan -> 3 | ["cyan","#00ffff"]

orangered -> 7 | ["orangered","#ff4500"]

 

해시 함수는 단방향 함수 ( 결과만 만들어 낼 뿐 결과값을 가지고 원래 값으로 돌릴 수는 없다)

 

Big O

성능이 안 좋은 해시 함수는 O(n) -> 불균형하게 데이터를 한쪽으로 몰아서 넣어두면 n개의 데이터를 가져오는데 n의 시간

 

Best Case

삽입: O(1) 

삭제: O(1)

접근: O(1)

 

 

 

좋은 해시를 만드는 법

1. 빨라야함

2. 일관된 방식으로 분배해야함, 다른 것들과 겹치지 않게 해야함

3. 결정론적임(특정 입력값을 입력할 때마다 같은 출력값이 나와야 한다)

-> 불확실성이 있어서는 안된다.

 

간단한 해시

function hash(key,arrayLen){
  let total=0
  for(let char of key){
    let value=char.charCodeAt(0)-96
    total=(total+value) % arrayLen;
  }
  return total
}

hash("pink",10) -> p, i, n ,k 에 대해 각각 charCodeAt(0) - 96한 값을 value에 넣어서 마지막 total과 배열의 길이를 가지고 나머지 연산자를 통해서 배열의 길이에 맞는 인덱스 번호를 만들고 반환함

 

문제점 : String만 해시, 상수 시간이 아님, 랜덤성

*charCodeAt() 메서드는 주어진 인덱스에 대한 UTF-16 코드를 나타내는 0부터 65535 사이의 정수를 반환 (defalut는 0)

 

[발전]

해시 테이블은 소수 값의 길이를 가지는 것이 항상 유리하고, Prime number (소수)를 사용해서 key를 더 고르게 퍼지게 하는데 도움을 준다

 

- 최대 100개의 글자에만 루프 적용

- 앞 100글자가 같으면? => 루프를 뒤에서부터 돌리거나 이런 방법을 고려해봐야한다

function hash(key,arrayLen){
  let total=0;
  let 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*PRIME+value)%arrayLen
  }
  return total
}

 

충돌 다루기

저장위치가 같을 때 해결하는 법은 많지만 그 중 2가지만 먼저 다뤄보겠다

 

1. 개별 체이닝 (Separate Chaining)

기본적으로 같은 장소에 여러 데이터를 저장할 때 배열이나 연결 리스트 등과 같은 구조를 활용하여 이중 데이터 구조를

사용하는 것

[ [] , [] ] 이런 구조로 저장되고 값을 찾으려면 해시로 먼저 방 번호를 찾아낸후 방 번호에서 루프를 돌려서 해당하는 값을 뽑아내는 방식으로 알고리즘을 만들면 된다.

 

2. 직선 탐색법(Linear Probing)

 

각 위치에 하나의 데이터만 저장한다는 규칙을 살림 -> 충돌이 발생하면 다음 빈 칸이 어디인지 확인 그리고 저장

 

set 함수(개별 체이닝)

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) -> 이걸 실행하면 size 미만의 값들 중 하나가 나온다
    그 인덱스에 데이터가 있는지 없는지 확인후 없으면 빈 배열을 생성해주고 있다면 push 해준다
    [ , , , , , [] ,]
    if(!this.keyMap[index]){
      this.keyMap[index]=[]
    }
    this.keyMap[index].push([key,value])
  }
}

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][1]
        }
      }
    }
    return undefined
  }
  
  같은 방 ex) 7번에 ["hi","there"] , ["bye","see"] 이런식으로 2개의 요소가 저장되있고
  파라미터 key와 같은 key를 가진 데이터를 조건문을 통해 확인한후 맞으면 value에 해당하는 값을
  반환시켜준다

keys 함수 / values 함수

  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;
  }
  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;
  }