JS에서 기본적인 HashMap을 구현하고자 했다.
Map
- 키-값 쌍을 저장할 수 있는 내장 객체이다.
- 삽입 순서를 보장한다.
주요 메서드 및 속성
set(key, value): 구현해야하는put()과 동일get(key): 구현해야하는get()과 동일has(key): 구현해야하는containsKey()와 동일delete(): 구현해야하는remove()와 동일clear(): 구현해야하는clear()와 동일size: 구현해야하는size()와 동일
Map vs HashMap
JS 에서는 HashMap이 없기 때문에(Map이 곧 HashMap), Kotlin에서의 둘의 차이를 알아보자.
| 구분 | Map | HashMap |
|---|---|---|
| 내부 구조 | 없음 | 해시 테이블 |
| 저장/조회 방법 | 구현하기 나름 | 해시 함수 기반 |
Map 은 인터페이스이고 따라서 내부 구현이 되어있지 않다. HashMap은 이 인터페이스를 기반으로 해시 함수 와 해시 테이블 을 사용해 내부 구현을 한 구현체 인 것이다.
그래서 사실 본질적인 차이 Map은 인터페이스이고 HashMap은 구현체이다 라는 것이다.
HashMap 동작 순서
hashCode()메서드를 호출해 정수형 해시값을 얻는다.- 해당 해시값을 바탕으로 내부 해시 함수가 추가 연산(비트 마스킹, 재해싱) 등을 수행한다.
- 2번 동작을 통해 해시 테이블 내 저장할 위치(버킷 인덱스) 를 결정한다.
해시함수
먼저, 해시 함수 란 키 -> 고정 길이의 숫자(해시값) 으로 변환하는 함수이다.
결국, 키를 해시 테이블의 인덱스로 빠르고 균등하게 변환 하는 것이 목적이다.
좋은 해시 함수의 조건
효율적이고 효과적인 해시 함수는 다음과 같은 조건을 만족해야 한다.
| 특징 | 설명 |
|---|---|
| 충돌 최소화 | 서로 다른 입력이 같은 해시값을 갖는 경우(충돌)을 최소화해야 함 |
| 빠른 계산 속도 | 해시값을 빠르게 계산할 수 있어야한다. |
| 균등 분포 | 키들의 해시값이 해시 테이블의 각 버킷에 고르게 분포되어야 한다. |
| 결과 예측 불가능 | 입력값에 아주 작은 변화가 있으면 해시값도 크게 달라져야 한다. (보안 중요시) |
해시값이 모든 버킷에 고르게 분포되어야 각 버킷이 적절히 사용되어 충돌이 적고, 조회 및 삽입이 빠르다고 한다.
해시맵 구조상 버킷 사이즈
해시맵은 내부에 여러 개의 저장 공간을 가진 배열 을 가지고 있다.
그리고, 이 배열의 각 칸을 버킷 이라고 부른다.
예를 들어, hash = [ [], [] ] 은 2개의 빈 배열(버킷) 이 있고, 이 배열의 길이가 버킷 사이즈 를 의미한다.
구현 함수
clear(): 전체 맵을 초기화한다.containsKey(String key): 해당 키가 존재하는지 여부에 따라boolean결과를 리턴한다.get(String): 해당 키와 매치되는 값을 찾아 리턴한다.isEmpty(): 비어있는 맵인지 Bool 결과를 리턴한다.keys(): 전체 키 목록을 [String] 배열로 리턴한다.put(String key, String value)키-값을 추가한다.remove(String key): 해당 키에 있는 값을 삭제한다.size(): 전체 아이템 개수를 리턴한다.
구현 전 고민
- 버킷 개수가 많을 수록, 충돌 확률이 감소할 텐데, 그렇다면 적절한 버킷 개수를 어떻게 구성할 것인가?
- 초반에 적당한 버킷 개수로 시작하고, 재해싱을 통해 버킷 수를 늘리고 기존에 저장된 키들을 다시 해시해서 재배치해야 할 것같다.
- 초반에 적합한 버킷 개수는 몇일까?
- Java, Kotlin의 초기 버킷 개수는 16개라고 한다. 기본적으로 버킷 개수는 2의 거듭제곱을 선호한다고 하는데,
비트 연산을 통해 성능을 비약적으로 개선할 수 있기 때문이라고 한다.
- Java, Kotlin의 초기 버킷 개수는 16개라고 한다. 기본적으로 버킷 개수는 2의 거듭제곱을 선호한다고 하는데,
- 재해싱을 하기 위한 트리거 조건은 몇으로 설정할까?
- 보통
loadFactor(부하율) = 엔트리 수 / 버킷 수가0.75를 초과하면, 다음 엔트리를 추가할 때 재해싱 트리거를 발생시킨다고 한다. 이것을 채택하자. - 재해싱시 배열 크기는 2배로 증가시킬려고 한다.
- 보통
- 기존 Map은 Map.get(key) 를 통해서, 값을 찾았다. 그런데 만약
hash = [ [1, 2], [4] ]처럼 구조가 생겼다면, 어떻게 키 값과 비교하면서 값을 도출할 수 있는가?hash [ [ [key, value], [key value] ] , [ ] ... ]와 같이, key 값도 같이 저장해서 순회할 수 있도록 해보자.
- 버킷의 개수가 충분하다고 해도, 특정 버킷에 값이 쏠릴 수 있을 것이다. 어떻게하면 버킷에 균등하게 값을 삽입할 수 있을 것인가?
- 좋은 해시 함수 설계가 필요.
- 입력값이 조금만 달라도 완전히 다른 해시값이 나와야 함.
- 패턴 있는 값들이 들어와도 특정 영역에 편중되지 않아야 함.
- 삭제가 많아서, 빈 버킷이 많이 생겼을 때도 재해싱이 필요할까?
- Java에서는 삭제 후 자동 축소는 하지 않는다고 한다. 전부 삭제시에는
clear을 사용하고, 애초에 엄청난 양의 메모리가 남을 만큼 삭제를 하지 않기 때문인 이유도 있다고 한다.
- Java에서는 삭제 후 자동 축소는 하지 않는다고 한다. 전부 삭제시에는
- 버킷의 크기가 2의 승수로 늘어나다보면 엄청나게 커질텐데, 최대 크기를 몇으로 제한해야할까?
- Java에서는 1 << 30 으로 제한한다. (약 10억 7천만)
- JS의 Map에서
size는 메서드가 아니라 속성이지만, O(1) 시간에 접근가능하다. 어떻게 이게 가능할까?size를 클래스 멤버로 관리하여,put을 할 때마다 1씩 늘려주면 된다.
구현 설정 값
JS의 Map 객체는 내부 구현 세부사항을 명확히 규정하지 않았기 때문에, Java 나 Kotlin 을 참고해서 작성했다.
- 버킷 초기 값 : 16
- 재해싱 트리거 :
loadFactor(부하율) = 엔트리 수 / 버킷 수> 0.75 초과시, 다음 엔트리 추가할 때. - 재해싱시 배열 크기 증가분 : 2배
- 버킷 내부 구조 :
[key value] - 내부 요소 삭제시 재해싱 여부: X
- 버킷 최대 크기 : 1 << 30
메서드를 구현할 때 고려했던 사항들
hashCode(String key)
해시 값을 반환하는 함수이다.
자바에서의 hashCode 의 내부 구조를 살펴보니, 해시 계산에 소수를 쓴다는 것을 확인했다.
해시 계산에 소수를 쓰면 충돌 확률이 줄고, 분포가 균등해진다 는 이유라고 한다.
또한, Java의 창시자 중 한 명이 실험을 통해 31이 가장 적당하다고 판단했다고 한다.
그래서 나도 31 을 해시 계산에 사용했다.
그리고, Java의 int 는 32비트 정수인데, hashCode() 도 int 값을 반환하기 때문에, JS 에서의 64비트를 32비트 int화 할 필요가 있어서 | 0 연산도 추가했다가, 음수 값이 나오길래 >>> 로 대체했다.
getIndex(String key)
hashCode 를 통해 가져온 해시 값을 버킷 총 개수로 나눈 나머지를 통해 인덱스를 구하는 함수이다.
hash 값은 >>> 로 인해 반드시 양수이고, % 연산만 잘 사용하면 되므로 구현이 어렵지 않았다.
isNeedReHashing()
loadFactor(부하율) = 엔트리 수 / 버킷 수
loadFactor > 0.75 라면, 리해싱이 필요하다는 의미로, boolean 을 반환하도록 했다.
put(String key, String value)
기존 key가 있다면 대체를하고 기존 key에 해당하는 버킷 마지막에 삽입하면 문제없이 구현이 가능할거라 생각했다.
JS에서 제공하는 Map 의 Set 메서드는, 반환 값으로 this 를 전달하여 메서드 체이닝을 지원하도록 하기 때문에, 나도 이와 같이 this 를 반환하도록 했다.
remove(String key)
JS에서 제공하는 Map 의 delete 메서드는 반환 값으로 boolean 을 제공하기 때문에, 여기서도 이 형식을 따랐다.
clear()
clear 을 구현하면서 버킷 크기를 초기로 돌릴까, 아니면 리해싱 이후의 크기를 유지할까 고민이 많았다.
JS나 Java에서는 리해싱 이후의 크기를 유지하고, clear 한 뒤 다시 많은 데이터를 넣을 가능성이 있기에 돌리지 않는 것이 기본 세팅이라고 한다.
메서드 명세
| 메서드 이름 | 반환 값 | 설명 |
|---|---|---|
| #hashCode(String key) | 해시값 | Key를 바탕으로 해시값을 생성해 반환한다. |
| #getIndex(String key) | 버킷 인덱스 값 | 해시 값을 바탕으로 한 버킷 인덱스 값을 반환한다. |
| #isNeedReHashing() | boolean | 리해싱이 필요한지 판별해준다. |
| remove(String key) | boolean | key에 해당하는 요소를 삭제하고, 삭제 되었다면 true 를, 아니라면 false를 반환한다. |
| isEmpty() | boolean | 맵이 비어있다면 true 를, 아니라면 false 를 반환한다. |
| put(String key, String value) | this | 키-값을 추가한다. 메서드 체이닝을 지원하기 위해 this 를 반환한다. |
| clear | undefined | 모든 버킷을 초기화한다. 리해싱 이후라면 리해싱 이후 크기로 초기화한다. |
| containsKey(String key) | boolean | 해당 키가 존재하면 true 를, 아니라면 false 를 반환한다. |
| keys | 전체 키 값 또는 undefined | 전체 키 목록을 반환한다. 키에 해당하는 값이 없을 경우, undefined를 반환한다. |
| get(String key) | 키와 매치되는 값 | 키와 매치되는 값을 반환한 |
| size() | 전체 아이템 개수 | 전체 아이템 개수를 리턴한다. |
| rehash() | undefined | 버킷 사이즈를 두 배로 늘리고, 기존 요소들도 재할당한다. |
| #validateInitialValue(initialValue) | undefined | 초기 값을 검증하고, 문제가 있다면 에러를 발생시킨다. |
구현 코드
class HashMap {
#INITIAL_CAPACITY = 16;
#MAX_BUCKET_SIZE = 1 << 30;
#MAX_LOADFACTOR = 0.75;
#RESIZE_FACTOR = 2;
#INPUT_ERROR_MESSAGE = "[ERROR] 초기 값 형태는 [['key', 'value'], ['key', 'value']] 와 같은 형태여야 합니다.";
#size;
#bucketSize;
#buckets;
constructor(initialValue = []) {
this.#bucketSize = this.#INITIAL_CAPACITY;
this.#buckets = [];
this.#size = 0;
for (let i = 0; i < this.#bucketSize; i++) {
this.#buckets[i] = [];
}
this.#validateInitialValue(initialValue);
for (const [key, value] of initialValue) {
this.put(key, value);
}
}
/**
* 전체 맵을 초기화한다.
*/
clear() {
this.#buckets = [];
for (let i = 0; i < this.#bucketSize; i++) {
this.#buckets[i] = [];
}
this.#size = 0;
}
/**
* 해당 키가 존재하는지 여부에 따라 boolean 결과를 리턴한다.
* @param {string} key
*/
containsKey(key) {
return this.get(key) !== undefined;
}
/**
* 해당 키와 매치되는 값을 찾아 리턴한다.
* @param {string} key
*/
get(key) {
const idx = this.#getIndex(key);
const bucket = this.#buckets[idx];
for (const pair of bucket) {
if (pair[0] === key) return pair[1];
}
return undefined;
}
/**
* 비어있는 맵인지 Bool 결과를 리턴한다.
*/
isEmpty() {
return this.size() === 0;
}
/**
* 전체 키 목록을 [String] 배열로 리턴한다.
*/
keys() {
const keys = [];
for (const bucket of this.#buckets) {
for (const pair of bucket) {
keys.push(pair[0]);
}
}
return keys;
}
/**
* 키-값을 추가한다.
* @param {string} key
* @param {string} value
*/
put(key, value) {
if (this.#isNeedReHashing()) {
this.#rehash();
}
const idx = this.#getIndex(key);
const bucket = this.#buckets[idx];
for (const pair of bucket) {
if (pair[0] === key) {
pair[1] = value;
return this;
}
}
bucket.push([key, value]);
this.#size++;
return this;
}
/**
* 해당 키에 있는 값을 삭제한다.
* @param {string} key
*/
remove(key) {
const idx = this.#getIndex(key);
const bucket = this.#buckets[idx];
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket.splice(i, 1);
this.#size--;
return true;
}
}
return false;
}
/**
* 전체 아이템 개수를 리턴한다.
*/
size() {
return this.#size;
}
/**
* 배열 크기를 2배로 증가하고 기존 요소를 재할당한다.
*/
#rehash() {
const oldBuckets = this.#buckets;
const nextBucketSize = this.#RESIZE_FACTOR * this.#bucketSize;
if (nextBucketSize > this.#MAX_BUCKET_SIZE) return;
this.#bucketSize = nextBucketSize;
this.clear();
for (const oldBucket of oldBuckets) {
for (const [key, value] of oldBucket) {
this.put(key, value);
}
}
}
/**
* 해시 값을 도출한다.
* @param {string} key
*/
#hashCode(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (31 * hash + key.charCodeAt(i)) >>> 0;
}
return hash;
}
/**
* 해시 값에 따라 버킷 인덱스를 반환한다.
* @param {string} key
* @returns
*/
#getIndex(key) {
const hash = this.#hashCode(key);
return hash % this.#bucketSize;
}
#isNeedReHashing() {
return (this.size() + 1) / this.#bucketSize > this.#MAX_LOADFACTOR;
}
#validateInitialValue(initialValue) {
if (initialValue.length > 0) {
if (typeof initialValue !== "object") {
throw new Error(this.#INPUT_ERROR_MESSAGE);
}
if (!initialValue.hasOwnProperty("length")) {
throw new Error(this.#INPUT_ERROR_MESSAGE);
}
for (const init of initialValue) {
if (init.length !== 2 || typeof init[0] !== "string" || typeof init[1] !== "string")
throw new Error(this.#INPUT_ERROR_MESSAGE);
}
}
}
printBucketSize() {
console.log(this.#bucketSize);
}
}
try {
const hashMap = new HashMap();
const hashMap2 = new HashMap([["홍길동", "24"]]);
hashMap.printBucketSize(); // bucketSize : 16
hashMap.put("1", "val1");
hashMap.put("2", "val1");
hashMap.put("3", "val1");
hashMap.put("4", "val1");
hashMap.put("5", "val1");
hashMap.put("6", "val1");
console.log(hashMap.keys()); // [1, 2, 3, 4, 5, 6]
hashMap.remove("1");
hashMap.remove("2");
hashMap.remove("3");
console.log(hashMap.keys()); // [4, 5, 6]
hashMap.put("7", "val1");
hashMap.put("8", "val1");
hashMap.put("9", "val1");
hashMap.put("99", "val1");
hashMap.put("11", "val1");
hashMap.put("22", "val1");
hashMap.put("33", "val1");
hashMap.put("44", "val1");
hashMap.put("55", "val1");
hashMap.put("66", "val1");
hashMap.put("77", "val1");
hashMap.put("88", "val1");
hashMap.printBucketSize(); // bucketSize : 32
console.log(hashMap.isEmpty()); // false
hashMap.clear();
console.log(hashMap.isEmpty()); // true
} catch (err) {
console.log(err);
}
꾸준함을 목표로 합니다.