javascript

해시 테이블의 동작 원리 — JavaScript 객체와 Map은 데이터를 어떻게 찾을까

해시 테이블이 데이터를 O(1)로 찾는 원리를 처음부터 설명합니다. V8 엔진의 히든 클래스 최적화, 객체와 Map의 내부 차이, 그리고 실무에서의 올바른 선택 기준을 정리합니다.

javascript hash-table v8 map object data-structure

들어가며

JavaScript에서 가장 자주 사용하는 문법 중 하나가 객체({})다. 키를 넣으면 값이 바로 나오는 이 단순한 동작 뒤에는 해시 테이블(Hash Table)이라는 자료구조의 원리가 숨어있다.

이 글에서는 데이터를 빠르게 찾는 문제에서 출발하여, 해시 테이블이 왜 필요한지, 어떻게 동작하는지를 처음부터 설명한다. 그리고 JavaScript의 객체와 Map이 내부적으로 어떻게 다른지, 실무에서는 언제 무엇을 써야 하는지까지 정리한다.

데이터를 저장하고 찾는 문제

배열에서 데이터 찾기

컴퓨터에 학생 정보를 저장한다고 생각해보자.

const students = [
  { name: '민수', score: 85 },
  { name: '영희', score: 92 },
  { name: '철수', score: 78 },
  // ... 수천 명의 학생
];

여기서 영희의 점수 를 찾으려면 어떻게 해야 할까?

1번째 확인: '민수' → 영희가 아니다, 다음
2번째 확인: '영희' → 찾았다! 92점

학생이 3명이면 금방이지만, 100만 명이라면? 최악의 경우 100만 번을 확인해야 한다. 이것을 O(n) 이라고 부른다. 데이터가 n개면 최대 n번 확인해야 한다는 뜻이다.

더 빠른 방법은 없을까?

도서관을 생각해보자. 책을 찾을 때 1번 서가부터 순서대로 훑지 않는다. 컴퓨터 과학 → 3층 A구역 같은 분류 체계가 있어서 바로 해당 위치로 찾아간다.

해시 테이블이 바로 이 분류 체계 역할을 한다.

해시 테이블의 원리

해시 함수란?

해시 함수는 입력값을 숫자로 바꿔주는 변환기다. 일상적인 비유로 설명하면 우편번호 체계와 비슷하다.

서울시 강남구 역삼동→ 06235
서울시 마포구 합정동→ 04085

주소(키)를 넣으면 → 숫자(우편번호)가 나온다

프로그래밍에서의 해시 함수도 같은 원리다.

해시 함수(민수) → 2
해시 함수(영희) → 5
해시 함수(철수) → 1

저장 과정

해시 테이블 내부에는 배열(버킷)이 있다. 해시 함수가 만든 숫자를 배열의 칸 번호로 사용한다.

저장할 데이터: 영희→ 92점

1단계: 해시 함수(영희) → 5    (키를 숫자로 변환)
2단계: 배열[5]에 저장            (해당 칸에 데이터 넣기)

배열 내부 상태:
┌───┬───┬───┬───┬───┬──────┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │  5   │ 6 │ 7 │
│   │철수│민수│   │   │ 영희 │   │   │
│   │ 78│ 85│   │   │  92  │   │   │
└───┴───┴───┴───┴───┴──────┴───┴───┘

조회 과정

영희의 점수를 찾을 때도 같은 해시 함수를 사용한다.

1단계: 해시 함수(영희) → 5    (같은 함수니까 같은 결과)
2단계: 배열[5] 확인 → 92점!     (바로 접근!)

배열에서 100만 번 찾아야 했던 것을 단 1번에 찾는다. 이것이 O(1) — 데이터가 아무리 많아도 한 번에 찾을 수 있다는 뜻이다.

해시 함수는 어떻게 동작할까?

아주 간단한 해시 함수를 직접 만들어보자.

