해시 테이블은 (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://mangkyu.tistory.com/102
https://medium.com/@clgh0331/javascript-node-js-hash-table%EC%9D%84-%EA%B5%AC%ED%98%84-f1442b24571c
저도 첫번째 주에 HashMap 쓰면서 해싱에 대해서 간략하게 알아봤는데 덕분에 리마인드하고 갑니다!