10 · 컬렉션과 해싱

Array, Dictionary, Set는 실무에서 매일 쓰지만 "왜 빠른가"를 물으면 대답이 흐려지기 쉬운 자료구조다. 이 챕터는 append가 "평균적으로" O(1)이라는 말이 정확히 무엇을 뜻하는지, Dictionary/Set이 충돌을 처리하는 진짜 방식(체이닝이 아니다), 순회 순서가 실행마다 달라지는 이유, Hashable을 직접 구현할 때 지켜야 할 계약, 그리고 reserveCapacity·ContiguousArray가 실제로 이득이 되는 조건까지 — 전부 이 문서를 쓰면서 직접 돌려본 실측 수치로 확인한다.

Q1. Array의 append가 amortized O(1)이라는 말의 정확한 의미와, 그것이 깨지는 조건은?

원리

Apple 공식 문서는 append(_:)를 이렇게 설명한다: "Because arrays increase their allocated capacity using an exponential strategy, appending a single element to an array is an O(1) operation when averaged over many calls to the append(_:) method." 반면 insert(_:at:)는 뒤따르는 원소를 전부 한 칸씩 밀어야 해서 항상 O(n)이고, remove(at:)도 "뒤 원소를 앞으로 당겨 빈틈을 메운다"고 문서화돼 O(n)이다. 이 amortized 분석의 정확한 배수(정확히 2배인지, 다른 비율인지)는 표준 라이브러리가 공개로 보증하는 계약이 아니다 — swiftlang/swift의 설계 문서도 "amortized O(1) growth"라는 성질만 약속하고 정확한 성장 배수는 구현 세부사항으로 남겨둔다.

내부 동작

Array 값은 힙에 있는 버퍼 클래스 인스턴스를 가리키는 얇은 구조체다. mutating 메서드를 호출하면 먼저 isKnownUniquelyReferenced로 "이 버퍼를 나만 참조하고 있는가"를 검사한다. 그 다음 append 한 번은 두 경로 중 하나를 탄다. 용량이 남아 있고 나만 참조 중이면 그 자리에서 바로 써서 O(1). 용량이 꽉 찼다면(공유 여부와 무관하게) 더 큰 새 버퍼를 할당하고 기존 원소를 전부 복사해야 해서 그 한 번만 O(n). 그리고 용량이 남아 있어도 다른 변수가 같은 버퍼를 붙잡고 있다면(isKnownUniquelyReferenced가 false), 공유를 깨기 위해 어차피 새 버퍼로 복제해야 해서 이 역시 O(n)이다 — 이때는 용량 부족이 원인이 아니라 순전히 "공유 중"이라는 이유만으로 복제가 일어난다.

실험 · 도구

capacity가 실제로 몇 단위로 뛰는지는 Array.capacity를 append 루프 중간중간 찍어보면 바로 보인다. 아래는 이 문서를 쓰면서 로컬 Swift 6.2.1(arm64, macOS 26)에서 swift 파일명.swift로 직접 실행해 얻은 실측 결과다.

var a: [Int] = []
var lastCap = -1
for i in 0..<70 {
    a.append(i)
    if a.capacity != lastCap {
        print("count=\(a.count) capacity=\(a.capacity)")
        lastCap = a.capacity
    }
}
// 실측 출력:
// count=1 capacity=2
// count=3 capacity=4
// count=5 capacity=8
// count=9 capacity=16
// count=17 capacity=36
// count=37 capacity=76

주목할 점: 16 다음이 정확히 32가 아니라 36이고, 그 다음도 정확히 72가 아니라 76이다. "항상 2배"라는 통념과 다르게, 실제 성장 배수는 공개된 계약이 아닌 구현 세부사항이라 버전에 따라 달라질 수 있다는 걸 그대로 보여준다. 공유로 인한 복제는 withUnsafeBufferPointer로 버퍼 주소를 찍어 대입 전후를 비교하면 확인할 수 있다(01장 Q2에서 다룬 실험과 동일한 기법).

프로젝트 적용

① 최종 크기를 미리 알 수 있는 벌크 로드라면 reserveCapacity로 중간 재할당을 없앤다. 다만 그 이득의 실제 크기는 원소 타입에 따라 크게 갈리는데, 실측치는 Q5에서 다룬다.

func loadAllRows(count: Int) -> [Row] {
    var rows: [Row] = []
    rows.reserveCapacity(count)   // 중간 재할당을 미리 없앤다 — 실측은 Q5
    for i in 0..<count {
        rows.append(Row(id: i))
    }
    return rows
}

