(JS 자료구조) 해시 테이블(Hash Table) - 해시 맵

정태호·2023년 3월 25일
JavaScript자료구조
0

Javascript 알고리즘 및 자료구조(Colt Steele 강의 참고)

목록 보기
9/13

해시 테이블(Hash Table)

해시 테이블이란?

  • 해시 테이블은 key-value 쌍을 저장하는 데 사용한다.
  • 해시 테이블의 key는 순서를 갖지 않는다.(배열은 인덱스)
  • 해시 테이블은 값을 찾거나 추가하거나 제거하는 데 빠르다.(배열과 달리)
  • 해시 테이블은 이처럼 속도가 빠르기 때문에 자주 사용되며, 대부분의 프로그래밍 언어에서는 다음과 같이 해시 자료 구조를 갖고 있다. 이들은 모두 key-value 쌍 데이터를 저장하고 해시 테이블을 사용한다.
    • ex) 정보 보호, 저장, 사이트 로그인 인증, 암호화폐 등
    • Python: Dictionary
    • Javascript :Map, Object(객체에서는 key로 문자열만 사용 가능하다)
    • Java, Go, Scala : Map
    • Ruby : Hash

해시 함수 구현

  • key를 갖고 value를 찾으려고 하면, key를 배열의 유효한 인덱스로 변환하는 방법이 필요하다. 이러한 기능을 하는 함수를 해시 함수(Hash fucntion) 라고 부른다.
  • key를 해시 함수에 입력하면, key들은 각각 항상 같은 인덱스(숫자)들로 변환돼야 한다.(=결정론적)
  • 하지만 반대로는 변환이 불가하다. 즉, 해시된 인덱스를 key로 변환할 수는 없다. 해시 함수는 단방향 함수이다.
  • 좋은 해시 함수의 조건 (보안 목적은 고려하지 않음)
    1. 속도가 빨라야 한다.(ex, O(1))
    2. 일관된 방식으로 분배하여 다른것과 겹치지 않게 골고루 분배돼야 한다.
    3. 결정론적이다(=특정 입력값을 입력할 때마다 같은 출력값이 나와야 한다).
  • 문자열에서 작동하는 해시 함수 구현
    • "a".charCodeAt(0) - 96
    • Stirng.prototpye.charCodeAt(인덱스) 는 주어진 인덱스에 대한 UTF-16 코드를 반환한다. 알파벳 A의 UTF-16 코드는 97부터 시작되므로, "a".charCodeAt(0) - 96 는 1을 의미한다. 이를 이용해서 아래와 같은 해시 함수를 만든다.
// key에 있는 글자들에 대해 아래와 같은 루프를 돌린다.
// 각각의 글자에 대한 코드값(value)과 total 더하고, 이를 배열 길이로 나눈 나머지를 total에 저장한다.
function hash(key,arrLen){
    let total = 0;
    for(let item of key){
        let value = item.charCodeAt(0) - 96;
        total = (total + value) % arrLen;
    }
    return total;
}
  • 문제점
    1. 오직 문자열에 대해서만 해시할 수 있다.
    2. 함수 실행에 걸리는 시간이 O(1)이 아니다. key의 길이만큼 O(N)의 시간이 소요된다.
    3. 무작위성이 떨어지고, 해시된 인덱스가 충돌할 수 있다.

해시 함수 문제점 개선

속도를 빠르게 해보자!

  • 예를 들어, 해시하려는 key 문자열이 수백만 글자라고 하면, for문을 수백만번 돌려야 한다. 이러한 비효율을 방지하기 위해, for문의 반복횟수인 key.length을 Math.min(key.length, 100)으로 수정하여 수 백만 번의 루프 대신 앞 글자 100개에 대해서만 루프를 돌리도록 지정한다. 이를 통해 거의 O(1)의 시간복잡도를 갖게 됐다.
  • 예외) 어떤 데이터 key들은 언제나 맨 앞의 100 글자가 같고 나머지 글자들이 다른 경우가 있다면, 알고리즘을 약간 바꿔서 맨 뒤에서 시작한다거나 약간의 조정이 필요하다.

해시된 인덱스의 충돌을 줄이자!

  • 충돌의 횟수를 줄이고 데이터가 더 퍼지고 무작위성을 가지도록 하기 위해 소수를 추가한다. 소수를 추가하는 데에는 수학적인 이유가 있으나 복잡하므로 넘어간다.
  • 테이블 저장하는 배열의 길이가 소수이면, 충돌이 일어날 확률이 더 적어지기 때문에 해시 함수 코드 내에 소수를 추가한다.
  • 일반적으로 추가하는 소수가 더 클수록 충돌이 일어날 확률이 적어진다.
  • 개선 코드
