해시맵 | Ray Book

해시맵이란

해시맵은 **키-값 쌍 (key-value pair)**을 저장하는 자료구조입니다. 배열이 인덱스로 값에 접근한다면, 해시맵은 임의의 키 로 값에 접근합니다.

// 배열: 숫자 인덱스로 접근
const arr = ["Ray", 30, "ray@dev.io"];
arr[0]; // "Ray"

// 해시맵: 키로 접근
const map = { name: "Ray", age: 30, email: "ray@dev.io" };
map["name"]; // "Ray"

핵심은 평균 O(1) 에 삽입, 삭제, 조회가 가능하다는 점입니다. 배열에서 특정 값을 찾으려면 처음부터 순회해야 하지만 (O(n)), 해시맵은 키만 알면 바로 접근할 수 있습니다.

이 마법 같은 성능의 비밀은 해시 함수 에 있습니다.

해시 함수

해시 함수는 키를 버킷 인덱스 로 변환하는 함수입니다. 어떤 크기의 입력이 들어와도 고정된 범위의 정수를 출력합니다.

Hash(key):
    hash_value = 0
    for each character c in key:
        hash_value = hash_value + charCode(c)
    return hash_value % bucket_count

위 의사코드는 가장 단순한 해시 함수입니다. 각 문자의 코드를 합산한 뒤 버킷 수로 나머지 연산을 합니다.

좋은 해시 함수의 조건

결정적 (Deterministic) : 같은 키는 항상 같은 해시값을 반환해야 합니다
균등 분포 (Uniform Distribution) : 키를 버킷에 고르게 분산시켜야 합니다. 한쪽 버킷에 몰리면 성능이 저하됩니다
빠른 계산 : 해시 계산 자체가 느리면 O(1) 접근의 이점이 사라집니다

실제로 V8 엔진이나 Java의 HashMap은 단순 합산이 아닌, 비트 연산과 소수를 활용한 더 정교한 해시 함수를 사용합니다.

시각화

아래 시각화에서 해시맵에 키-값 쌍을 삽입하고, 충돌이 발생했을 때 체이닝으로 해결하는 과정을 단계별로 확인해 보세요.

Bucket Array (size: 5)

empty

해시맵의 내부는 버킷 배열입니다. 5개의 빈 버킷으로 시작합니다. 키-값 쌍을 저장할 때, 해시 함수가 키를 버킷 인덱스로 변환합니다.

충돌 처리

서로 다른 키가 같은 버킷에 매핑되는 것을 해시 충돌 (Hash Collision) 이라고 합니다. 버킷 수가 유한하므로 충돌은 피할 수 없습니다. 대표적인 해결 방법 두 가지를 살펴봅니다.

체이닝 (Separate Chaining)

각 버킷이 연결 리스트 (또는 다른 자료구조)를 가지고 있어, 같은 버킷에 여러 항목을 저장합니다.

Chained-Insert(hashmap, key, value):
    index = Hash(key)
    bucket = hashmap.buckets[index]
    for each entry in bucket:
        if entry.key == key:
            entry.value = value    // 기존 키면 값 업데이트
            return
    bucket.append(key, value)      // 새 키면 추가

Chained-Lookup(hashmap, key):
    index = Hash(key)
    bucket = hashmap.buckets[index]
    for each entry in bucket:
        if entry.key == key:
            return entry.value
    return NOT_FOUND

장점 : 구현이 단순하고, 삭제가 쉽습니다
단점 : 체인이 길어지면 O(n)으로 퇴화합니다. 추가 메모리 (포인터)가 필요합니다

개방 주소법 (Open Addressing)

충돌이 발생하면 다른 빈 버킷 을 찾아서 저장합니다. 별도의 연결 리스트 없이 버킷 배열 자체만 사용합니다.

Linear-Probing-Insert(hashmap, key, value):
    index = Hash(key)
    while hashmap.buckets[index] is not empty:
        if hashmap.buckets[index].key == key:
            hashmap.buckets[index].value = value  // 업데이트
            return
        index = (index + 1) % bucket_count        // 다음 버킷 탐색
    hashmap.buckets[index] = (key, value)

Linear-Probing-Lookup(hashmap, key):
    index = Hash(key)
    while hashmap.buckets[index] is not empty:
        if hashmap.buckets[index].key == key:
            return hashmap.buckets[index].value
        index = (index + 1) % bucket_count
    return NOT_FOUND

장점 : 캐시 친화적입니다 (연속 메모리 접근). 포인터 오버헤드가 없습니다
단점 : 클러스터링 (연속된 버킷이 채워지는 현상)이 발생할 수 있습니다. 삭제가 복잡합니다

부하율과 리사이징

부하율 (Load Factor) 은 저장된 항목 수를 버킷 수로 나눈 값입니다.

Load Factor = 저장된 항목 수 / 버킷 수

부하율이 높을수록 충돌 확률이 올라갑니다. 일반적으로 부하율이 0.75(75%)를 넘으면 리사이징 (Resizing) 을 수행합니다.

Resize(hashmap):
    new_bucket_count = hashmap.bucket_count * 2
    new_buckets = 새 배열[new_bucket_count]
    for each bucket in hashmap.buckets:
        for each entry in bucket:
            new_index = Hash(entry.key) % new_bucket_count
            new_buckets[new_index].append(entry)
    hashmap.buckets = new_buckets
    hashmap.bucket_count = new_bucket_count

