통합 요약노트
Ch.3 해시맵과 해시셋
해시 함수, 충돌 해결, 빈도수 세기 — O(1) 조회의 마법
이 챕터의 내용
해시 함수란? — 데이터를 주소로 바꾸는 마법
해시 함수가 키를 숫자로 바꾸고, 그 숫자가 곧 주소가 됩니다. 이것이 O(1)의 비밀입니다.
도서관에서 책을 찾는다고 생각해보세요. 모든 책을 하나하나 뒤질 건가요?
도서관에는 분류 번호가 있습니다. '813.6 한국소설' → 해당 서가로 직행!
해시 함수는 데이터의 '분류 번호'를 만드는 기계입니다
- 해시 함수 = 키 → 고정 크기 숫자 변환
- 해시 테이블 = 해시값을 인덱스로 쓰는 배열
- Python dict/set = 해시 테이블 기반 → O(1) 조회
해시 충돌과 해결 — Chaining vs Open Addressing
Chaining(연결 리스트)과 Open Addressing(빈자리 찾기), 두 전략으로 충돌을 관리합니다.
비둘기집 원리를 아시나요? 11마리 비둘기, 10개 집 → 최소 1개 집에 2마리!
"abc"와 "bac"는 다른 문자열이지만 같은 인덱스 4를 받았습니다!
해결법 ①: 같은 인덱스에 연결 리스트를 매달아 여러 값을 저장!
- 해시 충돌 = 서로 다른 키가 같은 인덱스를 가리킴
- Chaining = 리스트 연결, Open Addressing = 빈 슬롯 탐색
- Load Factor 관리가 성능의 핵심
Python dict 내부 동작 — 왜 O(1)인가?
dict의 내부 배열, __hash__ 프로토콜, 그리고 perturbation probing을 들여다봅시다.
Python에서 dict의 키가 되려면 hashable 해야 합니다
dict 내부에는 두 개의 배열이 있습니다. 인덱스 배열 + 엔트리 배열
Python 3.7부터 dict가 삽입 순서를 유지하는 이유가 바로 이 compact 구조!
- __hash__로 위치 계산, __eq__로 키 확인
- compact entries로 삽입 순서 보장 (Python 3.7+)
- LF > 2/3이면 자동 리사이즈 → amortized O(1)
빈도수 세기 패턴 — Counter의 원리
Counter와 defaultdict가 그 번거로움을 없애줍니다. 가장 Pythonic한 방법을 배워봅시다.
가장 기본적인 방법: dict에 키가 있으면 +1, 없으면 1로 초기화
동작하지만... if-else가 번거롭습니다. 더 깔끔한 방법이 있을까요?
dict.get(key, 기본값) 으로 if-else를 한 줄로 줄일 수 있습니다
- dict → defaultdict → Counter 순으로 편리해짐
- Counter는 most_common, 집합 연산까지 지원
- 아나그램, 다수 원소 등 빈도수 패턴의 핵심 도구
면접 실전: HashMap으로 푸는 5가지 패턴
각 패턴의 '신호'를 읽는 법을 익히면 문제를 보자마자 해시맵을 꺼낼 수 있습니다.
Two Sum: 배열에서 합이 target이 되는 두 수의 인덱스를 찾아라
문자열 배열에서 아나그램끼리 묶어라! 키를 어떻게 만들 것인가가 핵심
핵심 아이디어: sorted("eat") = sorted("tea") = ['a','e','t'] → 같은 키!
- Two Sum → 보수 탐색 패턴
- Group Anagrams → 키 변환 + 그룹핑 패턴
- Top K / Sudoku / Longest Consecutive → Counter, set 활용
챕터 3 종합 퀴즈
10문제로 챕터 3의 모든 개념을 점검합니다.
해시 함수의 가장 중요한 성질은?
Linear Probing에서 충돌이 발생하면 어떻게 하나요?
Python dict는 삽입 순서를 보장하지 않는다
- 해시 함수 → 충돌 해결 → Python dict 내부 동작
- Counter / defaultdict로 빈도수 세기
- 면접 5패턴: Two Sum, Group Anagrams, Top K, Sudoku, Longest Consecutive
핵심 용어 모음
해시 함수
임의의 데이터를 고정 길이 숫자로 변환하는 함수
해시 테이블
해시 함수로 키-값 쌍을 저장하는 자료구조
리스트 순차 탐색
O(n) — 최악의 경우 전부 확인
정렬 + 이진 탐색
O(log n) — 절반씩 줄여나감
해시 테이블 조회
O(1) — 인덱스로 직행!
해시 충돌
서로 다른 키 → 같은 인덱스를 가리키는 현상
Load Factor
n / m (저장 데이터 수 / 배열 크기)
Chaining
리스트로 연결 — 삭제 쉬움, 메모리 추가 필요
Open Addressing
빈 슬롯 탐색 — 캐시 효율적, 삭제 복잡
Python dict
Open Addressing 변형 사용 (최적화된 프로빙)
__hash__
객체의 해시값(정수)을 반환하는 매직 메서드
hashable
해시값이 변하지 않는 불변 객체 (str, int, tuple 등)
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 코스 시작하기