Hash Table
해시 테이블은 고정된 크기의 자료 구조이다. 해시 테이블이 만들어 질 때 그 크기가 정해진다. 해시 테이블을 사용하면 자료를 쉽고 빠르게 저장할 수 있고ㅓ, 키-값(key-value) 쌍을 기반으로 자료를 얻을 수 있따. 자바스크립트에서 자바스크립트 객체는 해시 테블과 같은 방식으로 키(속성)와 해당 키의 연관된 값을 정의하는 방식으로 동작한다.
해시 테이블에는 add(), get()이라는 두 가지 주요 함수 가 있다. add()은 자료를 해시 테이블에 저장하는데 사용되고, get()은 해시 테이블로부터 자료를 얻는데 사용된다. 두 함수 모두 시간복잡도가 O(1)이다. 해시 테이블은 인덱스가 해싱 함수에 의해 계산되는 배열과 유사하다. 이때 인덱스는 메모리에서 유일한 공간을 식별하기 위한 것이다.
1. 해싱기법
해시 테이블에서 가장 중요한 부분은 해시 함수이다. 해시 함수는 특정 키를 자료를 저장하는 곳의 인덱스로 변환한다. 좋은 해시 하뭇가 되기 위해선 3가지의 요구 사항이 있다.
- 결정성: 동일한 키는 동일한 해시 값을 생성해야 한다.
- 효율성: 시간 복잡도가 O(1)이어야 한다.
- 균일한 분배: 저장 공간 정체를 최대한 활용해야 한다.
해싱의 첫 번째 기법은 소수를 사용하는 것이다. 소수와 모듈러 연산을 사용함으로써 인덱스의 균일한 분배를 보장할 수 있다.
소수해싱
해싱에서 소수(정의: 약수가 1과 자기자신인 수)는 중요하다. 소수를 활용한 모듈러 나눗셈이 균일한 방식으로 인덱스를 생성하기 때문이다.
모듈러 수: 11 4 % 11 = 4 7 % 11 = 7 15 % 11 = 4
중요한 점은 소수에 의한 모듈러는 고정된 크기에 대해 가장 균등한 분배를 보장한다는 것이다. 4와 같이 소수가 아닌 작은 수에 의한 모듈러는 단지 0부터 3까지의 범위만을 보장하고 충돌이 자주 일어난다. 모듈러 나눗셈은 해싱에 있어 지켜야할 첫 번째 해싱 기법이다.
그렇다면 이미 값이 들어가 있는 경우는 어떻게 될까? 만들어놓은 해시 테이블에 이미 값이 들어가 있는 경우를 충돌이라고 한다.
- 같은 키 값이 들어간 경우
- 키 값은 다르지만 해시 함수의 결과 값이 같은 경우
완벽한 해시 함수의 경우 충돌이 일어나지 않는다. 하지면 현실적으로 불가능한 경우가 많기 때문에 충돌이 일어날 경우 값을 어떻게 처리할지 생각해야 한다.
탐사
충돌이 발생하는 것을 피하기 위해 탐사(probing) 해싱 기법을 사용해 배열에서 다음으로 사용 가능한 인덱스를 찾을 수 있다. 방법은 선형탐사와 이차탐사가 있다.
- 선형탐사: 한 번에 한 인덱스를 증가시킴으로 사용 가능한 인덱스를 찾는 방법이다. 예를들어 동일한 키로 해싱되는 두 값이 있다고하자. 먼저 들어간 값이 인덱스 1에 들어갔다고하면, 다음에 들어오는 값은 2에 들어가게 하는 것이다. 만약 2가 비어있지 않다면, 다음 빈곳을 찾기위해 값을 늘려간다.
- 이차탐사: 군집문제를 해결하는 좋은 기법이다. 이차탐사는 완전 제곱을 사용하여 사용 가능한 인덱스를 찾는 방법이다. 예를들어 동일한 키로 해싱되는 두 값이 있다고하자. 먼저 들어간 값이 인덱스 3에 들어갔다고하면, 다음에 들어오는 값은 3 + 1^2 = 4에 들어가게 하는 것이다. 4가 비어있지 않다면 4 + 2^2 = 8에 들어가도록 하는 방법이다.
재해싱/이중 해싱
키를 균일하게 분배하는 또 다른 좋은 방법으로 이차 해싱 함수를 사용해 원래 해싱 함수로부터 나온 결과를 한 번 더 해싱하는 것이 있다. 쉽게 생각해서 해싱을 2번 한다고 생각하면 된다. 두 번째 해싱함수가 지녀야할 요구 사항이 있다
- 1차 해싱함수와 달라야 한다
- 호율적이야 한다: 시간 복잡도가 여전히 0(1)이어야 한다.
- 0이 아니어야 한다: 두 번째 햐싱함수의 결과가 0이 되어서는 안된다. 0은 초기 해시 값을 결과로 내기 때문(이전과 바뀌는게 없다)
체이닝(Chaining/Linked List)
이미 해쉬테이블에 값이 있다면, 링크드 리스트를 통해 값이 이어붙여서 저장할 수도 있다.
2. 구현
초기화
해시 테이블과 해시 테이블 안에 들어갈 값이 될 클래스들 만들어 준다. 충돌을 해결하는 여러 방법이 있지만, 이 예제에서는 최종적으로 Chaining방법을 사용할 예정이다. 앞서 학습한 Linked List의 아이디어를 사용하면 쉽게 구현이 가능하다.
class HashNode {
constructor(key, value, next) {
this.key = key;
this.value = value;
this.next = next || null;
}
}
class HashTable {
constructor(size) {
this.buckets = Array(size);
this.numBucket = this.buckets.length;
}
// 해싱함수
hash() {}
// 삽입
add() {}
// 값 얻기
get() {}
// 존재하는 모든 값 얻기
allNodes() {}
}
해싱함수
전체 테이블의 크기와 모듈로 연산 그리고 **String.chatCodeAt()**을 이용해 해싱함수를 만들어 보도록 하겠다.
class HashNode {
constructor(key, value, next) {
this.key = key;
this.value = value;
this.next = next || null;
}
}
class HashTable {
constructor(size) {
this.buckets = Array(size);
this.numBucket = this.buckets.length;
}
// 해싱함수
hash(key) {
let total = 0;
for (let i = 0; i < key.length; i += 1) {
// 문자열을 하나의 숫자로 만드는 과정
total += key.charCodeAt(i);
}
// 모듈로 연산을 통해 만들어진 테이블에 들어갈 인덱스를 만들어줌.
const bucket = total % this.numBucket;
return bucket;
}
// 삽입
add() {}
// 값 얻기
get() {}
// 존재하는 모든 값 얻기
allNodes() {}
}
삽입
해시함수가 만들어졌으면, 본격적으로 값을 넣어보도록 하겠다. 해시 함수를 통해 테이블에 들어간 위치를 얻고, 그 위치에 값을 넣어주면 된다. 해당 인덱스에 값이 없다면 값을 넣으면 되지만, 이미 값이 존재한다면...
- 새로 들어온 값이 들어온 키값과 해싱값이 모두 같다면, 기존에 있던 값을 새로 들어온 값으로 바꿔준다.
- 그 외의 경우 HashNode의 next에 값을 넣어주면 된다.
class HashNode {
constructor(key, value, next) {
this.key = key;
this.value = value;
this.next = next || null;
}
}
class HashTable {
constructor(size) {
this.buckets = Array(size);
this.numBucket = this.buckets.length;
}
// 해싱함수
hash(key) {
let total = 0;
for (let i = 0; i < key.length; i += 1) {
// 문자열을 하나의 숫자로 만드는 과정
total += key.charCodeAt(i);
}
// 모듈로 연산을 통해 만들어진 테이블에 들어갈 인덱스를 만들어줌.
const bucket = total % this.numBucket;
return bucket;
}
// 삽입
add(key, value) {
const index = this.hash(key);
// 값이 존재하는지 확인
if (!this.buckets[index]) {
// 없다면 값을 넣어준다
this.buckets[index] = new HashNode(key, value);
} else if(this.buckets[index].key === key) {
// 이미 값이 있고, 기존 값 의 키값과 새로 들어온 키 값이 같다면
// 기존 키값의 value를 새로 들어온 value로 바꿔준다
this.buckets[index].value = value;
} else {
// 이미 값이 있고, 기존 값 의 키값과 새로 들어온 키 값이 다르다면
// .next에 새로운 값을 넣어준다.
// 새로 들어온 값을 가장 끝에 넣어주는 개념이다
let currentNode = this.buckets[index];
while(currentNode.next) {
if (currentNode.next.key === key) {
currentNode.next.value = value;
return;
}
currentNode = currentNode.next;
}
currentNode.next = new HashNode(key, value);
}
}
// 값 얻기
get() {}
// 존재하는 모든 값 얻기
allNodes() {}
}
값 얻기
키 값을 통해 해시 테이블에서 값을 불러올 수 있다.
class HashNode {
constructor(key, value, next) {
this.key = key;
this.value = value;
this.next = next || null;
}
}
class HashTable {
constructor(size) {
this.buckets = Array(size);
this.numBucket = this.buckets.length;
}
// 해싱함수
hash(key) {
let total = 0;
for (let i = 0; i < key.length; i += 1) {
// 문자열을 하나의 숫자로 만드는 과정
total += key.charCodeAt(i);
}
// 모듈로 연산을 통해 만들어진 테이블에 들어갈 인덱스를 만들어줌.
const bucket = total % this.numBucket;
return bucket;
}
// 삽입
add(key, value) {
const index = this.hash(key);
// 값이 존재하는지 확인
if (!this.buckets[index]) {
// 없다면 값을 넣어준다
this.buckets[index] = new HashNode(key, value);
} else if(this.buckets[index].key === key) {
// 이미 값이 있고, 기존 값 의 키값과 새로 들어온 키 값이 같다면
// 기존 키값의 value를 새로 들어온 value로 바꿔준다
this.buckets[index].value = value;
} else {
// 이미 값이 있고, 기존 값 의 키값과 새로 들어온 키 값이 다르다면
// .next에 새로운 값을 넣어준다.
// 새로 들어온 값을 가장 끝에 넣어주는 개념이다
let currentNode = this.buckets[index];
while(currentNode.next) {
if (currentNode.next.key === key) {
currentNode.next.value = value;
return;
}
currentNode = currentNode.next;
}
currentNode.next = new HashNode(key, value);
}
}
// 값 얻기
get(key) {
let index = this.hash(key);
if (!this.buckets[index]) {
return null;
} else {
let currentNode = this.buckets[index];
while(currentNode) {
if (currentNode.key === key) {
return currentNode.value;
}
currentNode = currentNode.next;
}
return null;
}
}
// 존재하는 모든 값 얻기
allNodes() {}
}
존재하는 모든 값 얻기
해시 테이블을 보면, 빈 배열로 표시된 곳이 있다. 그리고 값 안에 next로 다른 값들도 들어가 있는 경우도 있다. 이 모든 값들을 하나의 배열로 만들어서 확인해보자.
class HashNode {
constructor(key, value, next) {
this.key = key;
this.value = value;
this.next = next || null;
}
}
class HashTable {
constructor(size) {
this.buckets = Array(size);
this.numBucket = this.buckets.length;
}
// 해싱함수
hash(key) {
let total = 0;
for (let i = 0; i < key.length; i += 1) {
// 문자열을 하나의 숫자로 만드는 과정
total += key.charCodeAt(i);
}
// 모듈로 연산을 통해 만들어진 테이블에 들어갈 인덱스를 만들어줌.
const bucket = total % this.numBucket;
return bucket;
}
// 삽입
add(key, value) {
const index = this.hash(key);
// 값이 존재하는지 확인
if (!this.buckets[index]) {
// 없다면 값을 넣어준다
this.buckets[index] = new HashNode(key, value);
} else if(this.buckets[index].key === key) {
// 이미 값이 있고, 기존 값 의 키값과 새로 들어온 키 값이 같다면
// 기존 키값의 value를 새로 들어온 value로 바꿔준다
this.buckets[index].value = value;
} else {
// 이미 값이 있고, 기존 값 의 키값과 새로 들어온 키 값이 다르다면
// .next에 새로운 값을 넣어준다.
// 새로 들어온 값을 가장 끝에 넣어주는 개념이다
let currentNode = this.buckets[index];
while(currentNode.next) {
if (currentNode.next.key === key) {
currentNode.next.value = value;
return;
}
currentNode = currentNode.next;
}
currentNode.next = new HashNode(key, value);
}
}
// 값 얻기
get(key) {
let index = this.hash(key);
if (!this.buckets[index]) {
return null;
} else {
let currentNode = this.buckets[index];
while(currentNode) {
if (currentNode.key === key) {
return currentNode.value;
}
currentNode = currentNode.next;
}
return null;
}
}
// 존재하는 모든 값 얻기
allNodes() {
let allNodes = [];
for (let i = 0; i < this.numBucket; i += 1) {
let currentNode = this.buckets[i];
while(currentNode) {
allNodes.push(currentNode);
currentNode = currentNode.next;
}
}
return allNodes;
}
}
const hs = new HashTable(30); console.log(hs); // HashTable { buckets: [ <30 empty items> ], numBucket: 30 } hs.add("hyundai", "avante"); hs.add("kia", "k5"); hs.add("gm", "trax"); console.log(hs.get('gm')); // trax console.log(hs.allNodes()); // [ // HashNode { key: 'gm', value: 'trax', next: null }, // HashNode { key: 'hyundai', value: 'avante', next: null }, // HashNode { key: 'kia', value: 'k5', next: null } // ]
정리
해시 테이블은 크기가 처음에 정의되는 고정된 크기의 자료구조이다. 해시 테이블은 배열의 인덱스 크기를 생성하는 해시 함수를 사용해 구현할 수 있다. 좋은 해싱함수는 결정성, 효율성, 균일한 분배를 갖춘 함수이다. 하지만 충돌을 완전히 없애는 것은 불가능하다. 따라서 해시 충돌 처리 기법을 이용해 충돌을 처리해야 한다. 위에 소개된 방법 말고도 다른 방법들도 존재한다. 해시 테이블은 이미 만들어진 테이블 내에서 자료들이 저장되고, 처리된다는 장점이 있다. 하지만, 만들어진 테이블 이상의 데이터가 들어오면 테이블의 크기를 재조정 해줘야하고, 해시 함수가 좋지 않다면 오히려 충돌로 인해 데이터가 손실되는 경우가 생길 수 있다. 즉, 해시 함수가 중요하며, 해시 함수의 성능에 전체 해시 테이블의 성능이 좌우될 수 있다.