// 각 글자의 문자 코드를 더한 뒤 배열 크기로 나눈 나머지
const hash = (key, bucketSize) => {
  let total = 0;
  for (let i = 0; i < key.length; i++) {
    total += key.charCodeAt(i);
    // charCodeAt: 문자를 숫자로 변환
    // 'a' → 97, 'b' → 98, 'A' → 65 ...
  }
  return total % bucketSize;
  // % (나머지 연산): 결과가 항상 0 ~ (bucketSize - 1) 범위
  // 예: 317 % 8 = 5 → 배열 크기가 8이면 0~7 사이 값이 나옴
};

hash('abc', 8); // (97 + 98 + 99) % 8 = 294 % 8 = 6
hash('bca', 8); // (98 + 99 + 97) % 8 = 294 % 8 = 6 ← 같은 값! (충돌)

실제 프로그래밍 언어들은 이보다 훨씬 정교한 해시 함수를 사용하지만, 원리는 동일하다. 키를 숫자로 변환하여 배열 인덱스로 사용하는 것이다.

해시 충돌 — 피할 수 없는 문제

충돌이란?

배열 칸은 한정되어 있는데 저장할 데이터는 많다. 서로 다른 키가 같은 칸 번호를 받는 일이 생긴다.

해시 함수(영희) → 5
해시 함수(수진) → 5   ← 같은 칸! 충돌 발생!

비유하자면, 두 사람이 같은 사물함 번호를 배정받은 상황이다.

해결법 1: 체이닝 (Chaining)

한 칸에 여러 데이터를 연결 리스트로 이어붙이는 방식이다.

배열[5]: (영희, 92) → (수진, 88) → null

조회: 수진의 점수
1단계: 해시 함수(수진) → 5
2단계: 배열[5]에서 키가 수진인 것을 탐색
       영희? 아님 → 다음 → 수진? 맞음! → 88점
┌───┬───┬───┬───┬───┬──────────────┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │      5       │ 6 │ 7 │
│   │철수│민수│   │   │ 영희 → 수진 │   │   │
│   │ 78│ 85│   │   │  92     88   │   │   │
└───┴───┴───┴───┴───┴──────────────┴───┴───┘

해결법 2: 개방 주소법 (Open Addressing)

충돌이 나면 다음 빈 칸을 찾아 저장하는 방식이다.

수진을 저장하려는데 배열[5]가 이미 차있음
→ 배열[6] 확인 → 비어있음! → 여기에 저장

┌───┬───┬───┬───┬───┬──────┬──────┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │  5   │  6   │ 7 │
│   │철수│민수│   │   │ 영희 │ 수진 │   │
│   │ 78│ 85│   │   │  92  │  88  │   │
└───┴───┴───┴───┴───┴──────┴──────┴───┘

충돌이 많아지면?

한 칸에 데이터가 몰리면 결국 그 칸에서 하나씩 찾아봐야 한다. 극단적으로 모든 데이터가 한 칸에 몰리면 배열에서 순서대로 찾는 것과 다를 바 없는 O(n)이 된다.

그래서 두 가지가 중요하다.

대부분의 프로그래밍 언어는 적재율(load factor)을 감시한다. 적재율이란 저장된 데이터 수 / 배열 크기인데, 이 비율이 일정 수준(보통 0.75)을 넘으면 배열 크기를 2배로 늘리고 모든 데이터를 다시 배치한다. 이 과정을 리해싱(rehashing)이라고 한다.

JavaScript 객체와 해시 테이블

겉보기에는 해시 테이블

JavaScript 객체는 겉으로 보면 해시 테이블과 똑같이 동작한다.

const student = {
  name: '영희',
  score: 92,
  grade: 'A',
};

student.name; // '영희' — 키로 바로 접근
student.score; // 92

하지만 V8 엔진 (Chrome, Node.js의 JavaScript 엔진)은 내부적으로 더 똑똑한 방법을 사용한다.

V8의 히든 클래스 (Hidden Class)

V8은 객체를 만들 때 내부적으로 설계도 를 만든다. 이것을 히든 클래스(Hidden Class) 또는 Shape라고 부른다.

const student1 = { name: '영희', score: 92 };
const student2 = { name: '민수', score: 85 };

이 두 객체는 같은 프로퍼티(name, score)를 같은 순서로 가지고 있으므로, V8은 설계도를 하나만 만들어 공유한다.