② 앞쪽에 계속 끼워 넣는 패턴(insert(_:at:0))은 amortized조차 아니라 매번 O(n)이다. 뒤에 append하고 필요할 때만 순서를 뒤집는 편이 총 비용이 훨씬 작다.

// ❌ 매번 맨 앞에 삽입 — 호출마다 O(n), 전체는 O(n²)
var recentBad: [LogLine] = []
func prependBad(_ line: LogLine) {
    recentBad.insert(line, at: 0)
}

// ✅ append는 amortized O(1) — 보여줄 때만 한 번 뒤집는다
var recentGood: [LogLine] = []
func appendGood(_ line: LogLine) {
    recentGood.append(line)
}
func displayOrder() -> [LogLine] {
    recentGood.reversed().map { $0 }   // 여기서만 O(n), 딱 필요한 순간에
}

꼬리 질문

Q2. Swift의 Dictionary/Set은 충돌을 어떻게 처리하는가? 최악의 경우는 언제 생기는가?

원리

두 방식은 충돌을 저장하는 위치 자체가 다르다. 체이닝은 버킷 배열의 각 칸이 "포인터 하나"이고, 충돌한 원소들은 그 포인터가 가리키는 별도의 연결 리스트(혹은 트리)에 쌓인다. 오픈 어드레싱은 버킷 배열 자체가 원소를 직접 담고, 충돌하면 정해진 탐사 규칙(선형 탐사면 "바로 다음 슬롯")을 따라 빈 슬롯을 찾아 그 자리에 저장한다. Apple 공식 문서는 "A dictionary is a type of hash table, providing fast access to the entries it contains"라고만 설명하고 구체적인 충돌 처리 알고리즘까지는 명시하지 않지만, Swift 표준 라이브러리 구현은 오픈 어드레싱 + 선형 탐사 계열이다.

내부 동작

Swift의 네이티브 해시 버퍼는 버킷 개수가 2의 거듭제곱인 배열과, "이 슬롯이 차 있는가"를 표시하는 별도의 비트맵으로 이뤄져 있다. 삽입·조회 모두 키의 해시값을 버킷 수로 마스킹해 시작 슬롯을 정하고, 그 슬롯이 이미 다른 키로 차 있으면 순서대로 다음 슬롯을 확인해 나간다(선형 탐사). 이 구조 덕분에 조회 경로는 포인터를 따라 이곳저곳 튀는 대신 연속된 배열 위를 움직이므로 캐시 지역성이 좋다. 반대로 해시값이 소수의 슬롯에 몰리면(나쁜 Hashable 또는 의도적 공격) 탐사가 사실상 배열 전체를 순차 스캔하는 것과 같아져 O(n)으로 저하된다. 채워지는 정도(load factor)가 임계치를 넘으면 더 큰 버킷 배열로 전체를 재구성하는 리해시가 일어나는데, 이 리해시 비용도 Array의 재할당처럼 amortized로 상각된다.

실험 · 도구

hash(into:)를 일부러 모든 값이 같은 해시로 뭉치게 구현하면, 조회가 사실상 배열 전체를 훑는 최악의 경우를 재현할 수 있다. 아래는 실제로 돌려서 얻은 실측치다.

struct GoodKey: Hashable { let v: Int }

struct BadKey: Hashable {
    let v: Int
    func hash(into hasher: inout Hasher) {
        hasher.combine(0)   // 모든 값이 같은 해시로 뭉친다 — 최악의 Hashable
    }
    static func == (l: BadKey, r: BadKey) -> Bool { l.v == r.v }
}

let n = 3000
// good hash, n=3000 삽입 3000회 + 조회 3000회: 0.001024 초
// bad hash(모두 충돌), 동일 작업: 0.026476 초  ← 약 26배 느림

키 3000개에 조회까지 포함한 이 작업이 나쁜 해시에서 약 26배 느려졌다 — 오픈 어드레싱에서 해시가 몰리면 탐사가 곧 선형 스캔이 된다는 것을 그대로 보여준다.

프로젝트 적용

① 커스텀 Hashable을 만들 때는 반드시 실제로 값을 구별하는 프로퍼티를 combine에 먹인다. 구별력 없는 해시는 성능을 이 실험처럼 떨어뜨린다(계약 위반 여부는 Q4에서 다룬다).

