JavaScriot로 hash table을 구현해보자.
연관배열 구조(associative array)
hash table을 보기전에 연관배열 구조에 대해 알아야 한다. 연관배열 구조는 간단하게 키 1개와 값 1개가 1:1로 연관되어 있는 구조를 말한다.
해시 테이븢ㄹ은 연관배열 구조를 이용해 키에 값을 저장하는 자료구조이다. 좀 더 자세하게 설명하면 키는 해시함수를 통해 해시로 변경되며 해시는 값과 매칭되어 저장소에 저장이 된다.
해시 테이블은 저장, 삭제 , 검색에서 평균적으로 O(1)의 시간 복잡도를 갖고있다. 이러한 우수한 효율성을 장점으로 갖는 반면, 해시를 이용한 자료구조 방식은 필연적으로 갖는 문제가 있는데, 무한한 값(key)을 유한한 값(hash)로 표현하면서 서로 다른 두개 이상의 유한한 값이 동일한 출력값을 가지게 된다는 것이다. 이를 hash collision(해시 충돌)이라 한다.
이 해시 충돌을 해결하는 방법은 여러가지가 있지만, 여기서는 Seperate Chaining을 사용해 해시충돌을 막을 것이다.
충돌을 허용하되 이를 최소화한다. 해시 함수로 키를 해시로 바꾼 뒤 저장소에 넣을때 이미 저장소에 값이 있으면 추가적으로 배열을 생성해서 값을 추가해준다.
key : 문자열, 숫자형을 허용하기로 했다.
Hash Function : 간단하게 key를 각 문자를 유니코드로 변환해서 합한 값을 hash table을 생성할때 지정해둔 size로 나눈 나머지를 hash로 바꾼다.
insert
키에서 해시를 뽑아 내어 배열로 구성한 저장소에 hash를 인덱스로 하여 [key, value] 쌍을 저장. 이때 2차원 배열형태로 저장 가능하다.
delete
키에서 해시를 봅아 내어 해시에 해당하는 저장소의 인덱스로 접근해 삭제한다. 이 때, 해당하는 키가 존재하는지 확인해야 하며, 추가적으로 여러 요소가 존재하면 반복문으로 확인해서 찾아내어 삭제한다.
이때 delete 연산자나 해당 요소를 undefined로 바꾸게 되면 해당하는 인덱스가 빈 공간으로 남아 에러를 유발하므로 splice메서드로 삭제한다.
삭제 성공시 true를, 실패시 false를 반환한다. 값의 존재유무에 상관없이 에러는 발생해선 안된다.
search
키에서 해시를 봅아 내어 해시에 해당하는 저장소의 인덱스로 접근해 value를 반환한다. 해당하는 키가 존재하는지 확인해야 하며, 추가적으로 여러 요소가 존재하면 반복문으로 확인해서 찾아낸다.
요소를 찾아내는 모든 과정은 delete 메서드와 같다. delete메서드는 요소를 찾으면 삭제하는 프로세스를 진행하지만, search 메서드는 찾아낸 요소의 value를 반환하고 마친다.
만약 해당하는 요소가 존재하지 않으면 false를 반환한다.
getTable
구현하며 디버깅을 위해 만들어둔 테이블 전체를 반환하는 메서드
class hashTable {
constructor(size) {
this.storage = [];
if (size) {
this.size = size;
} else {
this.size = 100;
}
}
insert = (key, vale) => {
let index = this.hash(key);
if(this.storage[index] === undefined) {
this.storage[index] = [[key, value]];
} else {
let storageFlag = false;
for (let i = 0; i < this.storage[index].length; i++) {
if(this.storage[index][i][0] === key) {
this.storage[index][i][1] = value;
storageFlag = true;
}
}
if(!storageFlag) {
this.storage[index].push([key, value]);
}
}
}
delete = (key) => {
let index = this.hash(key);
if(this.storage[index] === undefined) {
return false;
} else if (this.storage[index].length === 1 && thos.storage[index][0][0] === key) {
this.storage.splice(index, 1);
return true;
} else {
for (let i = 0; i < this.storage[index].length; i++) {
if(this.storage[index][i][0] === key) {
this.storage[index].splice(i, 1)
return true;
}
}
return false;
}
}
search = (key) => {
let index = this.hash(key);
if(this.storage[index] === undefined) {
return false;
} else if(this.storage[index].length === 1 && this.storage[index][0][0] === key) {
return this.storage[index][0][1];
} else {
for (let i = 0; i < this.storage[index].length; i++) {
if(this.storage[index][i][0] === key) {
return this.storage[index][i][1];
}
return false;
}
hash = (key) => {
let hash = 0;
for(let i = 0; i < key.length; i++){
hash += key.charCodeAt(i);
}
return hash % this.size;
}
getTable(){
return this.storage;
}
}