설계도 (히든 클래스):
┌─────────────────────┐
│ name  → 메모리 0번째 │
│ score → 메모리 1번째 │
└─────────────────────┘

student1의 실제 메모리: ['영희', 92]  ← 배열처럼 연속 저장
student2의 실제 메모리: ['민수', 85]  ← 같은 설계도 사용

왜 히든 클래스가 빠른가?

해시 테이블 방식과 히든 클래스 방식의 조회 과정을 비교해보자.

해시 테이블 방식:
score→ 해시 함수 실행 → 해시값 계산 → 버킷 찾기 → 충돌 처리 → 값 반환

히든 클래스 방식:
score→ 설계도에서 1번째 → 메모리[1] 바로 접근

해시를 계산하는 과정 자체를 건너뛰기 때문에 훨씬 빠르다. V8은 이 최적화를 통해 JavaScript 객체의 프로퍼티 접근 속도를 C++ 구조체(struct)에 근접하게 만든다.

히든 클래스 전환 과정

V8은 프로퍼티가 추가될 때마다 새로운 히든 클래스를 생성하고, 이전 클래스와 전환 체인(transition chain)으로 연결한다.

const obj = {}; // 히든 클래스 C0 (빈 객체)
obj.name = '영희'; // 히든 클래스 C1 (name 추가)
obj.score = 92; // 히든 클래스 C2 (score 추가)
C0 {} ──name──▶ C1 {name} ──score──▶ C2 {name, score}

같은 순서로 프로퍼티를 추가하는 다른 객체는 이 전환 체인을 재사용한다. 그래서 같은 형태의 객체가 많을수록 V8의 최적화 효과가 커진다.

히든 클래스가 깨지는 경우

V8의 최적화가 무너지면 느린 해시 테이블(딕셔너리 모드)로 전환된다.

// ❌ 사례 1: 프로퍼티 추가 순서가 다를 때
const a = { name: '영희', score: 92 }; // 설계도 A
const b = { score: 85, name: '민수' }; // 설계도 B (순서가 다름!)
// → 설계도를 공유하지 못한다

// ❌ 사례 2: delete로 프로퍼티를 삭제할 때
const student = { name: '영희', score: 92, grade: 'A' };
delete student.score;
// → 설계도 체인이 깨짐 → 딕셔너리 모드로 전환 (느려짐)

// ✅ 대안: delete 대신 undefined 할당
student.score = undefined;
// → 설계도 유지, 값만 비움 (빠름)

// ❌ 사례 3: 동적으로 많은 프로퍼티를 추가할 때
const obj = {};
for (let i = 0; i < 100; i++) {
  obj[`prop_${i}`] = i;
  // 프로퍼티가 추가될 때마다 새 설계도 생성
  // 너무 많아지면 V8이 포기 → 딕셔너리 모드
}

딕셔너리 모드는 말 그대로 일반적인 해시 테이블 구조로 동작한다. 동작은 하지만 히든 클래스 최적화를 받는 것보다 프로퍼티 접근이 느려진다.

인라인 캐싱 (Inline Caching)

V8은 히든 클래스와 함께 인라인 캐싱(IC)이라는 최적화도 사용한다. 같은 히든 클래스의 객체를 반복 접근하면, V8이 프로퍼티 위치를 기억해서 다음에는 탐색 없이 바로 접근한다.

const getScore = (student) => student.score;

// 첫 번째 호출: student.score의 위치를 찾아서 캐싱
getScore({ name: '영희', score: 92 });

// 두 번째 호출: 같은 히든 클래스 → 캐시 히트! 바로 접근
getScore({ name: '민수', score: 85 });

// 다른 형태의 객체가 들어오면: 캐시 미스 → 다시 탐색
getScore({ score: 78, name: '철수' }); // 순서가 다름!

이것이 함수에 같은 형태(shape)의 객체를 전달 하는 것이 성능상 유리한 이유다.

Map — 처음부터 해시 테이블로 설계된 자료구조

ES6(2015년)에 도입된 Map은 처음부터 해시 테이블로 설계되었다.

기본 사용법

const map = new Map();

// 저장 (set)
map.set('name', '영희');
map.set('score', 92);