// 대부분은 이걸로 충분하다 — 컴파일러가 모든 저장 프로퍼티를 자동으로 combine한다
struct OrderKey: Hashable {
    let orderId: String
    let lineNumber: Int
}

② 삽입할 개수를 미리 안다면 init(minimumCapacity:)로 리해시 횟수를 줄인다.

var counts = [String: Int](minimumCapacity: 10_000)
for word in words {
    counts[word, default: 0] += 1
}

꼬리 질문

Q3. Set/Dictionary 순회 순서가 실행마다 달라지는 이유는? — SipHash 시딩과 SWIFT_DETERMINISTIC_HASHING

원리

Swift Forums의 stdlib 팀 공지는 이 설계를 명확히 설명한다: 해시 함수로 SipHash-1-3을 쓰고(구현 세부사항, 향후 바뀔 수 있음), 해시 플러딩 공격을 막기 위해 실행마다 랜덤 128비트 시드를 사용한다는 것이다. Hasher 공식 문서도 "같은 실행 내에서는 동일 입력이 항상 동일 해시값을 내지만, 실행마다 시드가 다시 부여돼 값이 달라지므로 해시값을 저장하거나 실행 간 비교하면 안 된다"고 명시한다.

내부 동작

런타임은 프로세스가 시작할 때 128비트 랜덤 시드를 한 번 만들어 그 프로세스의 모든 Hasher 인스턴스가 공유하는 SipHash 키로 쓴다. 여기서 한 걸음 더 들어가면: Swift 5부터는 컬렉션 인스턴스마다 자신이 쓰는 스토리지 버퍼의 메모리 주소까지 시드에 섞는다. 그래서 SWIFT_DETERMINISTIC_HASHING=1을 켜서 랜덤 시드를 고정해도, 서로 다른 프로그램(혹은 메모리 배치가 다른 두 실행)에서 완전히 같은 순회 순서를 재현하려면 "그 Set들이 정확히 같은 메모리 주소에 할당돼야" 하므로 사실상 보장되지 않는다. 이 환경 변수가 실제로 유용한 상황은 "같은 프로그램을 몇 번이고 다시 실행해도 항상 같은 순서가 나오게 해서 스냅샷 테스트를 안정시키는" 좁은 목적뿐이다.

실험 · 도구

같은 코드를 여러 번 실행해보면 바로 확인된다. 아래는 실제로 4번 실행해 얻은 결과다.

let s: Set<Int> = [1,2,3,4,5,6,7,8,9,10]
print(Array(s))

// 실행 1 (랜덤 시드): [1, 5, 2, 3, 7, 9, 4, 10, 8, 6]
// 실행 2 (랜덤 시드): [6, 3, 5, 9, 7, 8, 10, 4, 2, 1]
// 실행 3 (SWIFT_DETERMINISTIC_HASHING=1): [4, 2, 3, 6, 8, 5, 9, 1, 10, 7]
// 실행 4 (SWIFT_DETERMINISTIC_HASHING=1): [4, 2, 3, 6, 8, 5, 9, 1, 10, 7]  ← 3번과 동일

랜덤 시드일 때는 두 실행의 순서가 완전히 다르고, 환경 변수로 시드를 고정하면 같은 프로그램을 다시 돌려도 순서가 그대로 재현된다.

프로젝트 적용

① Dictionary/Set 내용을 JSON으로 내보내거나 UI 리스트로 보여줄 때는 절대 순회 순서를 그대로 쓰지 말고 명시적으로 정렬한다.

// ❌ 실행마다 다른 순서로 인코딩될 수 있다
let tags: Set<String> = ["swift", "ios", "network"]
let json = try JSONEncoder().encode(Array(tags))

// ✅ 정렬해서 실행에 상관없이 같은 순서를 보장
let sortedJSON = try JSONEncoder().encode(tags.sorted())

② 스냅샷 테스트나 골든 파일 비교에 Set/Dictionary 순회를 그대로 쓰면 CI가 랜덤하게 깨진다 — 비교 전에 항상 정렬한다.

func sameElements(_ a: Set<String>, _ b: Set<String>) -> Bool {
    a.sorted() == b.sorted()   // Array(a) == Array(b)는 순서가 달라 실패할 수 있다
}

꼬리 질문

Q4. Hashable을 직접 구현할 때 Hasher를 어떻게 써야 하고, 무엇을 하면 안 되는가?

원리

