JavaScript 문자열 해시 테이블 구현: 충돌 처리와 리사이즈, NFC 정규화

여기부터는 필요한 기능을 골라 읽는 참고 영역입니다. 새로운 파일로 전체 코드를 실행할 때는 아래 Node.js 실행 안내를 따르세요. 앞쪽의 작은 브라우저 실습과 전체 파일을 한 콘솔에 이어 붙이지 마세요. 기능별 입력 조건과 반환 형식은 아래 설명을 기준으로 합니다.

키를 빨리 찾으려면 무엇을 생략할 수 있는가

문자열 배열에서 키 하나를 찾으면 최악에는 모든 키를 비교합니다. 해시 테이블은 키로부터 버킷 번호를 계산해 조사 범위를 줄입니다. 다만 가능한 문자열 수는 버킷 수보다 훨씬 많으므로 서로 다른 키가 같은 버킷으로 가는 충돌은 정상적인 현상입니다.

이 구현은 각 버킷에 작은 배열을 두는 분리 체이닝을 사용합니다. 해시는 후보 버킷을 선택하고, 그 안에서 실제 문자열 동등성 비교로 키를 확정합니다. 해시 값이 같다는 이유만으로 키까지 같다고 처리하면 서로 다른 데이터가 덮어써집니다.

문자열 계약과 유니코드 정책

키는 문자열만 허용합니다. 숫자 1이나 객체를 자동 문자열화하지 않아 의도하지 않은 키 합침을 피합니다. 키는 모든 공개 조회·저장·삭제에서 NFC로 정규화하므로 조합형 e + 결합 악센트와 완성형 é는 같은 키입니다. 대소문자, 공백, 호환 문자는 별도로 합치지 않습니다.

빈 문자열과 이모지도 유효한 키입니다. for…of는 UTF-16 코드 단위를 낱개로 쪼개지 않고 코드 포인트 단위로 진행합니다. 단, 코드 포인트는 사용자가 보는 글자 묶음인 자소와 같지 않습니다. NFC 역시 철자가 비슷한 모든 문자열을 하나로 바꾸는 검색용 유사도 처리가 아닙니다.

값에는 undefined도 허용하기 때문에 get은 {found:true,value} 또는 {found:false}를 반환합니다. 같은 정규화 키를 set하면 값만 교체하고 size는 늘리지 않습니다. entries의 순서는 버킷 배치에 따라 달라지며 삽입 순서를 보장하지 않습니다. 내부 buckets나 resize는 학습을 위한 공개 상태이므로 호출자가 직접 바꾸지 않는 계약입니다.

전체 코드와 실행

아래를 hash-table.cjs로 저장해 node ./hash-table.cjs로 실행합니다. Node.js CommonJS 전체 파일입니다. 예제는 NFC로 합쳐지는 키를 갱신하고 초기 버킷 2개를 4개로 늘린 후 조회 결과를 출력합니다.

'use strict';

class StringHashTable {
  constructor(capacity = 4) {
    if (!Number.isInteger(capacity) || capacity < 1) {
      throw new RangeError('capacity must be a positive integer');
    }
    this.buckets = Array.from({ length: capacity }, () => []);
    this.size = 0;
  }

  normalize(key) {
    if (typeof key !== 'string') throw new TypeError('key must be a string');
    return key.normalize('NFC');
  }

  index(key, capacity = this.buckets.length) {
    let hash = 2166136261;
    for (const character of key) {
      hash = Math.imul(hash ^ character.codePointAt(0), 16777619) >>> 0;
    }
    return hash % capacity;
  }

  resize(capacity) {
    const next = Array.from({ length: capacity }, () => []);
    for (const bucket of this.buckets) {
      for (const entry of bucket) {
        next[this.index(entry.key, capacity)].push(entry);
      }
    }
    this.buckets = next;
  }

  set(rawKey, value) {
    const key = this.normalize(rawKey);
    let bucket = this.buckets[this.index(key)];
    for (const entry of bucket) {
      if (entry.key === key) {
        entry.value = value;
        return this;
      }
    }
    if ((this.size + 1) / this.buckets.length > 0.75) {
      this.resize(this.buckets.length * 2);
      bucket = this.buckets[this.index(key)];
    }
    bucket.push({ key, value });
    this.size += 1;
    return this;
  }

  get(rawKey) {
    const key = this.normalize(rawKey);
    for (const entry of this.buckets[this.index(key)]) {
      if (entry.key === key) return { found: true, value: entry.value };
    }
    return { found: false };
  }

  delete(rawKey) {
    const key = this.normalize(rawKey);
    const bucket = this.buckets[this.index(key)];
    const index = bucket.findIndex(entry => entry.key === key);
    if (index === -1) return false;
    bucket.splice(index, 1);
    this.size -= 1;
    return true;
  }

