HashMap 직접 구현하기

자바스크립트의 Map을 배열만으로 직접 구현해보면서 해시맵의 동작 원리를 이해하는 과정을 정리했다.

 

구현 목표

자바스크립트의 Map 기본 동작을 따라서 문자열 키-값 해시맵을 구현한다.

단, Object, Map 등을 사용하지 않고 오직 배열로만 구현해야 한다.

구현할 메서드

• clear(): 전체 맵 초기화
• containsKey(String): 키 존재 여부 반환
• get(String): 키에 해당하는 값 반환
• isEmpty(): 빈 맵 여부 반환
• keys(): 전체 키 목록을 배열로 반환
• put(String key, String value): 키-값 추가
• remove(String key): 키에 해당하는 값 삭제
• size(): 전체 아이템 개수 반환

 

사전 학습

구현에 앞서 필요한 개념들을 먼저 정리했다.

배열과 리스트

배열은 메모리에서 연속된 공간에 같은 타입의 데이터를 저장하는 구조다.

메모리 주소:   1000   1004   1008   1012
데이터:       [10]   [20]   [30]   [40]
인덱스:        0      1      2      3

• 고정된 크기
• 인덱스로 직접 접근 가능: O(1)
• 메모리 효율적
• 중간 삽입/삭제에 비효율적: O(n)

 

리스트는 각 요소가 다음 요소의 위치를 가리키는 구조다.

           [데이터:10|다음:1008] -> [데이터:20|다음:2004] -> [데이터:30|다음:null]
메모리주소:          1000                  1008                  2004

• 동적인 크기
• 순차 접근만 가능: O(n)
• 삽입/삭제에 효율적: O(1)
• 포인터 저장을 위한 추가 메모리 필요

 

해시와 해시맵

해시는 데이터를 정해진 규칙에 따라 다른 값으로 변환하는 것이다.

'사과' -> 해시함수 -> 12345
'바나나' -> 해시함수 -> 67890
'오렌지' -> 해시함수 -> 24680

 

해시맵은 해시를 이용해 키-값을 저장하는 자료구조다.

키 '사과' -> 해시함수 -> 인덱스 12345 -> 배열[12345]에 값 저장
키 '바나나' -> 해시함수 -> 인덱스 67890 -> 배열[67890]에 값 저장

키로 바로 값에 접근이 가능하여 O(1) 시간복잡도를 가진다.

 

JavaScript의 Map

Map은 키-값 구조를 뜻하는 개념이다. 이러한 Map의 형태를 가지는 여러 자료구조 중 해시 방식으로 구현한 구체적인 클래스를 HashMap이라고 한다.

// Java
Map<String, Integer> map1 = new HashMap<>(); // 해시 방식
Map<String, Integer> map2 = new TreeMap<>();  // 트리 방식

 

자바스크립트에서는 HashMap만 제공하기 때문에 특별히 구분할 필요가 없어 이름을 Map으로 단순화했다.

// JavaScript
const map = new Map(); // 실제로는 해시 방식

 

구현 과정

기본 구조

자바스크립트 Map의 실제 동작에 가깝게 만들기 위해 클래스 방식을 선택했다.

class HashMap {
  constructor() {
    this._buckets = [];
    this._currentSize = 0;
    this._INITIAL_CAPACITY = 16;
    this._LOAD_FACTOR = 0.75;
    this._initialize();
  }

  _initialize() {
    this._buckets = [];
    for (let i = 0; i < this._INITIAL_CAPACITY; i++) {
      this._buckets[i] = [];
    }
    this._currentSize = 0;
  }
}

충돌 해결 방식 선택

해시맵에서는 서로 다른 키가 같은 해시값을 가지는 충돌 상황이 발생할 수 있다.

대표적인 충돌 해결 방식으로는 오픈 어드레싱과 체이닝이 있다.

	오픈 어드레싱	체이닝
방식	충돌 시 다른 빈 슬롯을 찾아 저장	충돌 시 같은 슬롯에 연결 리스트로 여러 데이터 저장
장점	적은 메모리 사용량, 빠른 접근 속도	간단한 삭제, 성능 안정성
단점	데이터 군집현상 발생	추가 메모리 필요

 

