해쉬 테이블은 키-값 쌍을 저장하는데 사용하는 알고리즘으로, 값을 찾거나 (탐색), 추가하거나 (삽입), 제거하는 처리 속도가 굉장히 빠르다는 특징이 있다. 순서가 있고 연속적인 데이터라면 배열을, 그 밖의 경우 해쉬 테이블(딕셔너리, 객체 등)을 사용하면 된다.
굉장히 빈번히 사용되는 알고리즘으로 많은 프로그래밍 언어들에 해당 기능이 자체적으로 내장되어 있지만, 본 섹션에서는 해쉬 테이블의 알고리즘 구조를 이해하고 직접 구현해보고자 한다.
해쉬 함수
입력받은 키에 따라 무작위 인덱스를 부여하고, 배열에 넣어 데이터를 관리해주는 단방향 함수를 말한다. 이를 통해 String 형태로 이루어진 키를 이용해 원하는 값을 찾을 수 있게 된다.
좋은 함수를 만드는 기준
- 탐색, 삽입, 제거 등의 데이터 처리 속도가 빠를 것
- 일관적인 데이터 분배를 통해 인덱스가 중복되는 데이터가 없게 할 것
- 특정 입력값에 따른 출력값이 항상 일정할 것 (결정론)
의사코드
- Key 정보가 될 문자열과 해쉬 테이블을 저장할 배열의 길이를 입력으로 받는다.
- 해당 문자열은 입력한 배열의 길이보다 작은 무작위 인덱스를 반환받게 된다.
해쉬 함수 구현
입력받은 문자열에 대해 어떻게 항상 일정한 출력값을 반환할까? 먼저 각 알파벳을 UTF-16 형태로 변환하여 고유 정수값을 갖게 하고, 전부 더해주는 방식을 이용해보았다. 더하기만 한 상태에서는 값이 너무 커질 수 있으므로, 배열의 길이와 나머지 연산을 통해 해당 결과를 반환하게 해주었다. 이를 통해 어느 경우에나 배열의 길이보다 작은 인덱스를 반환할 수 있게 된다.
function hash(key, length) {
let total = 0;
for (let char of key) {
let value = char.charCodeAt(0) - 96;
total = (total + value) % length;
}
}의사코드와 채택한 방법론을 기반으로 작성한 코드이다. 그러나 본 코드에서는 몇 가지 문제가 존재한다.
첫 번째로 오직 문자열 형태의 파라미터만 입력받을 수 있다. 숫자나 불린, 배열 형태의 Key 입력에도 작동하는 코드가 필요하다.
두 번째로 일정한 처리 시간을 갖는 것이 아닌, 입력값의 길이에 따라 달라진다.
세 번째로 무작위성이 떨어져 데이터가 같은 인덱스로 쉽게 뭉친다.
해쉬 함수 개선
처리 시간이 상수 값의 시간에 가까워지는 것(1) 과 인덱스 중복을 피하는 것(2) 에 초점을 두고 구현할 계획이다.
(1)의 해결책으로, 루프문에 최대 횟수 제한을 걸어줄 수 있다. 가령 문자열의 길이가 100 이하라면 모든 문자열의 코드를 계산해 결과를 반환하고, 100을 넘어간다면 맨 앞의 100자만 계산하여 반환한다. Numpy에서의 Clip과 유사한 개념.
(2)의 해결책으로는 반환할 인덱스 결과에 소수 연산을 추가하는 것이다. 실제로 해쉬 연산에는 소수를 이용하는데, 충돌을 줄이고 데이터를 빠르게 회수하기 위함이다.
function newHash(key, length) {
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) % length;
}
return total;
}
제시한 해결책을 바탕으로 작성한 코드이다. 이전의 해쉬 함수보단 훨씬 낫지만, 이마저도 데이터 충돌에 대해 완전히 자유롭지는 않다.
충돌 처리
1. 개별 체이닝 (Separate Chaining)
같은 장소에 여러 데이터를 저장할 때, 배열이나 연결 리스트 등과 같은 것을 활용하여 이중 데이터 구조를 사용하는 방법론을 말한다. 사용과 구현은 쉽지만, 이중 배열 구조 사용으로 연산 효율이 떨어질 수 있다.
2. 직선 탐색법 (Linear Probing)
각 인덱스에 하나의 데이터만 저장한다는 규칙을 지키며, 충돌 발생 시 빈 인덱스를 찾아 데이터를 넣는다.
해쉬 테이블
클래스 셋업
class HashTable {
constructor(size = 53) {
this.keyMap = new Array(size);
}
_hash(key, length) {
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 / Get 메서드
Set : 입력받은 키를 해쉬 처리, 반환받은 인덱스 결과에 따라 배열에 삽입. 단 개별 체이닝을 사용해 충돌을 처리할 것이기 때문에 빈 인덱스라면 새로운 배열을 생성해 첫 번째 원소로 들어가고, 기존에 배열이 존재했다면 Push
set(key, val) {
let index = this._hash(key);
if (!this.keyMap[index]) {
this.keyMap[index] = [];
}
this.keyMap[index].push([key, val]);
}
Get : 입력받은 키를 해쉬 처리, 반환받은 인덱스 해쉬 맵에 접근하여 값을 읽어 옴. 개별 체이닝 방식이기 때문에, 해당 인덱스에 존재하는 배열을 순회하여 일치하는 키의 값을 반환
get(key) {
let 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;
}
Keys / Values 메서드
Keys : 테이블에 있는 모든 키를 포함한 목록을 출력
Values : 테이블에 있는 모든 값을 포함한 목록을 출력
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;
}
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++) {
if (!valuesArr.includes(this.keyMap[i][j][1])) {
valuesArr.push(this.keyMap[i][j][1]);
}
}
}
}
return valuesArr;
}비교하고 출력하는 배열의 차원만 바꿔주면 된다.
해쉬 테이블의 빅오 복잡도
일반적인 경우 삽입, 제거, 탐색에 상수 값의 시간 복잡도 O(1)를 갖는다. 훌륭한 성능이다. 또한 해쉬 함수의 성능이 해쉬 테이블 연산 복잡도에 큰 영향을 미치는 것을 알 수 있었고, 데이터를 균일하게 분포시키는 것 또한 중요하다는 것을 알 수 있었다. 국내외 연구팀에서 지금까지도 해쉬 테이블에 대한 연구를 진행 중에 있다고 하니, 그냥 내장 메서드를 사용하자.
