1.2 자료구조의 메모리 배치 — 같은 이름, 다른 실체

자료구조의 성능은 API가 아니라 메모리에 놓이는 모양이 결정한다. 이 문서는 배열·연결 리스트·해시 테이블·트리가 실제로 메모리에 어떻게 배치되는지 세우고, 언어 런타임(V8·CPython·JVM)이 같은 이름의 자료구조를 다르게 구현하는 지점을 확인한 뒤, 접근 패턴을 근거로 자료구조를 선택하는 기준을 만든다. 측정 방법론과 하네스는 1.1 복잡도 분석과 벤치마크의 것을 그대로 쓴다.

학습 목표

• 배열·연결 리스트·해시 테이블·트리·힙의 메모리 배치를 그리고, 각 연산의 비용을 배치로부터 유도해 설명한다.
• "연결 리스트 삽입은 O(1)이라 배열보다 빠르다"는 통념을 실측으로 반증하고, 연결 리스트가 정당화되는 조건을 판단한다.
• 해시 테이블의 충돌 처리·load factor·해시 함수 품질이 성능과 보안(HashDoS)에 미치는 영향을 설명한다.
• V8 elements kinds, CPython list/dict, JVM 컬렉션의 구현 차이를 근거로 런타임별 자료구조 동작을 예측한다.

배경: 왜 이것이 존재하는가

자료구조 교과서의 그림은 대체로 추상 자료형(abstract data type)의 그림이다. "리스트", "맵", "집합"은 연산의 계약이지 메모리 배치가 아니다. 같은 계약을 연속 메모리로도, 포인터로 연결된 노드로도, 해시 버킷으로도 구현할 수 있고, 1.1에서 본 대로 그 선택이 실측 성능을 두 자릿수 배율로 가른다.

문제는 고수준 언어가 이 선택을 이름 뒤에 숨긴다는 점이다. JavaScript의 Array는 C의 배열이 아니며, 심지어 같은 Array 객체가 상황에 따라 연속 메모리였다가 해시 테이블로 바뀐다. Python의 list는 연결 리스트가 아니라 포인터의 동적 배열이다. Java의 HashMap은 버킷이 리스트였다가 트리로 변한다. 이름만 보고 교과서의 비용 모델을 적용하면 예측이 틀린다.

그래서 이 문서는 자료구조를 두 층으로 나눠 본다. 불변식(invariant, 이 구조가 항상 유지하는 성질 — "정렬되어 있다", "부모가 자식보다 작다")과 메모리 배치(그 불변식을 어디에 어떤 모양으로 저장하는가). 연산 비용은 이 둘에서 유도되고, 런타임별 차이는 대부분 배치 층의 차이다.

핵심 개념

배열 — 주소 계산이 O(1)의 정체

배열의 임의 접근이 O(1)인 이유는 마법이 아니라 산술이다. 원소가 같은 크기로 연속 배치되어 있으면 i번째 원소의 주소는 base + i × size로 계산된다. 메모리 접근 한 번, 곱셈과 덧셈 한 번 — 어떤 탐색도 필요 없다. 이 성질은 연속 배치에서만 나오므로, 연속성을 깨는 순간(중간 삽입, 구멍) 배열의 장점도 같이 깨진다.

동적 배열(dynamic array)은 여기에 성장 정책을 얹은 것이다. 원소 수(length)와 확보한 공간(capacity)을 분리하고, 공간이 차면 더 큰 공간을 할당해 복사한다. push가 amortized O(1)인 근거는 1.1에서 계산했다. 성장 계수는 런타임마다 다르며, 집필 시점의 소스 기준으로 다음과 같다.

런타임	구조	성장 정책 (근사)
V8 (JS Array)	연속 elements 저장소	기존 용량 × 1.5 + 16
CPython (list)	PyObject*의 동적 배열	기존 크기 × 약 1.125 + 상수
OpenJDK (ArrayList)	Object[]	기존 용량 × 1.5

계수가 클수록 재할당이 드물어 복사 총량이 줄고, 작을수록 낭비 공간이 줄어든다. CPython의 보수적인 계수는 메모리 절약을, V8과 JVM의 1.5는 균형을 택한 것이다. 어느 쪽이든 amortized O(1)은 유지된다(기하급수 합의 성질).