자바스크립트는 배열의 크기가 동적으로 조절되고 push(), splice() 등 다양한 배열 조작 메서드를 사용할 수 있기 때문에 구현 로직이 더 직관적인 체이닝 방식을 선택했다.

 

버킷 구조

체이닝 방식에서는 각 버킷이 여러 키-값 쌍을 저장할 수 있어야 한다.

// 둘 다 버킷 인덱스 3번으로 계산됐을 때 (충돌)
buckets[3] = [
  { key: "apple", value: "사과" },
  { key: "grape", value: "포도" },
];

배열로 해시맵을 직접 구현하되, 키-값 쌍을 표현하기 위한 단순 데이터 구조로는 객체를 사용했다.

 

해시 함수

문자열 키를 배열 인덱스로 변환하는 해시 함수가 필요하다. 일반적으로 사용되는 방식 중 다항식 해시 방식을 선택했다.

	ASCII 합계	다항식
설명	각 문자의 ASCII 값을 합산	문자의 위치를 가중치로 고려하여 계산
장점	구현이 간단	충돌 최소화, 균등한 분산
단점	순열 문자열이 같은 해시값을 가짐	-

 

다항식 해시는 각 문자에 위치별 가중치를 부여하고, 31(소수)의 거듭제곱을 사용하여 좋은 분산 특성을 가진다.

_hash(key) {
  let hashValue = 0;
  for (let i = 0; i < key.length; i++) {
    hashValue = hashValue * 31 + key.charCodeAt(i);
  }
  return Math.abs(hashValue) % this._buckets.length;
}

 

핵심 메서드 구현

put(key, value)

가장 기본이 되는 데이터 저장 기능이다.

put(key, value) {
  const idx = this._hash(key);
  const bucket = this._buckets[idx];
  const existingEntry = bucket.find((entry) => entry.key === key);

  if (existingEntry) {
    existingEntry.value = value;
  } else {
    bucket.push({ key, value });
    this._currentSize++;
  }
}

 

get(key)

저장된 데이터를 조회한다. 이 과정에서 키를 통해 엔트리를 찾는 공통 로직이 반복되어 헬퍼 메서드로 분리했다.

_getBucket(key) {
  const idx = this._hash(key);
  return { idx, bucket: this._buckets[idx] };
}

_findEntry(key) {
  const { bucket } = this._getBucket(key);
  return bucket.find((entry) => entry.key === key);
}

get(key) {
  const entry = this._findEntry(key);
  return entry ? entry.value : null;
}

 

containsKey(key)

키 존재 여부를 boolean으로 반환한다.

containsKey(key) {
  const { bucket } = this._getBucket(key);
  return bucket.some((entry) => entry.key === key);
}

 

size(), isEmpty(), clear()

인스턴스 변수와 초기화 함수를 활용해 간단하게 구현했다.

size() {
  return this._currentSize;
}

isEmpty() {
  return this._currentSize === 0;
}

clear() {
  this._initialize();
}

 

keys()

전체 키 목록을 배열로 반환한다. 2차원 배열을 순회하면서 키를 수집한다.

keys() {
  const keyList = [];
  for (const bucket of this._buckets) {
    for (const entry of bucket) {
      keyList.push(entry.key);
    }
  }
  return keyList;
}

 

remove(key)

키와 값을 모두 제거하고 삭제 성공 여부를 boolean으로 반환한다.

remove(key) {
  if (!this.containsKey(key)) return false;

  const { bucket } = this._getBucket(key);
  const entryIdx = bucket.findIndex((entry) => entry.key === key);
  bucket.splice(entryIdx, 1);
  this._currentSize--;
  return true;
}

 

동적 크기 조절

데이터 저장소의 크기를 동적으로 변화시키기 위해 로드 팩터 방식을 사용했다.

• 로드 팩터 = 저장된 데이터의 개수 / 전체 공간
• 일반적으로 사용하는 0.75를 기준으로 설정
• 이 값을 초과하면 버킷 크기를 2배로 확장

확장 방식