function hash(key,arrLen){
    let total = 0;
    let WEIRD_PRIME = 31; //소수값이용하기위해 소수지정
  	//루프를 최대 백번으로 고정
    for(let i=0; i<Math.min(100,key.length); i++){
        let value = key[i].charCodeAt(0) - 96;
      	//소수를 곱해서 결과 값을 낸다.
        total = (total * WEIRD_PRIME + value) % arrLen;
    }
    return total;
}

해시 함수 충돌을 개선하는 방법

  1. 개별 체이닝(Separte Chaining)
  2. 직선 탐색법(Linear Probing)
  • 해시 함수를 사용할 때, 데이터가 아주 많이 있는 경우라면 충돌이 어느 정도 일어날 가능성이 높다. 또는 데이터 저장 공간이 아주 크고 해시 함수가 아주 좋은 것일지라도 여전히 충돌은 발생할 확률이 있다.

방법 1. 개별 체이닝(Separte Chaining)

  • 개별 체이닝은 같은 장소에 여러 데이터를 저장할 때 배열이나 연결 리스트 등과 같은 것을 활용하여 중첩 데이터 구조를 쓰는 것이다. 즉, 충돌하는 데이터를 같은 인덱스에 중첩해서 저장하는 것이며, 배열을 쓰면 아래 이미지와 같이 중첩 배열 구조가 나오게 된다.
  • 개별 체이닝을 사용하면, 테이블의 길이보다 더 많은 데이터를 저장할 수 있다.

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

  • 선형 탐색법은 각 위치에 하나의 데이터만 저장한다는 규칙을 그대로 살려서 지킨다. 다만, 충돌이 발생하면 다음 빈 인덱스가 어디인지 확인하고 빈 인덱스 공간에 저장한다.
  • 선형 탐색법은 최대 테이블의 길이만큼만 저장할 수 있다.

해쉬 테이블 구현

  • 개별 체이닝을 활용한 Set, Get 메소드를 만들고 해쉬 테이블을 구현해보자!

기본구조

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

    hash(key){
        let total = 0;
        let WEIRD_PRIME = 31; //소수값이용하기위해 소수지정
        for(let i=0; i<Math.min(100,key.length); i++){
            let value = key[i].charCodeAt(0) - 96;
            total = (total * WEIRD_PRIME + value) % this.keyMap.length;
        }
        return total;
    }

set 메서드와 get 메서드

//입력된 key를 해시하여 인덱스를 구한다.
    set(key,value){
        var index = this.hash(key);
      	//충돌된 요소가 없으면 해당 인덱스에 빈배열을 할당
        if(!this.keyMap[index]){
            this.keyMap[index] = [];
        }
      	//해당 인덱스에 [키,값]을 배열로 푸쉬함
        this.keyMap[index].push([key,value]);
        return index;
    }
	//해당 키의 값을 얻는 메소드
    get(key){
        var 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; //아무것도 없을 때
    }

values 와 keys 메서드

  • values 메서드는 테이블에 있는 모든 value들의 목록을 반환한다.
  • keys 메서드는 테이블에 있는 모든 key들의 목록(중복되는 것은 한 개씩)을 반환한다.
  • keys와 values는 로직은 비슷하나 push 해주는 값만 this.keyMap[i][j][1],this.keyMap[i][j][0]으로 다르다.
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++){
                  	//valuesArr에 값이 있지 않으면 그 value를 push -> 중복제거
                    if(!valuesArr.includes(this.keyMap[i][j][1])){
                        valuesArr.push(this.keyMap[i][j][1]);
                    }
                }
            }
        }
        return valuesArr;
    }

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

해시 테이블 성능

  • 시간복잡도(평균)
    • 삽입 : O(1)
    • 삭제 : O(1)
    • 접근 : O(1)
  • 이러한 시간복잡도는 실제로 해시 함수의 성능에 달려 있다. 해시 함수가 얼마나 빠른지, 그리고 얼마나 고르게 데이터를 분배해서 충돌의 확률을 줄이는지 말이다. 따라서 좋은 해시 함수를 사용하여 성능을 높이기 위해서는, 직접 만든 해시 함수를 사용하기보다는 유명한 코드나 라이브러리들을 활용하자.
profile
정태호
주니어 프론트엔드 개발자가 되고 싶습니다!
이전 포스트

(JS 알고리즘) 이진 힙(Binary Heap)과 우선순위 큐(Priority Queue)

다음 포스트

(JS 자료구조) 그래프(Graph)

0개의 댓글