13강 / 20강

해시 테이블 — 이름을 번호로 바꾸는 마법

딕셔너리와 집합이 그렇게 빠른 진짜 이유

4강과 5강에서 이상한 일이 있었습니다. 100만 개짜리 집합에서도 in 검사가 즉시 끝났죠. 전부 훑지도 않았는데 어떻게 알았을까요?

비밀은 찾지 않기입니다. 대신 계산해서 자리를 알아냅니다.

🔑

열쇠

"민준"

🧮

해시 함수

이름 → 숫자

🗄️

칸 번호

3번 칸

사물함에 물건을 넣을 때 이름을 계산기에 넣어 나온 번호의 칸에 넣습니다. 찾을 때도 같은 계산을 하면 바로 그 칸이 나오죠. 훑을 필요가 없습니다.

고등학생이름을 번호로 바꾸는 마법

4·5강에서 이상한 일이 있었죠. 집합과 딕셔너리가 너무 빨랐습니다.

비밀 — 찾지 않는다. 계산해서 바로 간다

해시 함수가 하는 일

"김민수" → (계산) → 3
"이서연" → (계산) → 7

단계	일
넣을 때	계산해서 3번 칸에 넣는다
찾을 때	계산해서 3번 칸을 본다

같은 입력은 항상 같은 번호 — 그래서 다시 찾을 수 있다

비유 — 옷 보관소

옷을 맡기면 번호표를 줍니다. 찾을 때는 번호표를 내밀죠.

	번호표 없이	번호표로
찾는 법	다 뒤진다	그 칸으로

다만 해시는 번호표를 주지 않고 옷 자체로 번호를 계산합니다.

번호표를 잃어버릴 걱정이 없다 — 다시 계산하면 되니까

해시 함수의 조건

조건	왜
빨라야	매번 계산하니까
고르게 퍼져야	한 칸에 몰리면 소용없다
같은 입력 = 같은 출력	다시 찾아야 하니까

세 번째 때문에 변하는 것은 열쇠가 못 된다 (4·5강)

이름 → 숫자. 이게 해시의 전부입니다.

Python 브라우저에서 실행

# 아주 단순한 해시 함수 만들어 보기
def 내해시(글자열, 칸수=8):
    합 = 0
    for 글자 in 글자열:
        합 += ord(글자)          # 글자를 숫자로 바꿔 더한다
    return 합 % 칸수             # 칸수로 나눈 나머지 = 칸 번호

for 이름 in ["민준", "서연", "지호", "하윤", "예준"]:
    print(f"{이름} → {내해시(이름)}번 칸")

print()
print("파이썬의 진짜 해시:")
for 이름 in ["민준", "서연"]:
    print(f"{이름} → {hash(이름)}")

🎮 해시 테이블 실험실

이름을 넣으면 어느 칸에 들어가는지 계산 과정과 함께 보여 줍니다. 칸 수를 줄여서 충돌을 일부러 만들어 보세요.

고등학생충돌 — 다른 이름이 같은 칸에

완벽해 보이는데 문제가 하나 있습니다.

서로 다른 열쇠가 같은 번호를 낼 수 있다

피할 수 없나

피할 수 없습니다. 수학적으로 불가능해요.

	개수
가능한 열쇠	무한
칸 개수	유한

무한을 유한에 넣으면 반드시 겹친다 — 비둘기집 원리

비유 — 생일이 같은 사람

한 반에 366명이 있으면 생일이 같은 사람이 반드시 있습니다. 날짜가 365개뿐이니까요.

사실 23명만 있어도 확률이 50% 를 넘습니다. 충돌은 생각보다 훨씬 자주 일어나요.

칸이 넉넉해도 충돌은 생긴다 — 대비해야 한다

해결 방법 두 가지

방법	어떻게
체이닝	같은 칸에 연결 리스트로 매단다
개방 주소법	다음 빈 칸을 찾아간다

8강의 연결 리스트가 여기서 실제로 쓰인다

그러면 속도가 어떻게 되나

상황	속도
충돌이 드물다	O(1) ✔
충돌이 많다	O(n) ⚠

"평균 O(1)" 이라 말하는 이유 — 최악은 O(n) 이다

고등학생충돌을 줄이는 법

충돌을 없앨 수는 없지만 줄일 수는 있습니다.

칸을 넉넉히 두고 해시를 고르게 만든다

적재율 — 얼마나 찼나

적재율	충돌
0.5 (절반)	드물다 ✔
0.75	보통 — 대개 이 선에서 늘린다
0.95	잦다 ⚠

칸이 차면 더 큰 표를 만들어 옮긴다 — 리해싱

리해싱은 비쌉니다

전부 다시 계산해서 옮겨야 하니까요.

동작	비용
보통 삽입	O(1)
리해싱이 일어나는 삽입	O(n) ⚠

평균하면 여전히 O(1) 이지만 가끔 크게 멈춘다

실시간 시스템에서 이게 문제가 됩니다. 평균은 빠른데 최악이 튀는 것이죠.

비유 — 이사

짐이 늘면 더 큰 집으로 이사합니다.

평소	이사하는 날
물건 하나 넣기만	전부 옮긴다

평균 비용은 낮지만 그날은 하루 종일 걸린다

해시가 고르지 않으면

나쁜 해시 함수의 예 — 글자 수로 번호를 만든다면?

이름	번호
김민수 · 이서연 · 박지훈	전부 3 ⚠

한 칸에 몰리면 연결 리스트가 되어 O(n)