// 조회 (get)
map.get('name'); // '영희'
map.get('score'); // 92

// 삭제 (delete)
map.delete('score');

// 크기 확인
map.size; // 1

// 존재 여부 확인
map.has('name'); // true

객체와의 핵심 차이

키 타입

객체의 키는 항상 문자열(또는 Symbol)로 변환된다. Map은 모든 타입을 키로 사용할 수 있다.

// 객체: 키가 항상 문자열로 변환됨
const obj = {};
obj[1] = 'one';
obj['1'] = 'one string';
console.log(obj[1]); // 'one string' — 숫자 1이 문자열 '1'로 변환되어 덮어씀!

// Map: 키 타입이 그대로 유지됨
const map = new Map();
map.set(1, 'one');
map.set('1', 'one string');
console.log(map.get(1)); // 'one' — 숫자 1과 문자열 '1'은 별개!
console.log(map.get('1')); // 'one string'
// Map은 객체도 키로 사용 가능
const userA = { id: 1 };
const userB = { id: 2 };

const permissions = new Map();
permissions.set(userA, ['read', 'write']);
permissions.set(userB, ['read']);

permissions.get(userA); // ['read', 'write']

프로토타입 오염

// 객체: 기본적으로 프로토타입 프로퍼티가 존재
const obj = {};
console.log(obj.toString); // [Function: toString] — 만든 적 없는데 있다!
console.log(obj.constructor); // [Function: Object]

// 만약 키로 'toString'을 사용하면?
obj.toString = '데이터';
// → 기본 메서드를 덮어써서 예상치 못한 버그 발생 가능

// Map: 깨끗한 상태로 시작
const map = new Map();
map.get('toString'); // undefined — 아무것도 없다. 안전!

순서 보장

// Map: 삽입한 순서 그대로 반복
const map = new Map();
map.set('c', 3);
map.set('a', 1);
map.set('b', 2);

for (const [key, value] of map) {
  console.log(key, value);
}
// c 3
// a 1
// b 2  ← 넣은 순서 그대로!

객체도 ES2015부터 프로퍼티 순서가 부분적으로 보장되지만, 정수 키는 오름차순으로 먼저 정렬되는 등 직관적이지 않은 규칙이 있다.

const obj = {};
obj['b'] = 2;
obj['1'] = 'one';
obj['a'] = 1;
obj['2'] = 'two';

Object.keys(obj); // ['1', '2', 'b', 'a'] — 정수 키가 먼저 오름차순으로!

크기 확인

// 객체: 직접 계산해야 함
const obj = { a: 1, b: 2, c: 3 };
Object.keys(obj).length; // 3 — 모든 키를 배열로 만든 다음 길이를 셈 (느림)

// Map: 바로 확인 가능
const map = new Map([
  ['a', 1],
  ['b', 2],
  ['c', 3],
]);
map.size; // 3 — 항상 추적하고 있어서 즉시 반환 (O(1))

추가/삭제 성능

// ❌ 객체: delete가 히든 클래스를 깨뜨려서 점점 느려짐
const cacheObj = {};
cacheObj['key1'] = 'data1';
delete cacheObj['key1']; // 히든 클래스 깨짐!
cacheObj['key2'] = 'data2';
delete cacheObj['key2']; // 더 느려짐...

// ✅ Map: 추가/삭제가 처음부터 최적화되어 있음
const cacheMap = new Map();
cacheMap.set('key1', 'data1');
cacheMap.delete('key1'); // 해시 테이블에서 깔끔하게 제거
cacheMap.set('key2', 'data2');
cacheMap.delete('key2'); // 성능 일정하게 유지

차이 요약

특성객체 {}Map
키 타입문자열/Symbol만모든 타입 (객체, 함수 등)
순서 보장부분적 (정수 키 우선)삽입 순서 완전 보장
크기 확인Object.keys(o).lengthmap.size (O(1))
반복간접적 (for...in, Object.keys)직접 이터러블 (for...of)
프로토타입 오염toString 등 기본 키 존재없음
빈번한 추가/삭제느림 (히든 클래스 깨짐)빠름 (해시 테이블 최적화)
JSON 직렬화JSON.stringify 직접 지원직접 지원하지 않음