리사이징은 모든 항목을 새 배열에 다시 배치하므로 **O(n)**이 걸립니다. 하지만 충분히 드물게 발생하기 때문에, 삽입의 분할 상환 시간 복잡도 (Amortized Time Complexity) 는 여전히 O(1)입니다.

JavaScript 구현

의사코드를 JavaScript 클래스로 구현해 보겠습니다. 체이닝 방식을 사용합니다.

class HashMap {
  #buckets;
  #size = 0;
  #capacity;

  constructor(capacity = 16) {
    this.#capacity = capacity;
    this.#buckets = Array.from({ length: capacity }, () => []);
  }

  #hash(key) {
    let hash = 0;
    const str = String(key);
    for (let i = 0; i < str.length; i++) {
      // 31은 소수, 균등 분포에 유리
      hash = (hash * 31 + str.charCodeAt(i)) | 0;
    }
    return Math.abs(hash) % this.#capacity;
  }

  set(key, value) {
    const index = this.#hash(key);
    const bucket = this.#buckets[index];

    for (const entry of bucket) {
      if (entry[0] === key) {
        entry[1] = value; // 기존 키면 업데이트
        return;
      }
    }

    bucket.push([key, value]);
    this.#size++;

    // 부하율 0.75 초과 시 리사이징
    if (this.#size / this.#capacity > 0.75) {
      this.#resize();
    }
  }

  get(key) {
    const index = this.#hash(key);
    const bucket = this.#buckets[index];

    for (const entry of bucket) {
      if (entry[0] === key) {
        return entry[1];
      }
    }
    return undefined;
  }

  delete(key) {
    const index = this.#hash(key);
    const bucket = this.#buckets[index];
    const entryIndex = bucket.findIndex((e) => e[0] === key);

    if (entryIndex === -1) return false;

    bucket.splice(entryIndex, 1);
    this.#size--;
    return true;
  }

  has(key) {
    const idx = this.#hash(key);
    const bucket = this.#buckets[idx];
    return bucket ? bucket.some(([k]) => k === key) : false;
  }

  get size() {
    return this.#size;
  }

  #resize() {
    const oldBuckets = this.#buckets;
    this.#capacity *= 2;
    this.#buckets = Array.from({ length: this.#capacity }, () => []);
    this.#size = 0;

    for (const bucket of oldBuckets) {
      for (const [key, value] of bucket) {
        this.set(key, value);
      }
    }
  }
}

const map = new HashMap();
map.set("name", "Ray");
map.set("age", 30);
map.set("email", "ray@dev.io");

console.log(map.get("name"));  // "Ray"
console.log(map.has("age"));   // true
console.log(map.size);         // 3

map.delete("age");
console.log(map.has("age"));   // false

실무 연결

Object vs Map

JavaScript에서 키-값 저장소로 Object와 Map 둘 다 사용할 수 있지만, 내부 동작이 다릅니다.

특성	Object	Map
키 타입	문자열, Symbol만	모든 값 (객체, 함수 포함)
키 순서	삽입 순서 보장 (ES2015+, 정수 키 제외)	항상 삽입 순서 보장
크기 확인	`Object.keys(obj).length`, O(n)	`map.size`, O(1)
이터레이션	`for...in`, `Object.entries()`	`for...of`, `.forEach()`
프로토타입 오염	`toString` 등 기본 키 존재	없음
빈번한 추가/삭제	비최적화	최적화됨

일반 규칙 : 설정 객체나 간단한 레코드에는 Object, 동적으로 키-값을 추가/삭제하는 컬렉션에는 Map을 사용합니다.

V8 Hidden Class와의 관계

앞서 시리즈에서 다룬 V8의 Hidden Class는 해시맵과 직접적으로 연결됩니다. JavaScript 객체는 본질적으로 해시맵이지만, V8은 성능을 위해 Hidden Class로 프로퍼티 접근을 최적화합니다.

// V8의 관점에서...
const obj = {};
obj.x = 1;  // Hidden Class 전이 (C0 -> C1)
obj.y = 2;  // Hidden Class 전이 (C1 -> C2)

// Hidden Class가 안정되면 -> 오프셋 기반 접근 (배열처럼 빠름)
// Hidden Class가 불안정하면 -> 해시맵 탐색으로 폴백 (느림)

같은 구조의 객체를 반복 생성하면 Hidden Class를 공유하여 해시맵 탐색을 피할 수 있습니다. 반대로 delete obj.prop이나 동적 프로퍼티 추가는 Hidden Class를 무효화하여 해시맵 모드로 전환시킵니다.

시간 복잡도 정리

연산	평균	최악 (모든 키가 충돌)
삽입 (set)	O(1)	O(n)
조회 (get)	O(1)	O(n)
삭제 (delete)	O(1)	O(n)
탐색 (값으로 찾기)	O(n)	O(n)

최악의 경우는 모든 키가 같은 버킷에 매핑될 때입니다. 좋은 해시 함수와 적절한 부하율 관리로 이를 방지합니다.

다음 단계

해시맵은 배열 위에 해시 함수라는 "변환 계층"을 올린 자료구조입니다. 다음 글에서는 **트리 (Tree)**와 이진 탐색 트리 (BST) 를 살펴봅니다. 계층적 데이터를 표현하고, O(log n) 탐색을 가능하게 하는 트리 구조의 원리를 시각화합니다.