[Javascript] 해시테이블

이번에 소개드릴 자료구조는 해시테이블입니다. 그동안 배운 자료구조들에서 탐색이 유용하게 쓰였었는데, 이 해시테이블은 탐색을 잘 할 수 있는 자료구조입니다. 

---

1. 테이블과 해시함수 그리고 해시테이블

우선 테이블(Table)은 key와 value가 한 쌍을 갖고 표에 저장된 자료구조입니다. 단순히 표에 저장했다고 해서 테이블 자료구조가 아니라, key와 value가 쌍을 이루고 저장되어야합니다. 근데 key와 value라고하니 자바스크립트에서 떠오르는 한 가지 구조가 있습니다. 바로 key와 value 쌍을 이룬 연관(혹은 연상) 배열 map이었습니다. 그리고 우리는 이 연관 배열을 해시라고도 한다고 했었습니다. 혹은 집합과 유사한 Set도 해시테이블의 일종이라고 할 수 있습니다.

2021.03.15 - [Programming/Javascript] - [Javascript] 내장 객체 - Map 과 연관 배열

2021.03.15 - [Programming/Javascript] - [Javascript] 내장 객체 - Set

 

해시(Hash)는 '해시함수'라고 하는 함수를 이용해서 입력값을 고정길이 문자열로 치환하는 것을 말합니다. 즉, 키를 해시함수에 넣으면 해시값이라고 하는 암호화된 데이터가 반환되게 됩니다. 하지만 이 암호환된 데이터를 보안을 위해 사용한다기보다는 보통 어느정도 긴 key를 짧은 2~3길이(당연히 2~3은 예시고 해시함수나 구현 방식에 따라 고정길이가 다릅니다.)를 갖는 문자열로 바꿔 탐색을 편리하게 해주는 용도로 사용하게 됩니다.

테이블과 해시에 대한 소개는 여기까지 하고 이제 해시테이블에 대해서 알아보도록 하겠습니다. 해시테이블은 key와 value쌍으로 데이터를 저장합니다. 다만 다른점은 저장할 때 key를 해시함수에 input해서 임의의 해싱된 주솟값을 받습니다. 그리고 그 주솟값에 key와 value를 저장하게 됩니다. 이것이 해시 테이블입니다. 이렇게 하면 좋은점은 key가 매우 긴 문자열이나 숫자 등을 가질경우 key를 비교하는 과정에서 많은 시간이 소모되는 것을 고정길이 주솟값으로 변환해 주기때문에, 빠른 검색을 보장합니다.

 

 

 

2. 해시 충돌 Hash collision

해시 함수는 고정길이 문자열을 반환합니다. 그렇다보니 길이가 다른 key를 넣어도 같은 길이의 문자열이 반환됩니다. 이말인 즉슨 key를 저장할 수 있는 공간이 한정적이라면 다른 key를 넣어도 같은 문자열을 반환할 수 있다는 것 입니다. 이렇게되면 같은 곳에 덮어씌우는 일이 발생할 수 있고 우리는 이를 가리켜 해시 충돌이라고 부릅니다.

만약 사람이름을 key로 하여 저장하는데 이때 성씨를 기준으로 해싱한다고 가정합니다. Lee k라는 사람과 Lee t라는 사람이 있는데 이 사람들을 해시 함수에 넣으면 똑같은 'L'이 반환됩니다. 이렇게 저장해 버린다면 먼저 들어온 데이터는 덮어 씌워짐으로써 유실될 가능성이 높습니다. 이런 상황을 충돌이라고 볼 수 있습니다.

우리는 해시 충돌을 반드시 해결해야하는데, 지금은 해시 충돌이 어떤 것이다만 알아두고 해시 충돌의 해결법은 다음 포스트로 나누어서 따로 구현해보겠습니다.

 

 

3. 해시 테이블 구현

class HashTable {
    constructor(size) {
        this.size = size;
        this.table = [];
    }

    //해시함수
    hash(key) {
        let id = 0;

        for (let i = 0; i < key.length; i++) {
            id += key.charCodeAt(1) * 100;
        }
        return id % this.size;
    }
    
    //삽입
    insert(key, value) {
        const id = this.hash(key);

        this.table[id] = value;
    }

    //검색
    search(key) {
        const id = this.hash(key);
        const value = this.table[id];

        if (value) {
            return value;
        }
        else {
            return console.log('검색 실패');
        }
    }
}

 

 

이 해시 함수는 입력받은 키를 ASCII 코드에 100을 곱한 값을 테이블 크기로 나머지 연산해서 나온 값을 id로 쓰고 있습니다. 해시 함수 자체는 해시 테이블 구현 실습에서 크게 중요한 부분은 아니니 편한대로 만들어서 사용하시면 됩니다.

hash(key) {
        let id = 0;

        for (let i = 0; i < key.length; i++) {
            id += key.charCodeAt(1) * 100;
        }
        return id % this.size;
    }

 

삽입과 삭제연산입니다. 삽입은 key를 해시함수에 통과시켜 나온 id값을 토대로 해시 테이블에 value를 저장하는 간단한 구조입니다.

탐색도 마찬가지로 key를 해시함수에 통과시켜 나온 id를 토대로 value를 해시 테이블에서 찾아내어 반환합니다.

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

        this.table[id] = value;
    }

    search(key) {
        const id = this.hash(key);
        const value = this.table[id];

        if (value) {
            return value;
        }
        else {
            return console.log('검색 실패');
        }
    }

---

https://github.com/Bam-j/algorithm-study/blob/main/study-code/data-structure/HashTable.js

GitHub - Bam-j/algorithm-study: 블로그 알고리즘 정리 포스트 코드 수록 + 코딩 테스트 코드 수록