중간 삽입은 O(n)이다 — 삽입 지점 뒤의 모든 원소를 밀어야 하기 때문이다. 여기서 흔한 추론이 "그럼 삽입이 잦으면 연결 리스트"인데, 이 추론을 다음 절에서 실측으로 검증한다.

연결 리스트 — O(1) 삽입이라는 통념의 검증

연결 리스트(linked list)의 노드는 힙에 개별 할당된 객체이고, 순서는 포인터가 만든다. 노드를 이미 손에 쥐고 있다면 그 앞뒤에 끼워 넣는 것은 진짜 O(1)이다. 문제는 실무의 삽입이 대부분 "k번째 위치에" 혹은 "이 값 앞에"이고, 그 위치까지 **도달하는 비용이 O(n)**이라는 점이다. 결국 배열도 리스트도 임의 위치 삽입은 O(n)이고, 승부는 상수 인자로 넘어간다 — 배열의 O(n)은 연속 메모리 복사(memmove, 캐시·프리페처에 최적)이고, 리스트의 O(n)은 포인터 추적(접근마다 캐시 미스 가능성)이다. 이 차이를 만드는 하드웨어 메커니즘은 7.2 메모리 계층과 캐시 일관성에서 다룬다.

Stroustrup의 고전 실험을 재현한다. 빈 시퀀스에서 시작해 3만 개의 원소를 매번 무작위 위치에 삽입한다.

// insert.mjs — node insert.mjs 로 실행
const N = 30_000;

const positions = [];
for (let i = 0; i < N; i++) positions.push(Math.floor(Math.random() * (i + 1)));

// 배열: splice가 뒤 원소를 연속 메모리 복사로 밀어낸다
{
  const start = performance.now();
  const arr = [];
  for (let i = 0; i < N; i++) arr.splice(positions[i], 0, i);
  console.log(`array splice insert: ${(performance.now() - start).toFixed(1)}ms`);
}

// 연결 리스트: 머리부터 위치까지 포인터를 따라간 뒤 O(1) 연결
{
  const start = performance.now();
  let head = null;
  for (let i = 0; i < N; i++) {
    const p = positions[i];
    const node = { value: i, next: null };
    if (p === 0) {
      node.next = head;
      head = node;
    } else {
      let cur = head;
      for (let k = 0; k < p - 1; k++) cur = cur.next;
      node.next = cur.next;
      cur.next = node;
    }
  }
  console.log(`linked list insert : ${(performance.now() - start).toFixed(1)}ms`);
}

Node.js v24.14.0(V8 13.6), Apple M5 Pro, macOS 26.5에서의 결과다.

구현	소요 시간
배열(splice)	21.3 ms
연결 리스트	371.1 ms (약 17×)

두 구현 모두 총 O(n²)인데 배열이 17배 빠르다. "삽입이 잦으니 리스트"라는 교과서 추론은 삽입 지점을 이미 알고 있다는 숨은 전제 위에서만 성립한다.

메모리 비용도 배치에서 유도된다. 같은 100만 개 정수를 담았을 때의 힙 사용량을 측정하면(node --expose-gc로 실행, GC 강제 후 process.memoryUsage().heapUsed 차이):

구조	힙 증가량	원소당
number[] (packed)	10.0 MiB	~10 B
연결 리스트 노드	38.1 MiB	~40 B
Map<number, number>	28.0 MiB	~29 B
Float64Array	힙 증가 ~0	8 B (힙 밖)

리스트 노드는 값 하나에 객체 헤더 + 필드 2개가 붙어 배열의 4배를 쓴다. Float64Array가 0으로 보이는 것은 측정 지표의 함정이다 — 데이터가 JS 힙 밖의 ArrayBuffer에 잡혀 heapUsed에 안 찍힌다(process.memoryUsage().arrayBuffers에 잡힌다). 지표가 무엇을 세는지 모르면 측정이 거짓말을 한다.

그럼에도 연결 리스트가 정당화되는 조건이 있다.

