해시 테이블 기반 자료구조(Map, Set)와 Array의 시간 복잡도 차이, 해시 함수의 동작 원리, 그리고 순회 시 캐시 지역성까지 정리합니다.
"Array 메서드 대신 Map, Set을 사용하여 최적화 하였습니다" 라고 말하면 가장 처음 생각나는 의문이 왜 Map, Set으로 대체하면 성능 최적화가 되는지입니다.
예를 들어
someArr.indexOf();
위 예시처럼 indexOf를 사용하여 특정 값을 "검색"할 때 많은 책,글에서 "그럴때는 Map or Set을 이용하여 최적화해라~" 라고 합니다.
그러면 그렇구나 하고 Map, Set으로 바꿉니다.
근데 한번쯤 이런 의문이 듭니다. -> 왜 Map, Set을 쓰면 최적화인가?
Map & Set은 해시 테이블 기반 자료구조입니다.
해시 테이블이란, 값을 저장할 "빈 칸(버킷)"들이 미리 준비된 자료구조입니다.
그리고 해시 함수란, key를 받아 저장 위치(숫자)를 반환하는 함수입니다.
실생활로 이해해보자면, 만약에 우리가 "해리포터 1권"이라는 제목의 책을 찾고 싶고, 그 책을 찾을 수 있는 공간이 2개 있다고 가정해봅시다.
공간 A는 책 1만 권이 0번 책부터 순서대로 꽂혀있는 공간입니다. 문제는 0번,1번,... 이 숫자를 부여한 게 우리가 아니라 자동으로 부여된 것이기 때문에, 우리가 해리포터 1권이라는 제목의 책을 찾는 유일한 방법은 0번 책부터 순서대로 확인하는 방법뿐입니다.
공간 B는 책 1만 권이 보관된 도서관입니다. 우리는 보통 도서관에서 책을 찾을 때 하나씩 꺼내서 확인하지 않습니다.
도서관의 검색 시스템에 우리가 찾는 해리포터 1권을 입력하면, 시스템이 "그 책은 B-2 위치에 존재합니다"라고 알려줍니다. 그러면 우리는 그곳으로 가서 꺼내기만 하면 됩니다.
위에서 비유한 공간 A가 Array이고, 공간 B가 해시 테이블 기반 자료구조입니다.
그리고 이것이 값 존재 확인 / 값 검색 / 값 삭제에서 Array보다 해시 테이블 기반 자료구조들이 빠른 이유입니다.
보통 js에서 Set, Map을 사용한다고 하면 가장 먼저 수행하는 작업이 아래처럼,
const set = new Set();
const map = new Map();
공간을 만드는 작업입니다. -> 여기서의 공간이 위에서 말한 해시 테이블입니다.
그리고 이제 특정 값을 찾을 때는 아래처럼 진행합니다.
const map = new Map();
map.set('해리포터 1권', { location: 'B-2' });
const bookName = '해리포터 1권';
// 존재 확인 + 조회: O(1)
if (map.has(bookName)) {
const book = map.get(bookName);
}
반면 Array는 아래처럼 진행합니다.
const books = [
'반지의 제왕',
'나니아 연대기',
'해리포터 1권' /* ... 9997권 더 */,
];
const bookName = '해리포터 1권';
// 존재 확인: 0번부터 순서대로 확인
const exists = books.includes(bookName); // O(n)
// 검색: 0번부터 순서대로 확인
const index = books.indexOf(bookName); // O(n)
// 삭제: 찾고 + 제거
const idx = books.indexOf(bookName);
if (idx !== -1) {
books.splice(idx, 1); // O(n)
}
Array는 "해리포터 1권"이 어디 있는지 모르기 때문에, 0번 인덱스부터 하나씩 확인해야 합니다.
반면 Map은 해시 함수가 "해리포터 1권"의 위치를 바로 계산해주기 때문에, 순회 없이 즉시 접근합니다.
위 설명대로라면 무조건 Map & Set을 사용하는 게 더 나은 방법 같아 보입니다.
근데 만약에 위에서 예로 든 도서관 예시에서 책이 1만 권이 아니라 3권만 존재한다면?
공간 A는 아무리 운이 안 좋아도 3번만 확인하면 됩니다.
공간 B는 1만 권이든 3권이든 찾으려는 책을 시스템에 입력하고, 시스템이 위치를 계산해서 답변해줘야 합니다.
이처럼 충분히 적은 양에서는 해시 계산 오버헤드 때문에 Array가 더 빠를 수 있습니다.
또 다른 경우가 있습니다. 모든 요소를 순회해야 하는 경우입니다.
// Array 순회
for (const book of books) {
console.log(book);
}
// Map 순회
for (const [key, value] of map) {
console.log(key, value);
}
둘 다 O(n)으로 모든 요소를 방문해야 하는 건 같습니다. 하지만 Array가 더 빠릅니다.
이유는 메모리 구조 차이입니다.
Array는 메모리에 연속적으로 저장됩니다. CPU가 데이터를 읽을 때는 "캐시 라인"(보통 64바이트) 단위로 가져오는데, 연속된 메모리라면 한 번에 여러 요소가 캐시에 올라옵니다.
반면 Map/Set은 해시 테이블 구조상 메모리가 흩어져 있을 수 있습니다. 그래서 매번 새로운 메모리 위치를 읽어야 하는 경우가 많습니다.
비유하자면:
저도 이런 최적화를 시도한 적이 있습니다.
TanStack Query의 useQueries에서 indexOf()를 WeakMap으로 바꿔 O(n) → O(1)로 개선하려는 PR을 제출했습니다.
// Before: O(n) 검색
const index = this.#observers.indexOf(observer);
// After: O(1) 조회
const index = this.#indexMap.get(observer);
이론적으로는 분명히 개선이었습니다. 하지만 실제 벤치마크 결과는 달랐습니다.
10,000개 쿼리 같은 극단적 케이스에서도 의미 있는 차이가 없었고, 오히려 WeakMap 버전이 약간 느린 경우도 있었습니다.
결국 PR은 닫혔고, 이 경험을 통해 **"이론적 시간 복잡도 개선 ≠ 실제 성능 향상"**이라는 것을 배웠습니다.
| 상황 | 추천 |
|---|---|
| 값 검색/존재 확인/삭제가 빈번 | Map / Set |
| 데이터가 매우 적음 (수십 개 이하) | Array |
| 전체 순회가 주 작업 | Array |
| 중복 제거가 필요 | Set |
| 순서가 중요하고 인덱스 접근이 많음 | Array |
"Map, Set으로 바꾸면 최적화"라는 말은 검색/존재 확인/삭제가 빈번한 경우에 해당합니다. 상황에 따라 적절한 자료구조를 선택하는 것이 진짜 최적화입니다.