해시 테이블(Hash Table)

 

Separate chaining을 사용하는 해시테이블의 해싱 방식에 대한 간략한 구조도

 

 

해시테이블은  키-값 쌍을 저장하는 데 사용된다.

해시 테이블의 키는 순서를 가지지 않는다.

값을 찾고, 추가하거나, 제거하는 속도가 빠르다.

 

많은 프로그래밍 언어가 해시 테이블 자료구조를 기본적으로 제공한다.

- 파이썬: Dictionary

- 자바스크립트: Object, Map (오브젝트의 경우 string 타입만을 키로 설정할 수 있다.)

- 자바&고 : Map

- 루비: Hash

 

이 포스팅에서는 기본적으로 제공하는 해시 테이블 자료구조를 사용하지 않고 직접 간단한 해시테이블을 만들어 보았다. 

충돌처리에는 Separate Chaining 방식을 사용하였다. 이는 해싱을 통해 동일한 값을 가지게 된(충돌한) 키-값 쌍이 해당 원소의 이중 배열에 추가되는 방식을 의미한다.

 

이 방식 외에 선형 조사법(Linear Probing)도 존재한다. 선형 조사법은 인덱스가 충돌했을 시 주변에서 비어 있는 인덱스를 찾아 저장하는 방법을 의미한다. 이 방법은 메모리를 연속적으로 탐색하여 캐시 지역성이 좋다. 그러나 군집화가 일어날 수 있으며 삭제 처리가 복잡하다. 단순 해싱으로 해당 인덱스를 찾을 수 없기 때문에 체인이 끊어질 수 있는 것이다. 여기서 체인이란 해싱을 통한 논리적 연결을 의미한다. (이미 존재한다 -> 옆의 인덱스 -> 이미 존재 -> 옆의 인덱스)

 

테이블 객체 생성 시, 소수(Prime Number)를 넣는 이유

해시 충돌을 줄이기 위해서이다. 즉, 배열 내에 저장되는 데이터의 분포를 고르게 하는 역할을 한다.

-소수는 서로소이기 때문에 해시 값이 특정 패턴으로 몰리는 것을 방지한다.

- 예를 들어 배열 크기가 12이고 입력 키들이 모두 12의 배수라면 같은 인덱스에 많은 충돌이 발생할 수 있다.

- 소수를 이용하면 이런 규칙적인 패턴을 깨뜨릴 수 있다.

 

 

class HashTable {
	constructor(size = 53) {
		this.keyMap = new Array(size);
	}

	_hash(key) {
		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(key, value) {
		let index = this._hash(key);
		if(!this.keyMap[index]) {	// 해당 인덱스에 값이 존재하지 않는다면 배열 생성
			this.keyMap[index] = [];
		}
		this.keyMap[index].push([key, value]);	// 생성되어 있는 배열에 넣기 
	}

	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];	// 값을 반환
				}
			}
		}
	}

	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;
	}
}