그래서 좋은 해시 함수는 입력이 조금만 달라도 완전히 다른 번호를 냅니다.

파이썬 딕셔너리의 축소판. 칸 수를 2로 바꿔 충돌을 늘려 보세요.

Python 브라우저에서 실행

# 체이닝 방식으로 해시 테이블을 직접 만들어 봅니다
class 내딕셔너리:
    def __init__(self, 칸수=8):
        self.칸수 = 칸수
        self.칸 = [[] for _ in range(칸수)]      # 칸마다 리스트(=사슬)

    def _자리(self, 열쇠):
        return hash(열쇠) % self.칸수

    def 넣기(self, 열쇠, 값):
        사슬 = self.칸[self._자리(열쇠)]
        for ㅇ, (ㅋ, _) in enumerate(사슬):
            if ㅋ == 열쇠:
                사슬[ㅇ] = (열쇠, 값); return       # 이미 있으면 교체
        사슬.append((열쇠, 값))

    def 꺼내기(self, 열쇠):
        for ㅋ, ㅂ in self.칸[self._자리(열쇠)]:
            if ㅋ == 열쇠:
                return ㅂ
        raise KeyError(열쇠)

    def 보여주기(self):
        for ㅇ, 사슬 in enumerate(self.칸):
            표시 = " → ".join(f"{ㅋ}:{ㅂ}" for ㅋ, ㅂ in 사슬) or "(빈 칸)"
            print(f"  {ㅇ}번 칸: {표시}")

ㄷ = 내딕셔너리(칸수=5)
for 이름, 점수 in [("민준",95), ("서연",88), ("지호",76), ("하윤",91), ("예준",64), ("도윤",82)]:
    ㄷ.넣기(이름, 점수)

ㄷ.보여주기()
print()
print("서연의 점수:", ㄷ.꺼내기("서연"))

왜 열쇠가 '바뀌지 않는 값'이어야 할까요

5강의 그 규칙, 이제 이유를 알 수 있습니다. [1,2] 라는 리스트를 열쇠로 써서 3번 칸에 넣었다고 합시다. 그런데 누가 리스트를 [9,9] 로 바꿔 버리면? 이제 계산 결과가 7번 칸이 나옵니다. 물건은 3번 칸에 있는데 7번 칸을 찾게 되는 거예요. 영원히 못 찾습니다. 그래서 파이썬은 아예 바뀌는 값을 열쇠로 못 쓰게 막습니다.

좋은 해시 함수의 조건: 고르게 흩어 놓기.

Python 브라우저에서 실행

# 해시가 얼마나 고르게 흩어지는지 확인해 봅니다
import random, string

칸수 = 16
칸별개수 = [0] * 칸수
for _ in range(1600):
    낱말 = "".join(random.choices(string.ascii_lowercase, k=6))
    칸별개수[hash(낱말) % 칸수] += 1

print(f"낱말 1600개를 {칸수}칸에 흩뿌리면 (이상적으로는 칸마다 100개)")
for ㅇ, ㄱ in enumerate(칸별개수):
    막대 = "█" * (ㄱ // 5)
    print(f"  {ㅇ:2}번 |{막대} {ㄱ}")
print()
print("→ 좋은 해시 함수는 이렇게 '고르게' 흩어 놓습니다.")
print("→ 한 칸에 몰리면 그 칸의 사슬이 길어지고, 검색이 느려집니다.")

해시 테이블의 강점과 약점

	해시 테이블	이진 탐색 트리
찾기 · 넣기 · 지우기	⚡⚡ 즉시 (평균)	⚡ 높이만큼
정렬된 순서로 꺼내기	❌ 불가능	✅ 중위 순회
"30점~50점 사이" 찾기	❌ 전부 훑어야	✅ 범위 검색 가능
최악의 경우	😱 전부 한 칸에 몰리면 느려짐	😱 한쪽으로 쏠리면 느려짐

순서가 필요 없다면 해시, 순서나 범위가 필요하면 트리.

고등학생해시 테이블의 강점과 약점

note 의 정리를 선택 기준으로 바꿔 봅시다.

강점	약점
찾기 · 넣기 · 빼기 O(1)	순서가 없다
코드가 단순	범위 검색 불가
널리 쓰인다	메모리를 여유 있게 써야
—	최악은 O(n)

"하나를 정확히 찾기" 에는 최고, 나머지는 약하다

언제 해시를 쓰나

물음	해시가 좋은가
"이거 있나?"	최고 ✔
"이 열쇠의 값은?"	최고 ✔
"중복 제거"	최고 ✔
"가장 작은 것"	나쁘다 — 힙
"3~7 사이"	불가능 — 트리
"정렬해서 보기"	나쁘다 — 정렬

20강의 결론이 여기서 미리 보인다

파이썬 딕셔너리의 특별한 점

파이썬 3.7부터 딕셔너리는 넣은 순서를 기억합니다.

	보장하나
넣은 순서	그렇다 ✔
정렬된 순서	아니다 ✗

둘을 헷갈리면 안 된다 — 순서를 기억할 뿐 정렬은 아니다

집합은 어떤가

집합은 순서를 기억하지 않습니다. 같은 해시 테이블인데 보장이 다르죠.

"약속한 것" 만 믿는다 — 우연히 되는 것에 기대지 않는다

🤔 확인 문제

해시 테이블이 빠른 근본적인 이유는?

🤔 확인 문제

충돌(collision)이란?

🤔 확인 문제

"점수가 30점에서 50점 사이인 학생을 모두 찾기"에 알맞은 자료구조는?