알고리즘

[알고리즘] 해시 알고리즘 (javascript)

뜐🐸 2025. 2. 3. 21:29

자바스크립트의 경우 Object나 Map을 사용해서 해시 테이블을 구현할 수 있다.

  • Object: 키로 string만 사용할 수 있다.
  • Map: 다양한 데이터 타입을 키로 사용할 수 있으며, 삽입 순서를 유지하는 장점을 갖는다.
    하지만 내부적으로 어떻게 동작하는지 이해하기 위해, Object나 Map을 사용하지 않고 직접 해시 테이블과 해시 함수를 구현해보려고 한다.

해시 알고리즘의 처리 방식

해시 테이블은 키(Key)와 값(Value) 형태의 데이터 구조이다.
이때 키는 해시 함수를 통해 '고유한 해시값' 으로 변환된다. 변환된 해시 값은 해시 테이블에서 {key: value} 쌍이 저장될 위치인 해시 인덱스가 된다.

해시 알고리즘을 사용하면 효율적인 검색과 데이터 저장을 할 수 있다. 하지만 충돌이 발생할 가능성이 있기 때문에 이를 해결해야 한다.

키(Key)

키는 문자열 혹은 정수 형태로 구성이 되며, 저장된 데이터를 빠르게 찾기 위해 사용되는 고유 식별자이다. 키는 해시 함수에 전달되어 처리되며, 이를 통해 특정 위치에 값을 저장하거나 검색할 수 있다.

해시 테이블

해시 테이블은 키-값 쌍을 저장하는 자료구조로, 이 때 해시 테이블의 키는 순서를 갖지 않는다. 앞에서 말한대로, 해시 함수를 통해 '고유한 해시값' 을 계산하여 '해시 인덱스' 로 결정하고, 해당 인덱스에 값을 저장한다.

해시 함수

해시 함수는 문자열 또는 숫자로 된 키를 배열에서 사용되는 유효한 인덱스, 작은 숫자로 바꿔주는데 사용된다.

좋은 해시 함수의 조건

좋은 해시 함수를 만들기 위해서는, 아래와 같은 조건을 만족하도록 구현해야 한다.

  1. 빠른 연산 속도: 해시 함수는 O(1) 시간 복잡도로 동작해야 한다.
  2. 균등한 분배: 키를 해시 테이블의 모든 인덱스에 균일하게 분배해야 충돌을 줄일 수 있다.
  3. 결정론적 특성: 같은 입력 값에 대해 항상 같은 해시 값을 반환해야 한다.

해시 함수 작성하기 - (비효율적)

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

위의 코드는 아래의 문제점을 갖는다.

  • 문자열만 입력 가능 (숫자, 특수 문자 지원 X).
  • 해시 충돌 가능성이 높음 (비슷한 문자열이 동일한 해시 값을 가질 가능성이 높음)
  • 입력 길이에 따라 성능이 달라짐 (긴 문자열일수록 연산량 증가)

해시 함수 개선하기

해시 함수의 성능을 개선하기 위해 소수와 곱셈 연산을 사용한다.

function hash(key, arrayLen) {
    let total = 0;
    let WEIRD_PRIME = 31; // 해시 함수는 거의 대부분 소수를 이용한다-> 소수를 사용하면 충돌 가능성이 줄어듦

    for (let i = 0; i < Math.min(key.length, 100); i++) { //최대 100자까지만 처리
        let char = key[i];
        let value = char.charCodeAt(0) - 96;
        total = (total * WEIRD_PRIME + value) % arrayLen;
    }
    return total;
}
  • 소수(31)를 활용하여 충돌 최소화: 소수를 사용하면 해시 값이 더 균등하게 분포된다.
  • 문자열 길이 제한: 100자 이상 넘어가는 문자열은 해싱 과정에서 일부만 고려하도록 제한하여 성능을 최적화했다.
  • 곱셈을 활용한 해시 계산: 단순 덧셈이 아닌 곱셈을 추가하여 키의 순서를 더 강하게 반영.

해시 충돌 해결 방법

해시 테이블에서는 서로 다른 키가 동일한 해시 값을 가지는 충돌(Collision) 문제가 발생할 수 있다. 이를 해결하는 방법은 여러 개가 있지만, 이중 개별 체이닝과 선형 탐색법에 대해서만 알아보자.

개별 체이닝

  • 배열, 연결 리스트등을 사용하여 이중 데이터 구조를 쓰는 방법이다.
  • 즉 공동 저장 방식이다.
  • 충돌이 발생해도 동일한 인덱스에 추가 데이터를 저장할 수 있다.

직선 탐색법

  • 각 위치에 하나의 데이터만 저장한다는 규칙을 지키는 방식이다.
  • 충돌이 발생하면 다음 빈칸을 찾아 저장한다.
  • 해시 테이블이 꽉 차면 성능이 저하될 수 있다.

해시 테이블 클래스 만들기

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) {
        const index = this._hash(key);
        if (!this.keyMap[index]) {
            this.keyMap[index] = [];
        }
        this.keyMap[index].push([key, value]);
    }

    get(key) {
        const index = this._hash(key);
        const bucket = this.keyMap[index];
        if (bucket) {
            for (let [storedKey, storedValue] of bucket) {
                if (storedKey === key) {
                    return storedValue;
                }
            }
        }
        return undefined;
    }
}