• 위치 핸들을 이미 들고 있는 경우. 대표 사례가 LRU 캐시다: 해시 맵이 키 → 노드 참조를 주므로 도달 비용이 없고, "이 노드를 맨 앞으로"가 진짜 O(1)이 된다. JS Map이 삽입 순서를 유지하는 것도 내부적으로 같은 발상이다.
• 원소 이동 비용이 큰 경우. 이동이 금지되거나(다른 곳에서 주소를 참조) 복사가 비싼 대형 객체.
• 잦은 분리·접합. 리스트 두 개를 O(1)에 잇는 연산이 핵심인 워크로드.

이 조건들이 없다면 기본값은 배열이다.

해시 테이블 — 평균 O(1)의 조건과 대가

해시 테이블은 키를 해시 함수에 넣어 버킷 배열의 인덱스로 바꾼다. 평균 O(1)은 두 가지 조건 위의 보장이다: 해시 함수가 키를 고르게 분산시키고, 원소 수 대비 버킷 수의 비율(load factor)이 일정 이하로 유지된다.

충돌 처리 방식이 메모리 배치를 가른다.

• 체이닝(separate chaining): 같은 버킷의 원소를 리스트로 연결한다. 구현이 단순하고 삭제가 쉽지만, 체인 순회는 포인터 추적이다. OpenJDK HashMap이 이 방식이며, 한 버킷의 체인이 8을 넘으면 레드-블랙 트리로 바꿔 최악을 O(log n)으로 막는다. 소스 주석에 근거가 있다 — 좋은 해시라면 체인 길이는 포아송 분포를 따라 길이 8에 도달할 확률이 약 천만분의 6이므로, 트리화는 "해시가 나쁠 때"만 작동하는 보험이다.
• 오픈 어드레싱(open addressing): 충돌 시 같은 배열의 다른 슬롯을 탐사(probing)한다. 모든 데이터가 한 배열에 있어 캐시 친화적이지만, load factor에 민감하고 삭제가 까다롭다(tombstone). CPython dict가 이 방식이다.
• load factor와 리사이징: 어느 방식이든 원소가 차면 더 큰 버킷 배열로 전체 재배치한다. 1.1에서 본 amortized 스파이크가 여기서도 발생한다 — 리사이징 순간의 삽입 한 번이 O(n)이다.

해시 함수의 품질은 보안 문제이기도 하다. 공격자가 같은 버킷으로 몰리는 키들을 계산해 요청에 실어 보내면, 서버의 해시 테이블이 O(n) 리스트로 퇴화해 CPU를 소진시킨다(HashDoS, 2011년 28C3에서 주요 웹 플랫폼 대상 시연). 대응으로 Python(3.4+, PEP 456)과 Rust는 키가 예측 불가능한 시드를 쓰는 SipHash 계열을 기본 해시로 채택했다. 해시 테이블용 해시는 "빠르고 고르게"가 목표라는 점에서 암호학적 해시와 목적이 다르다 — 후자는 챕터 3에서 다룬다.

스펙과 구현의 구분. ECMA-262는 Map에 특정 자료구조를 강제하지 않는다. 요구사항은 "평균적으로 원소 수에 대해 준선형(sublinear)인 접근 시간"과 삽입 순서 순회뿐이다. V8은 이를 삽입 순서를 보존하는 해시 테이블(deterministic/ordered hash table)로 구현한다. CPython도 3.6에서 dict를 인덱스 배열 + 엔트리 배열의 compact 구조로 재설계하면서 삽입 순서 보존이 부수효과로 생겼고, 3.7부터 언어 스펙으로 승격됐다. 순서 보존이 "스펙 보장"인지 "구현 세부"인지는 언어·버전에 따라 다르므로 의존하기 전에 확인해야 한다.

트리와 힙 — 불변식이 성능을 보장한다

이진 탐색 트리(BST)의 O(log n)은 트리가 균형일 때의 이야기다. 정렬된 순서로 삽입하면 트리는 한쪽으로 뻗은 연결 리스트로 퇴화하고 모든 연산이 O(n)이 된다. 균형 트리(AVL, 레드-블랙 트리)는 "좌우 부분 트리 높이 차 ≤ 1"(AVL), "루트에서 리프까지의 블랙 노드 수 동일"(레드-블랙) 같은 불변식을 삽입·삭제 때마다 회전으로 복구해, 높이가 O(log n)임을 구조적으로 보장한다. 회전의 케이스별 세부는 실무 판단에 기여하는 바가 적어 다루지 않는다 — 중요한 것은 불변식이 무엇을 보장하고, 그 유지비(회전, 상수 인자)를 누가 내는가다.

