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

"O(1) 조회는 영원히 공짜가 아니야 — 너무 붐비기 전에 해시맵이 조용히 자기를 키워서 지키는 약속이야. 키우는 걸 멈추면 약속이 깨져."

부하율

부하율 (load factor) 은 저장된 항목 대 가용 슬롯의 비율이야: load = entries / slots. 해시맵 건강을 예측하는 단 하나의 숫자야. 낮은 부하 (가령 0.3) 에선 키가 얇게 퍼져, 충돌이 드물고, 조회가 깔끔하게 O(1). 부하가 1 쪽으로 오르면, 슬롯이 차고, 충돌이 쌓이고, 체인이 길어지고 (또는 탐사 순서가 늘어나고), 네 O(1) 이 조용히 O(n) 쪽으로 썩어. 부하율은 계기판의 게이지야 — 그걸 보면 맵이 건강한지 알아.

고침: 키우고 리해시

부하율이 임계값을 넘으면, 맵이 리사이즈해: 더 큰 테이블 (보통 두 배) 을 할당하고 기존 모든 항목을 거기로 리해시해. 왜 복사 말고 리해시? 슬롯 인덱스가 hash % size 인데 size 가 방금 바뀌어서 — 모든 키가 새 테이블용으로 인덱스를 다시 계산해야 해. 리해싱은 O(n) 연산이야. 근데 — 이 영화 정확히 봤지 — 테이블이 두 배가 되니까, 리사이즈가 지수적으로 덜 일어나, 그래서 모든 삽입에 펴 바른 O(n) 비용이 삽입당 분할 상환 O(1) 으로 평균 나. Complexity 트랙의 동적 배열 두 배 하기 이야기가, 한 층 위에서 펼쳐지는 거야.

부하율 = 항목 ÷ 슬롯. 오르면 충돌이 오르고 O(1) 이 떨어져. 맵은 임계값을 넘으면 리사이즈 (두 배) 하고 리해시해서 부하를 낮게 유지해 — 그게 정확히 해시맵 삽입을 분할 상환 O(1) 으로 만드는 거야.

임계값이 앉는 자리

맞는 임계값은 충돌 전략에 달렸어. 체이닝은 1 넘는 부하를 견뎌 (체인이 좀 길어질 뿐), 그래서 더 차게 굴릴 수 있어. 개방 주소법은 차면 가파르게 떨어져 — 꽉 차기 직전 탐사 순서가 폭발 — 그래서 더 일찍 리사이즈해야 해; CPython 의 dict 는 부하를 대략 2/3 미만으로 유지해. 그 2/3 규칙이 정확히 Python dict 가 키 추가할 때 가끔 멈춰 리사이즈하는 이유고, 항목 수가 암시하는 것보다 눈에 띄게 메모리를 더 쓰는 이유야. 빈 슬롯은 낭비가 아니라 — 조회를 O(1) 로 유지하는 숨 쉴 공간이야.

피파의 고백

한 번 삽입할 항목 수에 정확히 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)' 조회가 이제 훑고 있음.
# 리사이즈 (크기 두 배 -> 부하 ~0.5 로 떨어짐) 가 짧은 탐사를 회복.

Exercise

해시맵이 부하율이 0.66 을 넘을 때마다 리사이즈 (두 배) 해. 처음에 작은 테이블에 1,000 개 키를 하나씩 삽입해. 대략 몇 번 리사이즈하고, 가끔의 O(n) 리해시에도 왜 각 삽입이 여전히 분할 상환 O(1) 이야? 이게 앞의 어느 lesson 이랑 같은 논증이야?

Hint

작은 시작에서 1000 키를 담게 두 배 하면 ~10 번 리사이즈 (2의 거듭제곱). 각 리해시가 O(n) 인데 지수적으로 덜 일어나서, 총 리해시 일이 n 삽입에 펴 발라져 ~O(n) = 분할 상환 O(1) — Complexity 트랙 동적 배열 append 랑 동일한 논증.

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

부하율

고침: 키우고 리해시

임계값이 앉는 자리

피파의 고백

Code

External links

Exercise

Progress

댓글 0