해시 테이블 - Hash Tables

목차

1. 해시 테이블 소개
2. 해시 테이블에 대한 더 자세한 정보
3. 해시 함수 소개
4. 첫번째 해시 함수 작성하기
5. 해시 함수 성능 향상시키기
6. 충돌(Collision) 처리
7. 해시 테이블 Set과 Get 메소드
8. 해시 테이블 Set 메소드 솔루션
9. 해시 테이블 Get 메소드 솔류션
10. 키와 값이 한 쌍을 이루는 해시 테이블
11. 해시 테이블의 키와 값 솔루션
12. 해시 테이블의 빅오 복잡도

 

1. 해시 테이블 소개

슬라이드 : Hash Tables (slides.com)

Hash Tables

목표

①. 해시테이블이 무엇인지 설명하기
②. 해싱 알고리즘 정의하기
③. 좋은 해싱 알고리즘 만들기
④. 해시 테이블에서 충돌이 일어나는 경우와 충돌이 무슨 의미인지 이해하기
⑤. 충돌을 해결하는 2가지 방법 배우기 : 개별 체이닝(separate chanining), 선형 조사법or직선 탐색법(linear probing)

 

①. 해시 테이블이란?

해시 테이블은 key-value 쌍을 저장하는데 사용한다.

배열과 비슷하지만, key는 순서를 가지지 않는다.

배열에서는 당연히 인덱스가 0에서 시작하여 연속되는 숫자로 이어진다. 이건 해시 테이블이 아니다.

해시 테이블이 좋은 이유는 값을 찾거나, 새 값을 추가하거나, 값을 제거하는데 아주 빠르다. 모든것이 빠르다.

 

Q. 그럼 해시 테이블을 왜 배워야 할까?

속도가 빠르기 때문이다.

 

Q. 연속적인 흐름이 있는 데이터가 있다면?

배열을 사용하면 된다.

 

Q. 특정 언어에서 사용되는 해시 맵 or 해시 테이블의 간단한 예시 (key-value) ?

파이썬 - Dictionaries, 자바스크립트 - Objects, Maps

자바, 고, 스칼라 - Maps루비 - Hashes

 

 

하지만, 자바스크립트에서 내장된 객체나 파이썬에 내장된 딕셔너리를 사용할 수 없다고 가정한다.

그래도 key-value 데이터 저장법이 필요하다면 직접 만들어야 한다. -> 해시 테이블 구현하기

 

색깔을 저장할 때 위의 배열 처럼 쓰면 헤깔림

대신 key-value 쌍으로 만들어서 저장하면 편리함. 즉 colors['cyan'] 이 colors[2] 보다 직관적임

 

 

2. 해시 테이블에 대한 더 자세한 정보

HASH 파트

1. 해시 테이블을 적용하기위해서, 배열을 사용한다.

2. key값으로 value를 찾기 위해서, key값을 알맞은 배열 인덱스로 변환하는 방법이 필요하다.

3. 이런 작업을 수행하는 함수를 해시 함수(hash function)라 부른다.

 

3. 해시 함수 소개

좋은 해시 함수를 결정하는 기준?

1. Fast (즉, 상수의 시간)

나쁜 예시, 느림

2. 일관된 방식으로 분배를 해서 다른 것들과 겹치지 않게 해야한다. (만약 요소가 같은 자리에 저장되면 충돌 발생)

나쁜 예시, 일관된 방식의 분배가 아님. 항상 0만 리턴

3. 결정론적(Deterministic)이어야 한다. 즉, 특정 입력값을 입력할 때마다 같은 출력값이 나와야 한다는 말이다.

나쁜 예시, 무작위 값이 나오면 안됨.

 

4. 첫번째 해시 함수 작성하기

charCodeAt

//basic_hash.js
function hash(key, arrayLen) {
  let total = 0;
  for (let char of key) {
    // map "a" to 1, "b" to 2, "c" to 3, etc.
    let value = char.charCodeAt(0) - 96
    total = (total + value) % arrayLen;
  }
  return total;
}
// hash(' ', 10); 길이 10을 넣으면 0~9 사이의 값이 항상 나옴
hash('pink', 10); // 0
hash('orangered', 10); // 7
hash('cyan', 10); // 3

문제점

1. 이 함수는 스트링에 대해서만 해시 처리를 한다. (불린, 숫자 넣으면 작동안함. 곧 해결할 것)

2. 상수 값의 시간이 걸리는게 아니다. key값의 길이에 달려있다.

3. 무작위 성이 덜하다. 데이터가 생각보다 뭉치기 쉽다.

 

5. 해시 함수 성능 향상시키기

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

hash('hello', 13) // 7
hash('goodbye', 13) // 9
hash('hi', 13) // 10
hash('cyan', 13) // 5

1. 속도 빠르게 하기

예를 들어, key의 길이가 200자, 500자, 혹은 1억자 가 된다고 가정한다.

그러면 모든 글자를 하나하나 루프하지 않는 것이 좋다.

그래서 최소값을 추가한다. Math.min(키의 길이, 100) 으로해서 값을 판정한다.

키의 길이가 백만자면 루프가 100번만 돌게한다.

 

2. 소수 추가 하기

해시 함수는 거의 대부분 소수를 이용한다.몇 가지 이유가 있는데, 일단 이렇게 하면 충돌이 줄어든다.