트리가 배열·해시에 대해 갖는 고유한 능력은 순서 있는 연산이다: 범위 질의(k 이상 m 이하), 최솟값/최댓값, 순서 순회. 키 조회만 필요하면 해시가 낫고, 순서가 필요하면 트리 또는 정렬 배열이 후보다.

힙(binary heap)은 "부모 ≤ 자식" 불변식만 유지하는 완전 이진 트리이고, 배치가 흥미롭다 — 포인터 없이 배열에 담는다. 인덱스 i의 자식은 2i+1, 2i+2, 부모는 (i-1)>>1로 산술 계산된다. 트리의 형태를 갖지만 메모리는 연속이라 캐시 친화적이다. 최솟값 꺼내기와 삽입이 O(log n)인 우선순위 큐의 표준 구현이며, 1.4의 다익스트라가 이것을 사용한다.

메모리 계층이 디스크로 확장되면 같은 논리가 트리의 모양을 바꾼다. 접근 단위가 캐시 라인(수십 바이트)이 아니라 디스크 페이지(수 KiB)가 되면, 노드 하나가 페이지 하나를 꽉 채우는 수백 갈래의 B-트리가 이진 트리를 대체한다. 데이터베이스 스토리지 엔진의 B-트리와 LSM 트리는 챕터 11에서 다룬다.

확률적 자료구조는 정확성을 공간과 바꾸는 별도의 축이다. Bloom filter는 "확실히 없다 / 아마 있다"만 답하는 대신 원소당 몇 비트로 집합 멤버십을 담고, HyperLogLog는 고유 원소 수를 KiB 단위 메모리로 근사한다. 대규모 데이터 처리에서 등장하며 여기서는 존재만 확인해 둔다.

런타임이 배치를 바꾸는 순간 — V8 elements kinds

JS Array는 스펙상 그냥 객체지만, V8은 내부적으로 원소 타입과 밀도에 따라 다른 배치(elements kind)를 쓴다. 작은 정수만 있으면 PACKED_SMI_ELEMENTS(태그된 정수의 연속 배열), 실수가 들어오면 PACKED_DOUBLE_ELEMENTS(unboxed double 배열), 그 외 값이 섞이면 PACKED_ELEMENTS(포인터 배열). 인덱스를 건너뛰어 구멍이 생기면 HOLEY_*로, 극단적으로 희소해지면 해시 테이블(dictionary mode)로 바뀐다. 전환은 한 방향이다 — 구멍을 도로 메워도, 실수를 도로 지워도 원래 kind로 돌아가지 않는다.

V8 내장 함수로 직접 관찰할 수 있다.

// elements-kinds.mjs — node --allow-natives-syntax elements-kinds.mjs 로 실행
// %로 시작하는 함수는 V8 내부 디버그 함수로, 프로덕션 코드에서는 사용할 수 없다.
const a = [1, 2, 3];
console.log('초기(정수만):     SMI =', %HasSmiElements(a), ', holey =', %HasHoleyElements(a));

a.push(4.5);
console.log('실수 추가 후:     DOUBLE =', %HasDoubleElements(a));

a.push('x');
console.log('문자열 추가 후:   OBJECT =', %HasObjectElements(a));

const b = [1, 2, 3];
b[10] = 4; // 인덱스를 건너뛰어 구멍 생성
console.log('인덱스 건너뛴 후: holey =', %HasHoleyElements(b));

const c = new Array(3); // 길이만 지정한 생성도 holey
console.log('new Array(3):     holey =', %HasHoleyElements(c));

초기(정수만):     SMI = true , holey = false
실수 추가 후:     DOUBLE = true
문자열 추가 후:   OBJECT = true
인덱스 건너뛴 후: holey = true
new Array(3):     holey = true