  entries() {
    const result = [];
    for (const bucket of this.buckets) {
      for (const entry of bucket) result.push([entry.key, entry.value]);
    }
    return result;
  }
}

module.exports = { StringHashTable };

if (require.main === module) {
  const table = new StringHashTable(2);
  table.set('e\u0301', 1);
  table.set('é', 2);
  table.set('가', 3);
  table.set('🙂', 4);
  console.log(JSON.stringify({
    size: table.size,
    capacity: table.buckets.length,
    accent: table.get('e\u0301'),
    missing: table.get('없음')
  }));
}

실행 출력

{"size":3,"capacity":4,"accent":{"found":true,"value":2},"missing":{"found":false}}

해시 계산과 충돌 탐색

index는 코드 포인트를 누적하면서 Math.imul로 32비트 정수 곱셈을 수행하고 >>> 0으로 부호 없는 값으로 해석합니다. 마지막 나머지 연산이 버킷 범위를 만듭니다. FNV 계열의 혼합 상수를 활용한 교육용 함수이며 표준 바이트 기반 FNV 구현이나 암호학적 해시라고 주장하지 않습니다.

set은 먼저 같은 키를 찾습니다. 기존 키의 갱신이라면 새 저장 공간이 필요 없으므로 바로 반환합니다. 없을 때에만 새 원소를 포함한 적재율을 계산합니다. size가 실제 서로 다른 정규화 키 수와 일치한다는 불변식이 리사이즈 시점을 정합니다.

get은 버킷의 모든 후보 중 정확히 같은 key를 찾습니다. delete 역시 일치 항목만 지우며, splice가 뒤의 버킷 원소들을 이동시킬 수 있으므로 충돌 체인의 길이를 비용에 포함해야 합니다. 찾지 못한 삭제는 false이며 size를 바꾸지 않습니다.

왜 리사이즈는 복사가 아니라 재배치인가

적재율 (size + 1) / 버킷 수가 0.75를 넘으면 버킷 수를 두 배로 늘립니다. 같은 해시 정수라도 나누는 수가 바뀌면 나머지가 달라집니다. 기존 버킷 배열만 길게 만드는 것으로는 조회 위치가 맞지 않기 때문에 모든 항목을 새 용량으로 다시 분류합니다.

resize는 이미 중복이 제거된 항목을 직접 새 버킷에 넣습니다. set을 다시 호출하지 않으므로 size를 중복 증가시키거나 불필요하게 키를 재정규화하지 않습니다. 재배치 중에도 key와 value는 유지되며, 끝에 buckets 참조만 바꿉니다. 삭제 후에는 축소하지 않는 정책이므로 최고 사용량에 가까운 버킷 메모리가 남을 수 있습니다.

충돌을 눈으로 확인하려면 같은 용량에서 index 결과가 같은 서로 다른 두 문자열을 찾아 set해 보세요. 두 항목은 같은 배열에 나란히 있어야 합니다. 테스트에서는 index를 항상 0을 반환하도록 바꾼 별도 인스턴스로 충돌이 극단적인 경우의 정확성도 검사할 수 있습니다. 이런 조작은 일반 사용 API가 아닙니다.

평균 O(1)을 말하기 위한 조건

해시 분포가 고르다는 가정은 공격자가 고른 키에도 보장되는 사실이 아닙니다. 버킷 수가 늘어도 의도적 충돌은 남을 수 있으며, 리사이즈하는 단일 set은 상수 시간이 아닙니다. JavaScript 문자열 정규화의 구체적인 실행 시간 역시 언어 명세가 Big-O로 약속하지 않으므로 표의 문자열 처리 가정을 구분해 읽어야 합니다.

실무에서는 보통 내장 Map을 먼저 사용합니다. 이 구현의 목적은 충돌 처리와 비용 조건을 이해하는 것이며 해시 서비스의 보안성이나 Map보다 빠른 성능을 보장하지 않습니다. 외부 입력에 노출되는 서버라면 입력량 제한과 검증을 별도로 설계해야 합니다.

경계 확인과 연습

NFC 등가 키의 갱신, 대소문자가 다른 키, 빈 문자열, 이모지, 저장된 undefined, 없는 키 삭제를 확인하세요. 리사이즈 직전과 직후에 모든 entries를 다시 조회하면 나머지 계산을 옛 용량으로 수행하는 오류를 찾기 쉽습니다.

함께 연습하고 확인할 자료

Design HashMap: 정수 키 사전을 구현하는 외부 연습입니다. 이 글의 NFC 문자열 키 정책과는 입력 계약이 다릅니다.

관련 개념 참고: Princeton Algorithms — Hash Tables, MDN — String.prototype.normalize() 공식 자료와 문제 페이지는 2026년 9월 10일 확인했습니다. 외부 문제의 지문·예시를 복제하지 않고 이 글의 예제와 창작 문제를 별도로 구성했습니다.