해시 테이블 - 빠른 검색

이번 포스트에서는 해시 테이블에 대하여 알아보겠습니다.
개발을 하면서 효율성을 고려한다면 필수적이라 할 수 있을 정도로 해시테이블은 매우 빠른 자료구조인데요.
그만큼 사용할 수 있는 케이스 또한 다양합니다.
그럼 지금부터 해시테이블에 대해서 알아보겠습니다.

 

---

1. 해시 테이블 ( Hash Table )이란?

 대부분의 프로그래밍 언어들은 해시 테이블 자료구조를 구현하고 있으며 각각 해시, 맵, 해시맵, 딕셔너리, 연관 배열 등의 여러 가지 이름으로 불리고 있습니다.

 해시 테이블은 Key - Value  쌍으로 이루어진 자료 구조로 선언은 다음과 같이 합니다.

const hashTable = { "abc" : 123, "def" : 456 };

 

또한 아래의 형태로 자료구조 내의 데이터에 접근할 수 있습니다.

hashTable["abc"]

 

위와 같은 접근 방식의 시간 복잡도는 ( 평균적으로 ) 단 $ O(1) $입니다. 

놀랍지 않나요? 

이렇게 빠른 접근이 가능한 이유는 무엇일까요?

---

 

2. 해시 함수

 모두들 어렸을 때 이성친구와 비밀편지를 주고받아본 경험이 있으실 겁니다. ( 저는 없습니다. )

편지의 안에는 여러 기호나 문자들을 의미 있는 글자와 매칭시켜 둘만의 비밀스러운 이야기를 담았습니다. ( 전해 들었습니다. )

A = 1 , B = 2, C = 3.....

이와 같이 서로 약속하고

ABC = 123

이런 식으로 문장을 수로 바꾸어 표현할 수 있습니다.

 

이러한 과정을 해싱 ( Hashing )이라고 합니다. 또 글자를 특정 숫자로 변환하는 데 사용하는 함수를 해시 함수라고 부릅니다. 예시에서의 해시 함수는 단순히 수를 나열하였지만 동일한 문자열에 대해서 동일한 수가 나오는 어떤 변환 함수던 해시 함수가 될 수 있습니다.

 

---

 

3. 해시 테이블의 저장 & 탐색

 앞에서 언급한 내용을 숙지하였다면 저장은 쉽게 끝낼 수 있습니다.

준비한 해시 함수를 통해 주어진 키를 해싱합니다. 준비한 배열에 키를 해싱한 값을 인덱스로 하여 데이터를 저장만 하면 저장이 완료됩니다.

저장해 놓은 값을 찾고자 한다면 기억해 놓은 키를 해싱하면 저장되어 있는 데이터의 위치에 한 번에 접근할 수 있습니다.

주의해야 할 사항은 데이터를 알고 있다 하더라도 키는 위와 같은 방식으로 구할 수 없습니다.

배열 전체를 순회하여야 하기 때문에 $ O(N) $ 의 시간 비용이 듭니다.

 

---

 

4. 충돌 문제

 이처럼 뛰어난 자료구조인 해시 테이블에도 결점이 존재합니다.

각기 다른 키에 대한 해싱 결과가 같은 수 ( 인덱스 )가 나올 수 있다는 것입니다. 이러한 현상을 충돌이라고 정의했습니다.

이러한 문제를 해결하기 위해 여러 가지 방법이 고안되었습니다.

고전적인 방법으로는 분리연결법이 존재합니다.

분리연결법은 충돌이 발생하면 셀 하나에 하나의 값만을 넣는 것이 아닌 배열로의 참조를 넣습니다. 탐색 시 키를 해싱한 후 셀로 이동하고 만일 참고하는 값이 배열이라면 데이터를 찾기 위해 선형 탐색을 합니다.

 

 

---

 

5. 해시 테이블의 효율성을 결정하는 요인

• 얼마나 많은 데이터를 저장하는가
• 얼마나 많은 셀을 사용할 수 있는가
• 어떠한 해시 함수를 사용하는가

데이터와 셀의 개수는 충돌 발생 횟수에 영향을 끼칩니다. 충돌이 적게 발생할수록 데이터를 찾는 시간을 줄어들겠죠?

그러면 해시 함수는 어떻게 효율성에 영향을 끼치는 것일까요?

 해시테이블에서는 데이터 간의 밀집도가 낮을수록 충돌이 줄어들게 됩니다. 때문에 데이터를 넓게 퍼뜨려 충돌이 줄어들게 하는 함수가 좋은 해시 함수입니다.

하지만 데이터 간 밀집도를 낮추기 위해 지나치게 크게 선언된 자료 구조는 메모리의 낭비를 가져오게 됩니다.

좋은 해시 테이블은 많은 메모리를 낭비하지 않으면서 충돌을 피할 수 있어야 합니다.

컴퓨터 과학자들은 좋은 해시 테이블을 구분 짓기 위해  부하율 ( Load factor )라는 것을 정의하였습니다.

부하율은 데이터 - 셀 간의 비율이며  원소의 개수 / 셀의 개수로 구할 수 있습니다.

이상적인 부하율은 0.7 정도로 보고 있습니다.

 

---

 

6. 해시 테이블의 구현

// 해시 테이블의 길이
const HASH_SIZE = 1000
// 셀 내의 배열의 길이
const HASH_LENGTH = 400;
// 해시 계산용 
const HASH_VAL = 17 // 17, 19, 23 나누어 지지 않는 소수가 바람직

// 임의의 해시 함수
function getHashKey(str) {
    const groupOfChars = [...str];
    let key = 0;
    for (let i = 0; i < groupOfChars.length; i++) {
        key = (key * HASH_VAL) + str.charCodeAt(i);
    }
    if (key < 0) key = -key;
    return key % HASH_SIZE;
}


const hashtable = Array.from({
    length: HASH_SIZE
}, () => Array.from({
    length: HASH_LENGTH
}, () => []));

// 각 인덱스에 있는 셀의 길이 저장 배열
const length = Array.from({
    length: HASH_SIZE
}, () => 0);

// 해시 테이블의 셀에 값이 존재하는 지 확인 및 저장
function checking(target, key) {
    const len = length[key]
    console.log(len)
    if (len !== 0) {
        for (let index = 0; index < len; index++) {
            const data = hashtable[key][index]
            if (data === target) {
                return ++length[key];
            }
        }
    }
    hashtable[key][len] = target
    length[key] += 1;
    return -1;
}

---

7. 해시 테이블의 사용 예

• 조건부 로직의 간소화
• 객체의 표현
• 빠른 접근을 위한 배열
• 배열의 부분 집합 확인 로직

---

마치며

 사실 개발을 하면서 자료구조를 직접 구현해 볼 기회가 없었습니다.
이미 최고의 효율성으로 구현되어 있다고 생각했기 때문에 별 고민 없이 그때그때 손이 가는 것으로 사용했습니다.
하지만 자료구조를 공부를 하며 해당 자료구조가 어떠한 특징을 가지고 있고 어떠한 상황에서 써야 하는지 알게 되면서 과거의 자신을 돌아보게 됐습니다.
점점 더 좋은 개발자가 되어가는 것 같습니다.