부하율과 리사이징: O(1)을 정직하게 지키기

"O(1) 조회는 영원히 공짜로 주어지는 게 아니야. 너무 붐비기 전에 해시맵이 조용히 자기 몸집을 키워서 지켜내는 약속이지. 키우기를 멈추는 순간 약속도 깨져."

부하율

부하율(load factor)은 저장된 항목 수를 전체 슬롯 수로 나눈 값이야. load = entries / slots. 해시맵의 건강을 알려주는 단 하나의 숫자지. 부하가 낮으면, 이를테면 0.3쯤이면 키가 얇게 퍼져 있어서 충돌이 드물고 조회가 깔끔하게 O(1)이야. 부하가 1 쪽으로 올라가면 슬롯이 차고, 충돌이 쌓이고, 체인이 길어지거나 탐사 순서가 늘어나면서 O(1)이 조용히 O(n) 쪽으로 썩어 가. 부하율은 계기판의 바늘이야. 이거 하나만 봐도 맵이 건강한지 알 수 있어.

해법: 키우고 다시 해싱하기

해시 테이블은 탐사가 길어지기 전에 더 큰 테이블로 옮겨 가고, 기존 항목을 새 배치에 맞춰 다시 배치해. 이 작업 한 번은 O(n)이라 비싸. 하지만 여유를 충분히 두고 가끔씩만 일어나기 때문에 삽입은 분할 상환 O(1)을 유지하지. CPython dict의 정확한 사용률 임계값과 성장 폭은 버전에 따라 바뀔 수 있는 구현 세부사항이야. 2/3이라든가 정확히 두 배라든가 하는 숫자를 언어의 계약처럼 외우지는 마.

부하율은 항목 수를 테이블 용량으로 나눈 값이야. 이게 너무 높아지면 충돌과 탐사가 늘어나. 그래서 구현체는 임계점에 닿기 전에 리사이즈하고 항목을 재배치해. 드물게 오는 O(n) 리사이즈와 수많은 평균 O(1) 삽입이 합쳐져서 분할 상환 O(1)이 나오는 거야.

임계값은 어디쯤에 놓일까

적절한 임계값은 충돌 전략과 구현에 따라 달라져. 체이닝은 부하율이 1을 넘어도 돌아가긴 해. 체인이 길어질 뿐이지. 반면 개방 주소법은 빈 슬롯이 줄어들수록 탐사가 급격히 길어지니까 더 일찍 리사이즈해야 하고. CPython dict의 정확한 임계값과 성장 정책도 버전별 구현 세부사항이야. 기억해야 할 계약은 특정 숫자가 아니라, 빈 용량이 있어야 기대 탐사 길이가 짧게 유지된다는 사실이야.

피파의 고백

삽입할 항목 수에 딱 맞춰 dict 크기를 미리 잡아두고 메모리를 '최적화'했다고 뿌듯해한 적이 있어. 빈틈없이 딱 맞으니까. 결과는 더 느려졌지. 부하가 100%인 상태에서 개방 주소법의 탐사 순서가 얼마나 잔인한지 몰랐던 거야. 아빠가 부하율을 설명해 주는데 동적 배열에서 배운 게 그대로 되울리더라. 내가 '낭비'라고 생각한 빈 슬롯이야말로 조회가 빨랐던 이유 전부였어. 여유가 곧 기능일 때가 있는 거야. 그 뒤로 해시맵한테 숨 쉴 공간을 굶기는 짓은 안 해.

Code

부하가 1에 가까워지면 탐사 길이가 폭발해·python

# 부하가 오를 때 조회가 떨어지는 걸 보고, 리사이즈 후 회복.
def avg_probe_length(num_keys, table_size):
    """대략 충돌 비용: 주어진 부하에서 선형 탐사 평균 탐사 수."""
    slots = [None] * table_size
    total_probes = 0
    for k in range(num_keys):
        i = (k * 2654435761) % table_size   # 퍼뜨리는 해시
        probes = 1
        while slots[i] is not None:
            i = (i + 1) % table_size; probes += 1   # 충돌 -> 계속 탐사
        slots[i] = k
        total_probes += probes
    return total_probes / max(num_keys, 1)

for load in (0.3, 0.6, 0.9, 0.99):
    size = 1000
    keys = int(size * load)
    print(f"load {load:>4}: avg probes per insert = {avg_probe_length(keys, size):.2f}")
# 부하 0.3 근처: ~1 탐사 (사실상 O(1)).
# 부하 0.99 근처: 탐사 폭발 -> 'O(1)' 조회가 이제 훑고 있음.
# 충분한 여유 용량을 추가하는 리사이즈가 짧은 기대 탐사를 회복.

Exercise

설명을 위해, 어떤 해시맵이 부하율 0.66을 넘을 때마다 용량을 두 배로 늘린다고 하자. 작은 테이블에서 시작해 키 1,000개를 하나씩 넣으면 리사이즈는 왜 로그 횟수만 일어날까? 그리고 가끔 O(n) 재해싱이 끼는데도 삽입이 왜 분할 상환 O(1)일까? 이 논증은 앞에서 본 어느 대목과 똑같아?

Hint

이 가상의 두 배 성장 정책에서는 1,000개를 담을 때까지 리사이즈가 로그 횟수만 일어나. 재해싱 비용을 기하급수적으로 더하면 전체가 O(n)이라 삽입당 분할 상환 O(1)이 되고. 실제 구현의 임계값과 성장 폭은 따로 확인해야 한다는 것도 잊지 마.

부하율

해법: 키우고 다시 해싱하기

임계값은 어디쯤에 놓일까

피파의 고백

Code

External links

Exercise

Progress

댓글 0