Hashable의 계약은 한 방향이다: a == b이면 반드시 a와 b의 해시가 같아야 한다(역은 필요 없다 — 해시가 같아도 ==가 거짓일 수 있고, 그게 바로 충돌이다). 이 계약이 깨지면 Set/Dictionary가 내부적으로 하는 최적화 — "같은 버킷·같은 탐사 경로에 있는 원소끼리만 ==로 최종 확인한다" — 자체가 무너진다. 해시가 다른데 실제로는 같은 값이면 애초에 같은 버킷을 찾아가지도 못하니 == 비교 기회조차 얻지 못한다.

내부 동작

Hasher는 Set/Dictionary가 조회할 때마다 내부적으로 새로 만들어 쓰는 값 타입이다. 사용 패턴은 var hasher = Hasher(); hasher.combine(x); let h = hasher.finalize()인데, Hashable을 채택하면 이 과정을 hash(into:) 하나로 합쳐서 쓴다 — finalize()는 컴파일러가 자동으로 호출해주므로 직접 부를 필요가 거의 없다. 여기서 "무엇을 combine해야 하는가"가 헷갈리기 쉬운데, 정확한 기준은 "그보다 적게 combine하는 건 괜찮지만(해시 분포만 나빠진다), 그보다 많이 combine하면 안 된다(계약 위반)"이다.

실험 · 도구

Set에 넣은 뒤 해시에 쓰이는 프로퍼티를 몰래 바꾸면 무슨 일이 생기는지 실제로 재현해봤다.

final class Tag: Hashable {
    var name: String
    init(_ name: String) { self.name = name }
    static func == (l: Tag, r: Tag) -> Bool { l.name == r.name }
    func hash(into hasher: inout Hasher) { hasher.combine(name) }
}

var set: Set<Tag> = [Tag("swift")]
let t = set.first!
t.name = "kotlin"   // Set에 넣은 뒤, hash(into:)가 쓰는 프로퍼티를 몰래 바꿔버린다
print("contains(t):", set.contains(t))
print("contains(kotlin):", set.contains(Tag("kotlin")))
print("contains(swift):", set.contains(Tag("swift")))
print("count:", set.count, "elements:", set.map { $0.name })

// 실측 출력:
// contains(t): false
// contains(kotlin): false
// contains(swift): false
// count: 1 elements: ["kotlin"]

t 자기 자신을 조회해도, 바뀐 이름("kotlin")으로 조회해도, 원래 이름("swift")으로 조회해도 셋 다 false다. 그런데 set.count는 여전히 1이고 map으로 직접 순회하면 "kotlin"이라는 원소가 실제로 들어 있다 — 존재는 하지만 어떤 조회로도 찾을 수 없는 원소가 만들어진 것이다. t는 옛 해시값이 가리키던 버킷 위치에 그대로 남아 있는데, 새 이름으로 계산한 해시는 다른 버킷을 가리키기 때문이다.

프로젝트 적용

① 여러 필드가 있는 타입에서 ==가 비교하는 필드와 hash(into:)가 combine하는 필드를 정확히 맞춘다. 가능하면 컴파일러 합성에 맡기는 편이 이 실수 자체를 원천 차단한다.

struct UserKey: Hashable {
    let id: String
    let displayName: String   // == 비교에는 쓰지 않는다

    static func == (l: UserKey, r: UserKey) -> Bool { l.id == r.id }
    func hash(into hasher: inout Hasher) {
        hasher.combine(id)          // ✅ ==가 실제로 비교하는 프로퍼티만 combine
        // ❌ hasher.combine(displayName) — ==는 무시하는데 해시는 달라져 버린다
    }
}

② Set/Dictionary에 넣은 값에서 hash(into:)가 참조하는 프로퍼티는, 그 값이 컬렉션 안에 있는 동안은 불변으로 취급한다. 꼭 바꿔야 한다면 꺼냈다가 바꾸고 다시 넣는다.

var tags: Set<Tag> = [Tag("swift")]
if let existing = tags.first(where: { $0.name == "swift" }) {
    tags.remove(existing)     // 먼저 꺼내고
    existing.name = "kotlin"  // 그 다음에 바꾸고
    tags.insert(existing)     // 새 해시 위치로 다시 넣는다
}

꼬리 질문

Q5. reserveCapacity와 ContiguousArray는 언제 실제로 이득인가?

원리

