해시 테이블

Goody·2021년 1월 24일
0

CS

목록 보기
1/1

해시 테이블은 (Key, Value)로 데이터를 저장하는 자료구조 중 하나이다.

자료 검색에 O(1) 의 시간복잡도를 가지고 있다는 장점이 있다.



배열의 비효율성

우리에게 익숙한 배열을 떠올려보자.

배열내에서 원하는 값을 찾아가는 과정은 다음과 같다.

// 배열 내 3이라는 값을 찾고 싶다면?
const arr = [1,2,3,4,5]

for(let i = 0; i < arr.length; i++) {
    if(arr[i] === 3) {
        return arr[i];	// 3
    }
}

원하는 값을 찾는 시간이 배열의 크기만큼 걸린다. => O(N) 의 시간복잡도를 갖는다.



해시 테이블의 핵심, 해싱

해시 테이블을 구현하기 위해서는 해싱 이 꼭 필요하다.

해싱이 뭔지는 직접 구현해보면서 알아보자.

A = 1
B = 2
C = 3
D = 4
E = 5
...

위 코드에 따르면 ACE 는 135가 된다.

우리가 만약 "ACE" => "BED" 라는 key와 value를 갖고 싶다면,

위 코드에 따라 ACE를 숫자 135로 변환하고, 빈 배열의 135번 째 인덱스에 "BED" 라는 값을 저장하면 된다.

const arr = [...X134, "BED" ];

이처럼 문자를 가져와 숫자로 변환하고, 이를 인덱스로 쓰는 것이 해싱이다.

배열 내에서 다시 BED 라는 값을 찾고 싶을 때는 다시 ACE를 해싱한 135 를 입력하면 된다.

arr[135] === "BED"

이처럼 해시 테이블은 배열의 크기와 상관없이 O(1)의 시간복잡도를 갖는다.



배열이 작아도 괜찮아

위 해싱은 한 가지 문제점이 있다.

일단 ACE 를 135로 해싱은 해놨는데, 준비한 배열이 10칸밖에 되지 않을 수도 있기 때문이다.

그렇다고 배열을 무조건 큰 사이즈로 준비해놓을 수도 없다.

즉, 우리의 목표는 어떤 문자열이든 준비한 배열의 크기보다 작은 숫자로 변신하게 하는 것이다.

많이 쓰이는 방법은 아래와 같다.

let storage = [];
storage.length = 10;
function hash (key) {
        let hash = 0;

        if (typeof key === "number") {
            key += "";
        } else {
            [...key].forEach((e) => {
                hash += e.charCodeAt(0);
            });
        }
        return hash % storage.length;	// 해싱된 숫자를 배열의 크기로 나눈 나머지를 구했다.
    }
  • 입력받은 문자열을 한 글자씩 숫자로 바꿨다.
  • 바뀐 숫자들을 모두 더했다.
  • 더해진 숫자들을 배열의 크기만큼 나누고 남은 나머지를 반환한다.

배열의 크기만큼 나눈 나머지를 인덱스로 사용하므로, 인덱스가 배열의 크기보다 커질 일은 절대 없다.



충돌 해결

위 해싱을 거쳐서 배열에 다음과 같이 값들이 저장되었다고 해보자.

storage = [["ACE","Bed"],["SIDIZ","chair"],["IKEA","desk"],...]

그런데 만약 해싱의 결과가 0인 다른 값을 저장해야 할 때는 어떻게 해야 할까?

(storage의 크기가 10이니, 10으로 나눴을때 나머지가 0이 되는 수는 정말 많기 때문에 꽤나 흔한 일이다.)

여기에는 꽤나 다양한 해결방법이 있는데, 나는 배열 내부를 또 배열로 쪼개는 방법을 선택했다.

storage = [[["ACE","Bed"],["AEC","Angry"]],["SIDIZ","chair"],["IKEA","desk"],...]

storage[0]의 [0] 에는 ["ACE", "Bed"] 가, storage[0]의 [1] 에는 ["AEC", "Angry"] 가 저장되어 있다.

이렇게 하면 같은 해싱 값(0)이 나오더라도, storage[0] 에다가 계속해서 push 해주면 된다.

위 방법은 해싱 함수가 최대한 다양한 값을 뽑아낼 수 있게끔 설계해야 효과가 있다.

어떤 문자열이든 해싱 결과가 0이라면, 그 해시 테이블은 일반 배열과 다를 바가 없어지기 때문이다.



해시 테이블 구현

class HashTable {

    constructor(size) {
        this.storage = [];
        this.size = size;
    }


    hash = function (key) {
        let hash = 0;

        if (typeof key === "number") {
            key += "";
        } else {
            [...key].forEach((e) => {
                hash += e.charCodeAt(0);
            });
        }
        return hash % this.size;
    }

    insert = function (key, value) {
        const index = this.hash(key);

        if (!this.storage[index]) {
            this.storage[index] = [[key, value]];
        } else {
            this.storage[index].push([key, value]);
        }
    }

    search = function (key) {
        const index = this.hash(key);
        let value;

        this.storage[index].forEach(function(e) {
            if(e[0] === key) return value = e[1];
        });
        return value;
    }

    delete = function (key) {
        const index = this.hash(key);

        for(let i = 0; i < this.storage[index].length; i++){
            if(this.storage[index][i][0] === key) {
                this.storage[index].splice(i,1);
            }
        }
    }
}

자료의 삽입, 검색, 삭제가 모두 가능한 해시 테이블 자료구조를 구현했다.



해시 테이블로 풀어본 알고리즘 문제

https://velog.io/@goody/PR-%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80-%EB%AA%BB%ED%95%9C-%EC%84%A0%EC%88%98



REFERENCE

누구나 자료 구조와 알고리즘 (제이 웬그로우 저)

https://mangkyu.tistory.com/102

https://medium.com/@clgh0331/javascript-node-js-hash-table%EC%9D%84-%EA%B5%AC%ED%98%84-f1442b24571c

1개의 댓글

comment-user-thumbnail
2021년 1월 24일

저도 첫번째 주에 HashMap 쓰면서 해싱에 대해서 간략하게 알아봤는데 덕분에 리마인드하고 갑니다!

답글 달기