여기서 통념 재검증이 필요하다. "holey 배열 순회는 packed보다 훨씬 느리다"는 오래 회자된 조언인데, 같은 환경(Node.js v24.14.0)에서 완전히 채워진 holey 배열과 packed 배열의 숫자 합산을 1.1의 하네스로 측정하면 유의미한 차이가 없었다(0.56ms 대 0.54ms). SMI/DOUBLE/OBJECT kind 간 합산 차이도 이 패턴에서는 관찰되지 않았다. 수년 전 V8 블로그와 강연이 보여 준 차이를 현재의 최적화 파이프라인(특히 Maglev·TurboFan의 개선)이 상당 부분 흡수한 것이다. 이것이 1.1에서 말한 "수치의 시효"다 — elements kind 전환은 여전히 실재하고 관찰 가능하지만, 그 성능 영향은 버전과 패턴에 따라 다르므로 현재 런타임에서 재측정한 것만 믿는다. kind와 무관하게, 극단적 희소 배열이 dictionary mode로 떨어지면 접근이 해시 조회가 되는 것은 배치의 논리상 그대로다.

다른 런타임의 배치도 요약해 둔다.

• CPython list: 값이 아니라 PyObject* 포인터의 배열이다. 정수 100만 개의 리스트는 "연속 배열"이지만 실제 값은 힙에 흩어진 정수 객체들이고, 순회는 포인터 추적이다. 숫자 배열의 연속 배치가 필요하면 array 모듈이나 NumPy가 그 역할을 한다.
• JVM: int[]는 진짜 연속 원시 배열이지만 ArrayList<Integer>는 박싱된 객체 포인터의 배열이다. 객체마다 헤더(마크 워드 + 클래스 포인터)가 붙는 비용도 리스트 노드 실측(원소당 ~40B)과 같은 구조다.

공통 원리는 하나다. "배열"이라는 이름이 아니라, 값이 인라인으로 연속 배치되는지 포인터 뒤에 있는지가 성능을 가른다.

실무 관점

접근 패턴 → 자료구조 선택 기준

지배적인 접근 패턴	1순위 후보	근거
순차 순회, 인덱스 접근	배열 (숫자 대량이면 TypedArray)	연속 배치, 캐시·프리페처
키 → 값 조회	해시 맵	평균 O(1), 순서 불필요 시 최적
범위 질의, 정렬 순회, 최소/최대	정렬 배열(정적) 또는 균형 트리(동적)	순서 불변식
우선순위 최솟값 반복 추출	이진 힙	O(log n) + 배열 배치
끝에서만 추가/제거	배열(스택), 링 버퍼(큐)	JS에서 shift는 O(n)임에 주의
위치 핸들 보유 + 재배치 빈번	연결 리스트 (해시 맵과 조합)	LRU 패턴, 진짜 O(1) 삽입·삭제

• 작은 n에서는 표가 무의미하다. 원소 수십 개라면 어떤 구조든 캐시 몇 라인이고, 선형 탐색 배열이 해시 맵을 이기기도 한다. 판단이 필요하면 실제 n으로 측정한다(1.1 확인 문제 1).
• 수백만 개의 작은 객체는 구조 자체보다 박싱이 병목이 된다. {x, y, t} 객체 배열(AoS, array of structures) 대신 필드별 TypedArray(SoA, structure of arrays)로 바꾸면 메모리가 수 배 줄고 순회가 빨라진다. 객체 수가 줄면 GC 압력도 준다 — GC 비용 구조는 챕터 6에서 다룬다.

안티패턴

• 배열을 희소하게 쓰기: delete arr[i], 인덱스 건너뛰기, new Array(n) 후 부분만 채우기. holey 전환은 되돌릴 수 없고, 극단에서는 dictionary mode로 떨어진다. 제거는 splice나 스왑-팝으로, 크기 예약은 new Array(n) 대신 push 또는 Array.from으로 한다.
• Map이 필요한 자리에 일반 객체 쓰기: 키가 동적으로 추가·삭제되는 사전 용도라면 Map이 맞다. 객체는 hidden class(shape) 전환을 일으켜 프로퍼티 접근 최적화를 깨뜨리고, delete는 특히 비용이 크다. 고정된 형태의 레코드는 객체, 동적 사전은 Map으로 역할을 나눈다.
• 리사이징 스파이크 무시: 수백만 엔트리 해시 맵을 요청 경로에서 키운다면, 사전 크기 지정이 가능한 구조(JS Map은 불가 — 이것도 선택 기준이 된다)나 사전 워밍업을 검토한다.
• 측정 지표 오독: heapUsed는 ArrayBuffer 밖 메모리를 안 세고, RSS는 OS 캐시·단편화까지 섞인다. 메모리 주장을 하려면 지표의 정의부터 확인한다.

