해시 테이블은 왜 평균 O(1)이고, 언제 아닌가

해시 테이블의 평균 조회 시간이 O(1)이라는 건 다들 알지만, 면접에서 “왜 평균이고 최악은 언제 O(n)이 되나요”를 물으면 답이 갈립니다. 충돌 처리 방식을 알아야 답할 수 있는 질문입니다.

평균 O(1)이 성립하는 조건

해시 테이블은 키를 해시 함수로 정수 인덱스에 대응시켜 배열에 저장합니다. 인덱스 계산이 상수 시간이고, 그 인덱스에 값이 하나만 있다면 조회도 상수 시간입니다.

문제는 서로 다른 키가 같은 인덱스로 가는 경우, 즉 충돌입니다. 평균 O(1)은 다음 두 가지를 전제로 합니다.

• 해시 함수가 키를 버킷에 고르게 분산시킨다
• 적재율(load factor)이 일정 수준 아래로 유지된다

둘 중 하나가 깨지면 한 버킷에 값이 몰리고, 조회는 그 버킷을 선형 탐색하는 비용이 됩니다.

충돌 처리 두 갈래

체이닝

각 버킷이 연결 리스트를 들고 있습니다. 충돌하면 리스트에 덧붙입니다. 구현이 단순하고 적재율이 1을 넘어도 동작합니다. 대신 노드마다 포인터가 붙어 메모리를 더 쓰고, 참조가 흩어져 캐시 지역성이 나쁩니다.

최악의 경우는 모든 키가 같은 버킷으로 가는 상황이고, 조회는 O(n)이 됩니다.

오픈 어드레싱

충돌하면 다른 빈 버킷을 찾아 들어갑니다. 탐색 규칙이 선형 탐사, 이차 탐사, 이중 해싱 등으로 나뉩니다. 배열 하나에 값이 연속으로 놓이니 캐시 지역성이 좋습니다.

대신 적재율이 1을 넘을 수 없고, 0.7 근처만 가도 성능이 급격히 떨어집니다. 삭제도 까다롭습니다. 값을 그냥 비우면 탐사 경로가 끊겨서, 삭제 표식을 남기는 처리가 필요합니다.

Swift Dictionary는 어느 쪽인가

Swift 표준 라이브러리의 Dictionary는 오픈 어드레싱, 그중에서도 선형 탐사를 씁니다. 적재율이 임계치를 넘으면 버킷 배열을 키워 전체를 재해싱합니다.

var scores: [String: Int] = [:]
scores.reserveCapacity(1000)  // 재해싱 횟수를 줄인다

넣을 원소 개수를 미리 알고 있다면 reserveCapacity가 의미 있는 이유가 여기 있습니다. 재해싱은 모든 원소를 다시 배치하므로 O(n)이고, 이게 반복되면 삽입의 상각 비용이 올라갑니다.

Hashable을 직접 구현할 때 주의할 점

Hashable을 손으로 구현하면서 자주 나오는 실수가 있습니다.

struct User: Hashable {
    let id: UUID
    let name: String
    var lastSeenAt: Date   // 자주 바뀌는 값

    func hash(into hasher: inout Hasher) {
        hasher.combine(id)   // 불변 값만 넣는다
    }

    static func == (lhs: User, rhs: User) -> Bool {
        lhs.id == rhs.id
    }
}

hash(into:)에 넣는 값과 ==가 비교하는 값이 어긋나면 안 됩니다. 같다고 판정되는 두 값은 반드시 같은 해시를 내야 합니다. 그리고 자주 바뀌는 프로퍼티를 해시에 넣으면, 딕셔너리에 담아둔 뒤 그 값이 바뀌는 순간 키를 다시는 찾지 못합니다.

정리

항목	체이닝	오픈 어드레싱
평균 조회	O(1)	O(1)
최악 조회	O(n)	O(n)
적재율 1 초과	가능	불가능
캐시 지역성	나쁨	좋음
삭제	단순	표식 필요

“평균 O(1)“은 해시 함수가 제 역할을 하고 적재율이 관리될 때의 이야기입니다. 면접에서는 이 전제를 짚어주는 답이 훨씬 낫습니다.