가능한 한 데이터를 펼쳐서 다시 회수하는 것이 빠르도록 하고 싶은 것이다.

 

 

6. 충돌(Collision) 처리

1. 데이터 저장 공간이 아주 크고, 해시 함수가 아주 좋은 것일지라도, 여전히 충돌은 발생한다.

2. 충돌을 해결하는 2가지 방법 : 개별 체이닝(separate chaining), 선형 조사법(linear probing)

 

① 개별 체이닝 (Separate Chaining)

- 같은 장소에 여러 데이터를 저장할 때, 배열이나 연결 리스트 등과 같은 것을 활용하여 이중 데이터 구조를 쓴다.

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

- 이 테이블에는 10개 보다 더 많은 데이터를 저장할 수 있는 장점이 있다.

② 선형 조사법or 직선 탐색법 (Linear Probing)

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

- 충돌이 일단 발생하면, 다음 빈 칸이 어디인지 확인한다.

- 이렇게 하면 데이터가 같은 인덱스에 저장되는 것을 막을 수 있다. (중첩 구조에 데이터를 저장할 필요가 없다)

- 최대 저장량은 10개 밖에 안된다.

7. 해시 테이블 Set과 Get 메소드

set 의사코드

1. key와 value를 인자로 받는다.

2. key를 해시 처리한다. (어디에 저장할지 알아내는 과정)

3. 개별 체이닝을 통해서 해시 테이블에 key-value 쌍을 저장한다.

 

get 의사코드

1. key를 인자로 받는다.

2. key를 해시 처리한다.

3. 일단 값을 얻고나면 keyMap 배열의 인덱스에 해당하는 자리로 간다.

4. 그리고 그 값을 확인 (개별 체이닝 사용)

5. 해시 테이블에 해당하는 것이 없다면 undefined 리턴

 

8. 해시 테이블 Set 메소드 솔루션  &  9. 해시 테이블 Get 메소드 솔루션

//hash_table_set_and_get.js
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]){
      this.keyMap[index] = [];
    }
    this.keyMap[index].push([key, value]);
  }
  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;
  }
}

let ht = new HashTable(17);
ht.set("maroon","#800000")
ht.set("yellow","#FFFF00")
ht.set("olive","#808000")
ht.set("salmon","#FA8072")
ht.set("lightcoral","#F08080")
ht.set("mediumvioletred","#C71585")
ht.set("plum","#DDA0DD")

 

10. 키와 값이 한 쌍을 이루는 해시 테이블

keys 메서드

- 테이블에 있는 모든 key를 포함한 목록을 출력

 

values 메서드

- 한 배열에 모든 값을 다 모아서 해당 배열 리턴

 

11. 해시 테이블의 키와 값 솔루션

// hash_table_keys_and_values.js
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]){
      this.keyMap[index] = [];
    }
    this.keyMap[index].push([key, value]);
  }
  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;
  }
  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;
  }
}

let ht = new HashTable(17);
ht.set("maroon","#800000")
ht.set("yellow","#FFFF00")
ht.set("olive","#808000")
ht.set("salmon","#FA8072")
ht.set("lightcoral","#F08080")
ht.set("mediumvioletred","#C71585")
ht.set("plum","#DDA0DD")
ht.set("purple","#DDA0DD")
ht.set("violet","#DDA0DD")

console.log(ht.keyMap);
console.log(ht.keys()); // (7) ['plum', 'salmon', 'maroon', 'yellow', 'olive', 'lightcoral', 'mediumvioletred']
console.log(ht.values()); // (7) ['#DDA0DD', '#FA8072', '#800000', '#FFFF00', '#808000', '#F08080', '#C71585']

ht.keys().forEach(function(key){
  console.log(ht.get(key));
})

 

12. 해시 테이블의 빅오 복잡도

삽입: O(1)

삭제: O(1)

접근: O(1)  - key가 주어졌을 때 그에 해당하는 value를 찾는다는 말

 

---

 

회고

1. 해시 테이블은 key-value 쌍의 모음으로 많은 프로그래밍 언어에 이미 존재한다.

    (파이썬 - 딕셔너리, JS - Object, map 등등)

2. 해시 테이블은 key를 이용해서 value를 아주 빠르게 찾을 수 있다.

3. 해시 테이블은 key-value 쌍을 아주 빠르게 추가할 수 있다.

4. 해시 테이블은 배열을 이용해서 데이터를 저장한다, key를 해싱해서 배열의 인덱스를 받은 다음에 해당 위치에 데이터를 저장한다.

5. 좋은 해시 함수가 필요하다.

    - 빨라야함

    - 일관된 방식으로 작동해야 함

    - 요소간 충돌이 적게 일어나야 함

    - 가능한 넓게 퍼뜨려서 데이터를 저장해야 함

    - 결정론적으로 작동해야 함 (특정 입력값은 항상 같은 출력값이 나와야 함)

6. 같은 인덱스에 두 가지 데이터를 넣어야 할 때 사용할 수 있는 두 가지 전략이 있다.

    ① 개별 체이닝 (Separate Chaining) - 데이터들을 중첩하는 구조로, 같은 인덱스의 배열에 데이터를 저장한다.

    ② 직선 탐색법 (Linear Probing) - 해싱 인덱스가 중복되면 다음 빈 칸을 찾아내어서 데이터를 저장한다.