WeakMap — 메모리 누수를 방지하는 Map

Map과 비슷하지만, 키가 가비지 컬렉션의 대상이 될 수 있는 특수한 자료구조다.

// Map: 키로 사용된 객체는 Map이 존재하는 한 메모리에 유지됨
const map = new Map();
let user = { name: '영희' };
map.set(user, '데이터');
user = null; // user 변수는 비웠지만, Map이 참조하고 있어서 객체는 메모리에 남음

// WeakMap: 키로 사용된 객체에 대한 참조가 없어지면 자동으로 제거됨
const weakMap = new WeakMap();
let user2 = { name: '민수' };
weakMap.set(user2, '데이터');
user2 = null; // 다른 참조가 없으면 가비지 컬렉션 대상 → WeakMap에서도 자동 제거

DOM 요소에 데이터를 연결할 때 WeakMap이 유용하다. 요소가 DOM에서 제거되면 관련 데이터도 자동으로 정리된다.

const elementData = new WeakMap();

const setup = (element) => {
  elementData.set(element, { clickCount: 0 });
};

const handleClick = (element) => {
  const data = elementData.get(element);
  data.clickCount += 1;
};

// element가 DOM에서 제거되면 → 참조 사라짐 → WeakMap에서 자동 정리
// 메모리 누수 걱정 없음

실무 선택 기준

객체를 쓰면 좋은 경우

// 1. 구조가 미리 정해진 데이터
const config = { theme: 'dark', locale: 'ko', fontSize: 16 };

// 2. JSON으로 주고받는 API 응답
const response = { status: 200, data: { id: 1, name: '영희' } };

// 3. 함수의 옵션 파라미터
const createUser = (options: { name: string; age: number }) => {
  // ...
};

→ 프로퍼티가 고정적이고, 나중에 추가/삭제가 거의 없는 경우

Map을 쓰면 좋은 경우

// 1. 캐시 — 데이터가 수시로 추가/삭제됨
const apiCache = new Map();
apiCache.set('/api/users', userData);
apiCache.delete('/api/users');

// 2. 카운터 — 동적인 키로 집계
const wordCount = new Map();
const words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple'];
words.forEach((word) => {
  wordCount.set(word, (wordCount.get(word) || 0) + 1);
});
// Map { 'apple' => 3, 'banana' => 2, 'cherry' => 1 }

// 3. DOM 요소에 데이터 연결 — 객체를 키로 사용
const elementState = new Map();
const button = document.querySelector('#myButton');
elementState.set(button, { clickCount: 0, lastClicked: null });

// 4. 키가 문자열이 아닌 경우
const objectRelations = new Map();
const teamA = { name: 'Frontend' };
const teamB = { name: 'Backend' };
objectRelations.set(teamA, teamB);

→ 데이터가 동적으로 변하거나, 키가 문자열이 아니어야 하는 경우

판단 흐름

키-값 데이터를 저장해야 한다
         │
         ├─ 키가 문자열이 아닌 타입이 필요한가? ──── Yes ──▶ Map
         │
         ├─ 데이터 추가/삭제가 빈번한가? ──── Yes ──▶ Map
         │
         ├─ JSON 직렬화가 필요한가? ──── Yes ──▶ 객체
         │
         ├─ 키에 대한 참조가 사라지면
         │  데이터도 자동 정리되어야 하는가? ──── Yes ──▶ WeakMap
         │
         └─ 구조가 고정적이고 간단한가? ──── Yes ──▶ 객체

정리

해시 테이블은 키를 숫자로 변환하여 배열 인덱스로 사용함으로써 O(1) 조회를 가능하게 하는 자료구조다.

JavaScript에서 이 개념은 두 가지 형태로 나타난다.

핵심은 객체 = 해시 테이블이 아니라, V8이 상황에 따라 최적화 전략을 바꾼다는 점이다. 이 차이를 이해하면 어떤 상황에서 무엇을 써야 하는지 근거 있는 선택을 할 수 있다.

참고 자료

공식 문서

V8 엔진 내부 동작

해시 테이블 자료구조