[알고리즘👽] 19. 해시 테이블

알고리즘

[알고리즘👽] 19. 해시 테이블

머털박사 2022. 9. 22. 18:14

해시 테이블 소개

목표

해시 테이블에 대해 설명
해싱 알고리즘 정의
어떤 것이 좋은 해시 알고리즘을 만드는 지
해시 테이블에서 충돌이 일어나는 경우와 충돌이 무슨 의미인지
충돌을 해결하는 두 가지 방법

해시 테이블이란?

해시 테이블은 key-value 쌍을 이루어 저장한다. 배열과 비슷하나 테이블 키는 순서를 가지지 않는다. 배열과 달리 해시테이블은 값을 찾거나 추가하거나 제거하는데 매우 빠르다.

배워야 하는 이유?

거의 모든 언어는 해시 테이블 종류의 구조를 가진다. 그건 속도가 매우 빠르기 때문이다. 순서가 중요하다면 배열에 저장하면 되지만 대부분 데이터는 그럴 필요가 없다. 그런 경우 해시 맵이나 해시 테이블을 사용하면 된다.

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

해시테이블이 어떻게 작동하는 지 이해하기 위해서 모형을 만들어 볼 겁니다. 이를 위해 배열이나 리스트를 사용할 겁니다. 숫자를 이용해 정보를 저장하는 방식이죠. 해시 테이블을 가지고 하는 것은 입력값을 받아들이는 겁니다. 이 과정을 도와줄 함수를 해시 함수라고 부릅니다.

해시 함수의 컨셉

해시 함수 소개

해시 함수는 정보 보호, 저장, 사이트 로그인 인증등에 도움이 된다. 암호 기술을 사용하는 암호 화폐에도 사용된다.

기본적인 해시 함수의 정의는 수천 자든 수백만 자든 임의의 크기를 가지는 데이터를 입력하면 정해진 크기의 데이터를 출력하는 함수다. 입력값을 측량해서 정해진 크기의 출력값을 내보낸다.

hash("Hello!")
// 7665438013419399415

파이썬에서 hash를 입력하면 위와 같이 결과값을 반환한다.

좋은 해시 함수의 조건이란?

빨라야한다.
일관된 방식으로 분배해서 다른 것과 겹치지 않게 해야한다.
좋은 해시 함수는 결정론적이다. 특정 입력값을 입력할 때마다 같은 출력값이 나와야 한다. 어떤 불확실성이 있으면 안된다.

첫번째 해시 함수 작성하기

hash("pink",100)

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

해시 개선하기

오직 스트링에 대해서만 해시 처리합니다.
이게 상수 값의 시간을 가지지 않는다. 키의 길이에 따라서 시간이 늘어난다.
생각보다 무작위성이 떨어진다. 데이터가 생각보다 뭉치기 쉽다.

해시 함수 성능 향상시키기

hash("pink",100)

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

function hash(key, arrayLen) {
    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_RPIME + value) % arryLen;
    }
    return total;
}

대부분의 해시 함수는 소수를 사용한다. 결국에는 테이블 자체의 길이에 대한 건데 데이터의 저장하는 배열의 길이가 소수일 경우, 31이나 13처럼요. 일반적으로 큰 것이 더 좋습니다. 근런 경우에 충돌이 일어날 확률이 더 적다.

만약에 여기서 같은 인덱스를 가지게 된다면 충돌이 일어난다.

충돌(Collision) 처리

해시 함수를 사용할 때 데이터가 아주 많이 있는 경우라면 충돌이 어느정도 일어날 가능성이 높다. 데이터 저장 공간이 아주 크고, 해시 함수가 좋은 것일지라도, 여전히 충돌은 발생한다.

이것을 해결하기 위한 방법은 두 가지가 있다. 1. 개별 체이닝(Separate Chaining)과 2. Linear Probing(직선 탐색법)이다.

Separate Chaining

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

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

Linear Probing

각 위치에 하나의 데이터만 저장한다는 규칙을 그대로 살려서 지키는 것이다. 충돌이 일단 발생하면 다음 빈 칸이 어딘지 확인한다. 이런 식으로 하면 데이터가 같은 인덱스에 저장되는 것을 막을 수 있다.

해시 테이블 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_RPIME + value) % this.keyMap.length;
    }
    return total;
    }
}

Set / Get

Set

키와 값을 받는다.
키를 해시 처리한다.
개별 체이닝 한다.

Get

키를 받는다.
키를 해시처리한다.
해시테이블에서 키와 값 쌍을 확인한다.

해시 테이블 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_RPIME + value) % this.keyMap.length;
    }
    return total;
    }
    set(key, value){
        let index = this._hash(key)l
        if(!this.keyMap[index]) {
            this.keyMap[index] = [];
        }
        this.keyMap[index].push([key, values]);
    }
}

해시 테이블 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_RPIME + 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, values]);
    }
    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 ;
        }
        retrun undefined;
    }
}

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

Key

테이블에 있는 모든 키를 포함한 목록을 출력한다.

Value

테이블에 있는 모든 값을 포함한 목록을 출력한다.

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

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")

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

해시 테이블의 빅오 복잡도

메서드	빅오
Insert	O(1)
Deletion	O(1)
Access	O(1)

저작자표시

'알고리즘' 카테고리의 다른 글

[알고리즘👽] js 최대 공약수 유클리드 호제법으로 구하기 (0)	2022.10.13
[알고리즘👽] 20. 그래프 (1)	2022.09.23
[알고리즘👽] 18. 이진 힙 (1)	2022.09.21
[알고리즘👽] 17. 트리 순회 (0)	2022.09.20
[알고리즘👽] 16. 이진 검색 트리 (0)	2022.09.20

현재글[알고리즘👽] 19. 해시 테이블

개발

프론트엔드 중심으로 공부한 내용 정리해서 업로드합니다.

git push -u 옵션, 프론트엔드 면접질문, git 초기화, js유효성검사, gitlab github 차이, git push -u option, Tailwind단점, javascirpt, OpenSlide, Tailwind장점, 회고록, JavaScript, 알고리즘, 알고리즘 큐, 알고리즘 스택, git init 초기화, http 캐시, git과 github차이, REACT, git push -u origin main 뜻,

Today :
Yesterday :

개발