JavaScriot로 hash table을 구현해보자.
연관배열 구조(associative array)
hash table을 보기전에 연관배열 구조에 대해 알아야 한다. 연관배열 구조는 간단하게 키 1개와 값 1개가 1:1로 연관되어 있는 구조를 말한다.
Hash Table
해시 테이븢ㄹ은 연관배열 구조를 이용해 키에 값을 저장하는 자료구조이다. 좀 더 자세하게 설명하면 키는 해시함수를 통해 해시로 변경되며 해시는 값과 매칭되어 저장소에 저장이 된다.
Hash Table의 요소
- 키(key) : 고유한 값. 해시의 input이 된다. 다양한 길이의 값이 될 수 있다. 이 상태로 저장소에 저장이 되면 다양한 길이 만큼의 저장소를 구성해 두어야 하기 때문에 해시 함수로 값을 바꾸어 저장되어야 공간의 효율성을 추구할 수 있다.
- 해시 함수(Hash Function) : 키를 해시로 바꿔주는 역할을 한다. 다양한 길이를 가지고 있는 키를 일정한 길이를 가지는 해시로 변경해 저장소를 효율적으로 운영할 수 있도록 도와준다. 다만, 서로 다른 키가 같은 해시로 되는 경우를 해시 충돌이라고 하는데, 해시 충돌을 일으키는 확률을 최대한 줄이는 함수를 만드는 것이 중요하다.
- 해시(hash) : 해시 함수의 결과물이며, 저장소에서 값과 매칭되어 저장된다.
- 값(value) : 저장소에 최종적으로 저장되는 값으로 키와 매칭되어 저장, 삭제 , 검색, 접근이 가능해야 한다.
Hash Table의 메서드
- 저장(insertion) : 키를 해시 함수를 사용해서 해시로 변경한 뒤 저장소에 해시에 해당하는 인덱스에 값을 저장한다. 해시 함수를 통해 키를 해시로 변경해 해당하는 저장소에 값을 저장하기 때문에 시간복잡도는 O(1)이다.
- 삭제(deletion) : 키를 해시 함수를 사용해서 해시로 변경한 뒤 저장소에 해시에 해당하는 인덱스의 값을 삭제한다. 마찬가지로 시간 복잡도는 O(1)이다.
- 검색(search) : 키를 해시 함수를 사용해서 해시로 변경한 뒤 저장소에 해시에 해당하는 인덱스 값을 반환한다. 마찬가지로 시간 복잡도는 O(1)이다.
Hash Collision(해시 충돌)
해시 테이블은 저장, 삭제 , 검색에서 평균적으로 O(1)의 시간 복잡도를 갖고있다. 이러한 우수한 효율성을 장점으로 갖는 반면, 해시를 이용한 자료구조 방식은 필연적으로 갖는 문제가 있는데, 무한한 값(key)을 유한한 값(hash)로 표현하면서 서로 다른 두개 이상의 유한한 값이 동일한 출력값을 가지게 된다는 것이다. 이를 hash collision(해시 충돌)이라 한다.
이 해시 충돌을 해결하는 방법은 여러가지가 있지만, 여기서는 Seperate Chaining을 사용해 해시충돌을 막을 것이다.
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;
}
}출처
