배열과 해시의 진짜 비용 - 이름과 비용: 자료구조 ep.02

배열은 빠릅니다. 그런데 어떤 연산에서 빠른지는 따져본 적이 잘 없습니다.

배열이 빠른 이유는 하나입니다

배열은 값을 연속된 메모리(contiguous memory) 에 나란히 둡니다. 원소 하나의 크기가 정해져 있으니 시작 주소에 인덱스를 곱해 더하면 원하는 위치가 바로 나옵니다. 원소 하나가 8바이트이고 시작 주소가 1000이면 인덱스 5의 주소는 1000 + 5 × 8 = 1040입니다.

계산 한 번이면 끝납니다. 원소가 열 개든 천만 개든 같은 계산입니다. 인덱스 접근이 O(1)인 건 이 구조에서 나오는 결과입니다.

그런데 이 성질이 다른 부분에서는 비용이 됩니다. 값들이 나란히 붙어 있으므로 중간에 하나를 끼워 넣으려면 뒤쪽 전부를 한 칸씩 밀어야 합니다. 맨 앞이면 전부 밀게 됩니다.

연산	복잡도	이유
인덱스 접근	O(1)	주소 계산 한 번
맨 뒤 추가	상각 O(1)	용량이 찰 때만 재할당
맨 뒤 제거	O(1)	이동 없음
맨 앞 추가	O(N)	전체를 뒤로 이동
맨 앞 제거	O(N)	전체를 앞으로 이동
값으로 탐색	O(N)	전부 확인

맨 뒤 추가가 상각 O(1)인 건 ep.01 크기가 접근법을 정한다에서 본 상각 분석 그대로입니다. 용량이 꽉 차면 더 큰 공간을 잡아 전부 복사하지만, 그 일이 드물게 일어나므로 여러 번의 추가에 나눠 보면 상수 시간입니다.

큐를 배열로 만들면 조용히 느려집니다

실무에서 가장 자주 발생하는 문제는 맨 앞 원소를 제거해야 하는 일입니다. 자바스크립트에서 큐(queue) 를 만들 때 흔히 이렇게 씁니다.

const queue = [];
queue.push(x);               // O(1)
const front = queue.shift(); // O(N)

동작은 맞습니다. 원소가 몇백 개일 때는 문제도 없습니다. 그런데 큐에 십만 개가 들어가 있으면 shift() 한 번마다 십만 번의 이동이 생기고, 전체로는 O(N²)이 됩니다.

에러가 나지 않고 그냥 느려집니다. 원인을 찾기 어려운 종류의 성능 문제가 여기서 나옵니다.

해결책은 배열을 그대로 두고 읽는 위치만 옮기는 겁니다.

class Queue {
  #items = [];
  #head = 0; // 다음에 꺼낼 위치

  enqueue(x) {
    this.#items.push(x);
  }