더 깊이

V8이 배열 외 객체 프로퍼티를 다루는 메커니즘(hidden class/shape, 인라인 캐시)은 자료구조라기보다 런타임 최적화의 주제라 챕터 5(인터프리터와 JIT)에서 상세히 다룬다. 여기서는 한 가지만 연결해 둔다 — 같은 형태의 객체를 같은 순서로 초기화하는 코드는 단형(monomorphic) 접근이 되어 빠르고, 형태가 섞이면 다형이 되어 느려진다. 자료구조 벤치마크에서 객체 형태를 통제하지 않으면 이 효과가 측정에 섞인다.

CPython dict의 compact 구조는 두 배열로 되어 있다: 해시 슬롯 → 엔트리 인덱스의 희소 배열(오픈 어드레싱)과, 삽입 순서대로 쌓이는 밀집 엔트리 배열. 조회는 희소 배열을 탐사하고, 순회는 밀집 배열을 순차로 읽는다 — 순회를 캐시 친화적으로 만들면서 순서 보존을 공짜로 얻은 설계다. Objects/dictobject.c 상단 주석에 설계 논의가 정리되어 있다.

정리

• 자료구조 = 불변식 + 메모리 배치. 연산 비용은 이 둘에서 유도되며, API 이름은 배치를 보장하지 않는다.
• 배열의 O(1) 접근은 연속 배치의 주소 산술이다. 연속성을 깨는 사용(희소화)은 장점도 같이 깬다.
• 임의 위치 삽입은 배열도 리스트도 O(n)이고, 실측은 배열이 17배 빠르다. 연결 리스트는 위치 핸들을 이미 쥔 경우(LRU 등)에만 정당화된다.
• 해시 테이블의 평균 O(1)은 해시 품질과 load factor 위의 조건부 보장이다. 최악 퇴화는 공격 벡터(HashDoS)이기도 하며, 리사이징은 꼬리 지연 스파이크를 만든다.
• 힙은 트리의 불변식을 배열의 배치에 담은 구조다. 순서 연산이 필요하면 트리, 키 조회만이면 해시, 기본값은 배열이다.
• 런타임은 배치를 동적으로 바꾼다(V8 elements kinds, dictionary mode). 전환 규칙은 관찰 가능하지만 성능 영향의 수치는 버전에 따라 변하므로 현재 런타임에서 재측정한다.

확인 문제

1. 실시간 대시보드가 센서에서 초당 수천 건의 {timestamp, value} 포인트를 받아 최근 100만 건을 유지하며 차트로 그린다. 현재 구현은 객체 배열에 push하고 오래된 것을 shift로 제거하는데, 메모리가 예상의 5배이고 주기적으로 프레임이 끊긴다. 배치 관점에서 원인 두 가지와 개선안을 제시하라.

정답과 해설

원인: (1) 포인트마다 객체 하나 — 객체 헤더와 포인터 간접 참조로 원소당 실 데이터(16B)의 몇 배를 쓰고, 100만 개의 수명 짧은 객체가 GC 압력을 만들어 프레임 드랍(주기적 끊김)의 유력한 원인이 된다. (2) shift는 배열 앞 원소 제거라 O(n) — 매 제거마다 100만 원소를 밀거나 그에 준하는 내부 작업이 발생한다. 개선: 필드별 Float64Array 두 개(SoA)를 고정 크기 링 버퍼로 운용한다. 메모리는 원소당 16B로 고정되고, 추가·제거는 인덱스 산술 O(1)이며, 객체가 사라져 GC 압력도 제거된다. 검증은 process.memoryUsage()(단, arrayBuffers 항목 포함)와 프레임 타임 측정으로 한다.