Array는 이미 "충분히 좋은" 기하급수적 성장 정책을 갖고 있으므로(Q1), reserveCapacity의 이득은 "재할당 이벤트 수(대략 log n번)를 얼마나 줄이느냐"가 아니라 "그 한 번 한 번의 재할당이 얼마나 비싼가"에 달려 있다. 원소가 순수 값 타입(ARC 없음)이면 재할당 시 복사는 그냥 memcpy라 몇 번 덜 하나 더 하나 차이가 크지 않다. 원소에 String이나 클래스 참조가 섞여 있으면, 재할당마다 기존 원소 전부를 retain/release하며 옮겨야 해서 그 비용이 실제로 드러난다. ContiguousArray는 Array와 저장 방식이 거의 같지만 NSArray 브릿징 지원 자체를 포기하는 대신, Element가 class/@objc 프로토콜일 때 있던 "브릿징 가능성 검사" 경로를 없애 더 예측 가능한 성능을 낸다 — Element가 struct/enum이면 그 검사 경로 자체가 애초에 없으므로 차이도 없다.

내부 동작

실측은 두 단계로 진행했다. 처음엔 순수 Int 배열로 swift(최적화 없이) 돌렸더니 차이가 거의 잡음 수준이었다. 그래서 -O로 최적화를 켜고, 복사 비용이 실제로 드는 String 필드가 섞인 struct로 다시 측정했다 — 이 과정 자체가 "벤치마크는 반드시 -O로, 그리고 원소가 무거운 케이스로 돌려야 진짜 신호가 보인다"는 교훈이다.

실험 · 도구

import Foundation
func time(_ label: String, _ block: () -> Void) {
    let start = Date()
    block()
    print("\(label): \(Date().timeIntervalSince(start))s")
}
let n = 300_000
time("append, no reserveCapacity") {
    var a: [Int] = []
    for i in 0..<n { a.append(i) }
}
time("append, reserveCapacity(n)") {
    var a: [Int] = []
    a.reserveCapacity(n)
    for i in 0..<n { a.append(i) }
}
// 실측(최적화 없음): 0.025367s vs 0.024960s — 차이는 잡음 수준

struct Rec { var a, b, c, d: Int; var s: String = "0123456789abcdef" }
let n2 = 2_000_000
time("Rec append, no reserve") {
    var a: [Rec] = []
    for i in 0..<n2 { a.append(Rec(a: i, b: i, c: i, d: i)) }
}
time("Rec append, reserveCapacity(n2)") {
    var a: [Rec] = []
    a.reserveCapacity(n2)
    for i in 0..<n2 { a.append(Rec(a: i, b: i, c: i, d: i)) }
}
// swift -O로 실행한 실측: 0.035768s vs 0.006719s — 약 5.3배

final class Box { var v = 0 }
let n3 = 1_000_000
let src = (0..<n3).map { _ in Box() }
time("Array<Box> sum") {
    var s = 0
    let arr = Array(src)
    for b in arr { s += b.v }
    _ = s
}
time("ContiguousArray<Box> sum") {
    var s = 0
    let carr = ContiguousArray(src)
    for b in carr { s += b.v }
    _ = s
}
// 실측: 0.013644s vs 0.008701s — 약 1.56배

프로젝트 적용

① 최종 크기를 알 수 있는 벌크 로드에서 무거운 원소(문자열·클래스가 섞인 struct)를 담을 때는 reserveCapacity를 꼭 쓴다. 순수 Int/Double 배열이라면 이득이 미미하니, 가독성을 해치면서까지 억지로 넣을 가치는 적다.

struct Row { let id: Int; let name: String; let email: String }

func parse(_ lines: [String]) -> [Row] {
    var rows: [Row] = []
    rows.reserveCapacity(lines.count)   // Row엔 String이 둘 — 재할당마다 ARC 트래픽이 실제로 든다
    for line in lines {
        rows.append(makeRow(from: line))
    }
    return rows
}

② 원소가 class(또는 @objc 프로토콜)이고 NSArray로 내보낼 일이 전혀 없는 순수 Swift 내부 컬렉션이라면 ContiguousArray로 선언해 브릿징 검사 경로를 원천적으로 없앤다. 값 타입 원소에는 바꿀 이유가 없다.

final class Particle {
    var x, y: Double
    init(x: Double, y: Double) { self.x = x; self.y = y }
}

// 시뮬레이션 내부에서만 도는, ObjC로 내보낼 일 없는 버퍼
var particles = ContiguousArray<Particle>()
particles.reserveCapacity(10_000)

꼬리 질문

출처 · 참고자료