해시 함수에서 hash(key) % buckets.length로 인덱스를 계산하기 때문에, 버킷 크기가 변경되면 같은 키라도 다른 위치가 계산된다. 따라서 모든 데이터를 새로운 해시값으로 재배치해야 한다.

_initialize(capacity = this._INITIAL_CAPACITY) {
  this._buckets = [];
  for (let i = 0; i < capacity; i++) {
    this._buckets[i] = [];
  }
  this._currentSize = 0;
}

_resize() {
  const oldBuckets = this._buckets;
  const newCapacity = this._buckets.length * 2;

  this._initialize(newCapacity);

  for (const bucket of oldBuckets) {
    for (const { key, value } of bucket) {
      this._addEntry(key, value);
    }
  }
}

_addEntry(key, value) {
  const { bucket } = this._getBucket(key);
  bucket.push({ key, value });
  this._currentSize++;
}

resize() 에서 put()을 사용하면 로드 팩터 체크가 다시 일어나 무한 루프에 빠지기 때문에, 로드 팩터 체크 없이 단순히 엔트리만 추가하는 _addEntry() 함수를 분리했다.

 

더 나아가기

다른 타입의 키

자바스크립트의 내장 Map은 어떤 타입이든 키로 사용할 수 있다.

현재 구현은 문자열만 지원하지만, 다른 타입을 지원하려면 해시 함수를 다음과 같이 수정할 수 있다.

_hash(key) {
  let keyString;

  switch (typeof key) {
    case 'string':
      keyString = key;
      break;
    case 'number':
      keyString = key.toString();
      break;
    case 'boolean':
      keyString = key.toString();
      break;
    case 'object':
      keyString = JSON.stringify(key);
      break;
    default:
      keyString = String(key);
  }

  let hashValue = 0;
  for (const char of keyString) {
    hashValue = hashValue * 31 + char.charCodeAt(0);
  }
  return Math.abs(hashValue) % this._buckets.length;
}

다만 객체 키는 JSON.stringify()의 속성 순서에 따라 다른 해시값을 가질 수 있고, 참조 타입은 같은 내용의 다른 객체라도 서로 다른 키로 인식될 수 있다는 점을 주의해야 한다.

 

HashMap의 성능 기준

HashMap의 성능을 평가할 때는 여러 측면을 고려해야 한다.

시간 복잡도

이상적인 경우 모든 연산이 O(1)이지만, 최악의 경우 모든 키가 같은 버킷에 몰려 O(n)이 될 수 있다. 좋은 해시 함수와 적절한 로드 팩터를 유지하면 평균적으로 O(1) 성능을 달성할 수 있다.

로드 팩터

저장된 데이터 수 / 버킷 수로 계산되며, 일반적으로 0.75를 기준으로 한다. 이 값을 초과하면 충돌이 빈번해져 성능이 저하되고, 너무 낮으면 메모리가 낭비된다.

해시 함수의 품질

모든 버킷에 데이터가 고르게 분산되어야 하고, 서로 다른 키가 같은 해시값을 갖는 충돌을 최소화해야 한다. 또한 해시 계산 자체도 빠르게 수행되어야 한다.

메모리 사용량

버킷의 초기 용량과 확장 정책, 키-값 저장을 위한 추가 메모리, 체이닝 방식의 연결 구조 오버헤드 등이 전체 메모리 효율성에 영향을 준다.

 

정리

이번 구현을 통해 다음의 내용들을 배웠다

• 로드 팩터 0.75 기준의 동적 크기 조절
• 다항식 해시 함수로 충돌 최소화
• 체이닝 방식을 통한 삭제 로직 단순화
• 자바스크립트 환경에 적합한 배열 중심 구현

기본 요구사항인 문자열 키-값은 충실히 만족시켰고, 다양한 키 타입을 지원하는 방법도 고민해봤다. 다만 객체의 속성 순서 문제나 참조 타입의 동일성 판단 같은 부분은 실제 구현까지는 하지 못한 것이 아쉽다.

 

그래도 Map의 내부 동작 원리를 이해하고 직접 구현해보면서, 편리하게 사용했던 메서드 뒤에 이렇게 많은 고려사항들이 숨어있다는 걸 알게 된 것만으로도 의미 있는 학습이었다.