Ch.3 해시맵과 해시셋

Python dict 내부 동작 — 왜 O(1)인가?

__hash__()와 __eq__()가 dict 조회에서 하는 역할을 설명한다Python dict의 리사이즈 전략과 메모리 최적화를 이해한다

우리가 매일 쓰는 dict, 안에서는 무슨 일이 벌어질까?

Python dict는 단순해 보이지만, 내부에는 정교한 해시 테이블이 동작합니다. __hash__ 매직 메서드와 open addressing 변형이 그 비밀입니다.

왜 리스트(list)는 O(n)인데 dict는 O(1)일까?

dict의 내부 배열, __hash__ 프로토콜, 그리고 perturbation probing을 들여다봅시다.

lightbulb

핵심 개념

hash

객체의 해시값을 반환하는 Python 매직 메서드

hashable

__hash__를 가진 불변(immutable) 객체

article

핵심 내용

Python에서 dict의 키가 되려면 hashable 해야 합니다

# hashable 객체 — dict 키 가능
print(hash("hello"))    # -1220129488 (실행마다 다를 수 있음)
print(hash(42))         # 42
print(hash((1, 2, 3)))  # 529344067

# unhashable 객체 — dict 키 불가!
try:
    hash([1, 2, 3])     # list는 mutable!
except TypeError as e:
    print(e)  # unhashable type: 'list'

dict 키가 될 수 있는 타입: str, int, float, tuple, frozenset dict 키가 될 수 없는 타입: list, dict, set 규칙: 불변(immutable) = hashable = 키 가능

dict 내부에는 두 개의 배열이 있습니다. 인덱스 배열 + 엔트리 배열

# Python 3.7+ dict 내부 (개념적)
# 1) 해시 인덱스 테이블 (sparse)
indices = [None, 1, None, 0, None, 2, None, None]
#           ↑         ↑         ↑
#           빈 슬롯    entries[0] entries[2]

# 2) 엔트리 배열 (compact, 삽입순 유지)
entries = [
    # (hash,      key,      value)
    (3450234,   "apple",    100),
    (8723091,   "banana",   200),
    (1293843,   "cherry",   300),
]

Python 3.7부터 dict가 삽입 순서를 유지하는 이유가 바로 이 compact 구조!

dict["banana"]를 호출하면 내부에서 무슨 일이 벌어질까요?

조회 3단계: ① hash(key) 계산 → 정수 ② 정수 % 테이블크기 → 인덱스 ③ 인덱스 → 엔트리 → 값 반환 각 단계 모두 O(1) → 전체도 O(1)!

데이터가 많아지면 dict는 자동으로 배열을 키웁니다

import sys

d = {}
print(f"빈 dict: {sys.getsizeof(d)} bytes")  # 64 bytes

for i in range(6):
    d[i] = i
print(f"6개: {sys.getsizeof(d)} bytes")       # 232 bytes

for i in range(6, 12):
    d[i] = i
print(f"12개: {sys.getsizeof(d)} bytes")      # 360 bytes
# → Load Factor 2/3 초과 시 자동 리사이즈!

내가 만든 클래스도 __hash__와 __eq__를 정의하면 dict 키가 됩니다

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __hash__(self):
        return hash((self.x, self.y))  # 튜플로 해싱

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

# 이제 dict 키로 사용 가능!
distance = {
    Point(0, 0): 0,
    Point(3, 4): 5,
}
print(distance[Point(3, 4)])  # 5

__hash__는 '어디서 찾을지', __eq__는 '정말 같은 키인지' 판단합니다

다음 중 dict의 키로 사용할 수 없는 것은?

Python dict는 Load Factor가 ___을 초과하면 리사이즈합니다. (분수로 입력, 예: "1/2")

dict의 내부를 해부했습니다

key

핵심 용어

#️⃣

hash

객체의 해시값(정수)을 반환하는 매직 메서드

🔒

hashable

해시값이 변하지 않는 불변 객체 (str, int, tuple 등)

📦

초기 크기

8 슬롯 (빈 dict 생성 시)

📈

리사이즈 조건

Load Factor > 2/3 일 때

✕2

확장 배율

현재 크기의 약 2~4배

♻️

재해싱

모든 키를 새 배열에 다시 배치

edit_note

정리 노트

Python dict 내부 동작

dict 키 조건

hashable: 불변 객체만 키 가능 (str, int, tuple, frozenset)
__hash__: 해시값(정수) 반환 — '어디서 찾을지' 결정
__eq__: 동등성 비교 — '정말 같은 키인지' 확인

내부 구조 (Python 3.7+)

인덱스 배열: sparse — 해시값 → 엔트리 위치 매핑
엔트리 배열: compact — (hash, key, value) 삽입순 저장
리사이즈: LF > 2/3 → 배열 2~4배 확장 + 재해싱

★

면접 핵심: 'dict는 왜 O(1)인가?' → 해시 → 인덱스 → 직접 접근!

image

시각 자료

다이어그램: ds-d25

check_circle

핵심 정리

1__hash__로 위치 계산, __eq__로 키 확인
2compact entries로 삽입 순서 보장 (Python 3.7+)
3LF > 2/3이면 자동 리사이즈 → amortized O(1)

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작