  dequeue() {
    if (this.#head >= this.#items.length) return undefined;
    const value = this.#items[this.#head];
    this.#items[this.#head] = undefined; // 참조를 끊어 회수 가능하게
    this.#head++;
    return value;
  }

  get size() {
    return this.#items.length - this.#head;
  }
}

꺼낸 자리를 비우지 않으므로 이동이 없습니다. 두 연산 모두 O(1)입니다. 대신 배열이 계속 커지니, 오래 도는 큐라면 #head가 일정 비율을 넘을 때 앞부분을 잘라내는 처리를 덧붙여야 합니다.

해시 테이블은 위치를 계산합니다

배열이 인덱스로 위치를 찾는다면, 해시 테이블(hash table) 은 키에서 위치를 계산합니다.

키를 해시 함수(hash function) 에 넣으면 정수가 나옵니다. 그 정수를 버킷 개수로 나눈 나머지가 저장 위치입니다. 조회할 때도 같은 계산을 하니 한 번에 자리를 찾습니다.

여기까지는 O(1)입니다. 문제는 서로 다른 키가 같은 위치로 계산되는 경우입니다.

충돌은 예외가 아니라 전제입니다

키의 가짓수는 무한한데 버킷은 유한합니다. 충돌(collision) 은 피할 수 있는 사고가 아니라 반드시 일어나는 해시 테이블의 사양입니다. 해시 테이블은 충돌을 없애는 대신 어떻게든 처리하는 방식으로 구현됩니다.

체이닝(chaining) 은 같은 버킷에 들어온 값들을 연결 리스트로 매답니다. 구현이 단순하고 삭제도 쉽습니다. 대신 노드마다 포인터가 붙어 메모리를 더 쓰고, 값들이 메모리 여기저기 흩어져 캐시 효율이 떨어집니다.

개방 주소법(open addressing) 은 자리가 차 있으면 다음 빈 칸을 찾아 들어갑니다. 추가 구조가 없어 메모리 효율과 캐시 지역성이 좋습니다. 대신 삭제가 까다롭습니다. 값을 그냥 비우면 그 자리를 지나 뒤에 들어간 값들을 찾지 못하게 되어, 삭제 표시를 따로 남겨야 합니다.

평균 O(1)이 깨지는 지점

해시 테이블의 성능을 결정하는 값이 적재율(load factor) 입니다. 저장된 원소 수를 버킷 수로 나눈 값입니다. 버킷 16개에 원소 12개가 들어 있으면 0.75입니다.

이 값이 커지면 충돌이 늘고 조회가 길어집니다. 그래서 대부분의 구현은 적재율이 일정 선을 넘으면 버킷을 늘리고 전부 다시 배치합니다. 리해싱(rehashing) 입니다. 이 순간 하나의 삽입이 O(N)을 씁니다.

최악의 경우는 모든 키가 같은 버킷으로 몰리는 상황입니다. 그러면 조회가 연결 리스트를 끝까지 훑는 O(N)이 됩니다. 저절로 생기기는 어렵지만, 외부 입력을 키로 쓰는 곳에서는 누군가 일부러 만들 수 있습니다. 해시 함수에 무작위 시드를 섞는 구현이 있는 이유가 여기에 있습니다.

정리하면 이렇게 읽습니다.

상황	조회	삽입
충돌이 적은 평상시	O(1)	O(1)
리해싱이 발생한 삽입	O(1)	O(N)
키가 한 버킷에 몰림	O(N)	O(N)

객체와 Map과 Set은 같지 않습니다

자바스크립트에서 키로 값을 찾는 수단은 일반 객체와 Map 둘이고, 값의 존재 여부만 다루는 Set이 따로 있습니다. 셋 다 평균 O(1)로 찾지만, 받는 키와 지불하는 비용이 다릅니다.

일반 객체는 모양이 고정된 데이터에 맞는 그릇입니다.

키: 문자열과 심볼만 받습니다. 숫자는 문자열로 바뀌고, 객체는 전부 "[object Object]"가 되어 서로 구분되지 않습니다
순서: 정수 모양의 키가 오름차순으로 먼저, 나머지는 삽입 순입니다
개수: Object.keys(obj).length로 키를 다 세야 하니 O(N)입니다
비용: 조회는 평균 O(1)입니다. 다만 키를 자주 추가하고 삭제하면 V8 같은 엔진은 최적화된 구조를 포기하고 사전 모드로 바꿔 조회가 느려집니다
주의: 프로토타입 체인이 있어서 toString 같은 상속된 이름과 부딪힐 수 있습니다
장점: 리터럴로 바로 쓰고 JSON으로 그대로 직렬화됩니다
용도: 필드가 정해진 레코드, 설정값

Map은 키가 바뀌는 데이터에 맞는 해시 테이블입니다.

키: 어떤 값이든 받습니다. 객체, 함수, NaN도 키가 되고, 값이 같은지(SameValueZero)로 비교합니다
순서: 삽입 순서를 그대로 유지합니다
개수: size로 O(1)에 얻습니다
비용: 조회·삽입·삭제가 평균 O(1)이고, 키가 자주 늘고 줄어도 비용이 그대로입니다
주의: JSON으로 바로 직렬화되지 않아 Array.from(map)으로 풀어야 합니다
장점: 프로토타입 충돌이 없습니다
용도: 문자열이 아닌 키, 실행 중에 계속 바뀌는 키 집합, 개수를 자주 묻는 캐시·카운팅·인덱스

Set은 값만 담고 같은 값은 한 번만 들어가는 집합입니다.

키: 키 없이 값만 담습니다. 비교 기준은 Map과 같습니다
순서: 삽입 순서를 유지합니다
개수: size로 O(1)에 얻습니다
비용: has·add·delete가 평균 O(1)입니다. 배열의 includes가 앞에서부터 전부 확인하는 O(N)인 것과 달리 has는 위치를 계산해 바로 찾기 때문에 O(1)입니다
주의: JSON 직렬화는 Map과 같이 변환이 필요합니다
장점: 중복 제거가 자동입니다
용도: 존재 여부 확인, 중복 제거, 방문 표시

	일반 객체	`Map`	`Set`
담는 것	키와 값	키와 값	값만
키 타입	문자열, 심볼	모든 값	모든 값
순서	정수 키 먼저, 나머지 삽입 순	삽입 순	삽입 순
개수	`Object.keys()` O(N)	`size` O(1)	`size` O(1)
조회·삽입·삭제	평균 O(1), 잦은 변경에 취약	평균 O(1)	평균 O(1)
프로토타입 영향	있음	없음	없음
JSON 직렬화	바로 됨	변환 필요	변환 필요
맞는 용도	모양이 고정된 레코드, 설정	동적인 키, 캐시, 카운팅	존재 확인, 중복 제거, 방문 표시

셋 중 하나를 고르는 기준은 무엇을 키로 쓰고 얼마나 자주 바뀌느냐입니다. 노드 객체의 등장 횟수를 세는 코드로 보면 차이가 드러납니다.

// 객체: 문자열이 아닌 키는 전부 "[object Object]"로 합쳐진다
const countByObj = {};
for (const node of nodes) countByObj[node] = (countByObj[node] ?? 0) + 1;

// Map: 객체를 그대로 키로 쓴다
const countByMap = new Map();
for (const node of nodes) countByMap.set(node, (countByMap.get(node) ?? 0) + 1);

존재 여부만 물을 때는 배열 대신 Set입니다.

// O(N * M): 배열에서 매번 선형 탐색
const result = items.filter((x) => blocked.includes(x.id));

// O(N): 집합으로 바꾸면 조회가 상수 시간
const blockedSet = new Set(blocked);
const result = items.filter((x) => blockedSet.has(x.id));

참고 자료

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
MDN Web Docs. Map. Mozilla. https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Map
MDN Web Docs. Array.prototype.shift(). Mozilla. https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/shift

다음 편 예고

ep.03 - 내장 정렬이 보장하는 것

정렬 함수를 직접 구현할 일은 거의 없습니다. 대신 내장 정렬이 무엇을 보장하는지는 알아야 합니다. 안정성이라는 성질이 다중 기준 정렬에서 어떻게 결정적으로 작용하는지 봅니다.