2. 코드 리뷰에서 "이 Map은 키가 최대 20개라 배열보다 느릴 수 있다"는 코멘트와 "해시 맵은 O(1)이니 무조건 Map이 맞다"는 반박이 충돌한다. 두 주장의 타당한 부분과 틀린 부분을 배치 관점에서 정리하고, 결론을 내리기 위한 절차를 제시하라.

정답과 해설

반박의 오류: O(1)은 상수 인자를 말하지 않는다. 20개 수준에서는 해시 계산 + 버킷 접근(캐시 미스 가능)의 고정 비용이, 캐시 한두 라인에 들어가는 배열의 선형 탐색보다 클 수 있다. 코멘트의 한계: "느릴 수 있다"는 가설일 뿐이고, 이 코드가 핫 패스가 아니라면 가독성·의도 표현이 우선이라 최적화 논쟁 자체가 불필요할 수 있다. 절차: (1) 이 조회가 성능에 유의미한 경로인지 프로파일로 확인한다. 아니라면 의미가 명확한 쪽(동적 키 사전이면 Map)을 쓰고 끝낸다. (2) 유의미하다면 실제 키 타입·개수·조회 패턴으로 1.1의 방법론에 따라 측정해 교차점을 확인한다. "무조건"이라는 단어가 들어간 성능 주장은 대부분 측정으로 대체되어야 한다.

3. Python 서비스에서 외부 입력을 키로 하는 dict에 수십만 건을 넣는 엔드포인트가 특정 요청 패턴에서만 CPU 100%로 치솟는다. 해시 테이블의 어떤 성질이 악용된 것인지 설명하고, 언어 런타임 차원의 방어와 애플리케이션 차원의 방어를 각각 제시하라.

정답과 해설

HashDoS다. 공격자가 같은 버킷으로 해시되는 키들을 만들어 보내면 dict가 O(n) 구조로 퇴화하고, 삽입마다 긴 충돌 체인을 타면서 총 O(n²) 작업이 된다. 런타임 방어: Python 3.4+는 PEP 456에 따라 str/bytes 해시에 무작위 시드 기반 SipHash를 쓰므로, 공격자는 시드를 모르면 충돌 키를 사전 계산할 수 없다(PYTHONHASHSEED로 시드 고정을 끄지 않았는지 확인). 단, int 키는 자기 자신이 해시라 이 보호 밖이다 — 외부 입력 정수를 그대로 키로 쓰면 여전히 충돌을 설계당할 수 있다. 애플리케이션 방어: 요청당 키 개수·크기 제한, 외부 입력을 직접 키로 쓰지 않고 서버 시드로 다시 해싱, 비정상 패턴의 요율 제한.

참고 자료

• V8 blog, Elements kinds in V8 — elements kind의 종류, 전환 격자, 한 방향 전환 규칙의 1차 자료. 성능 수치는 게시 시점 기준이므로 본문의 재측정 결과와 함께 읽는다.
• ECMA-262, Map Objects — Map에 요구되는 것이 자료구조가 아니라 "평균 준선형 접근"과 삽입 순서 순회임을 스펙 원문으로 확인.
• CPython, Objects/dictobject.c 상단 주석 — compact dict의 두 배열 구조와 설계 논의(1차 자료). Objects/listobject.c의 list_resize에서 성장 정책도 확인할 수 있다.
• OpenJDK, java/util/HashMap.java 구현 노트 주석 — 트리화 임계값 8의 포아송 분포 근거가 주석으로 남아 있는, 설계 근거 문서화의 모범 사례.
• Aumasson, Bernstein, SipHash: a fast short-input PRF — HashDoS 방어용 키드 해시의 원 논문. PEP 456과 함께 읽으면 채택 맥락이 보인다.
• Bjarne Stroustrup, Why you should avoid Linked Lists (GoingNative 2012) — 본문 삽입 실험의 원본. 벡터가 이기는 이유를 설계자의 언어로 설명한다.
• V8 blog, Maps (hidden classes) in V8 — 객체 프로퍼티 접근 최적화의 동작 모델. 챕터 5에서 심화한다.