Ch.3 해시맵과 해시셋
해시 함수란? — 데이터를 주소로 바꾸는 마법
10만 개의 전화번호에서 한 사람을 1초 만에 찾으려면?
배열을 처음부터 끝까지 뒤지면 O(n)입니다. 하지만 해시 테이블은 키 하나로 단번에 찾아갑니다.
어떻게 '김철수'라는 이름이 곧바로 배열의 인덱스가 될 수 있을까?
해시 함수가 키를 숫자로 바꾸고, 그 숫자가 곧 주소가 됩니다. 이것이 O(1)의 비밀입니다.
핵심 개념
해시 함수
임의의 데이터를 고정 길이 숫자로 변환하는 함수
해시 테이블
해시 함수로 키-값 쌍을 저장하는 자료구조
핵심 내용
도서관에서 책을 찾는다고 생각해보세요. 모든 책을 하나하나 뒤질 건가요?
도서관에는 분류 번호가 있습니다. '813.6 한국소설' → 해당 서가로 직행!
해시 함수는 데이터의 '분류 번호'를 만드는 기계입니다
해시 함수는 어떤 데이터든 고정된 크기의 숫자로 바꿉니다
hash("apple") → 3 hash("banana") → 7 hash("cherry") → 1 키가 무엇이든, 배열 인덱스(숫자)가 나옵니다
핵심은 같은 키 → 항상 같은 숫자라는 점입니다. 그래서 찾을 때도 같은 인덱스로 직행!
해시값이 아무리 커도 나머지 연산(%) 으로 배열 크기에 맞춥니다
def simple_hash(key: str, size: int) -> int:
"""키를 배열 인덱스로 변환"""
hash_value = 0
for char in key:
hash_value += ord(char)
return hash_value % size
# 배열 크기 = 10
print(simple_hash("apple", 10)) # 530 % 10 = 0
print(simple_hash("banana", 10)) # 609 % 10 = 9
print(simple_hash("cherry", 10)) # 633 % 10 = 3배열에서 인덱스를 알면 단 한 번의 접근으로 값을 꺼냅니다
해시 테이블 = '주소록'입니다. 이름만 알면 전화번호를 즉시 찾을 수 있죠
Python의 dict와 set은 해시 테이블로 구현되어 있습니다
# dict: 키-값 저장 (HashMap)
phone_book = {
"김철수": "010-1234-5678",
"이영희": "010-8765-4321",
}
print(phone_book["김철수"]) # O(1) 조회!
# set: 값만 저장 (HashSet)
seen = {1, 2, 3}
print(4 in seen) # O(1) 존재 확인! → False
print(2 in seen) # O(1) 존재 확인! → Truedict = HashMap (키 → 값 매핑) set = HashSet (값의 존재 여부만 저장) 둘 다 내부적으로 해시 테이블 사용 → O(1) 평균 조회
해시 함수의 핵심 성질은?
Python의 set에서 'in' 연산은 O(n)이다
해시 테이블에서 데이터를 찾는 평균 시간 복잡도는?
해시 함수의 세계
핵심 용어
해시 함수
임의의 데이터를 고정 길이 숫자로 변환하는 함수
해시 테이블
해시 함수로 키-값 쌍을 저장하는 자료구조
리스트 순차 탐색
O(n) — 최악의 경우 전부 확인
정렬 + 이진 탐색
O(log n) — 절반씩 줄여나감
해시 테이블 조회
O(1) — 인덱스로 직행!
정리 노트
해시 함수 — 데이터를 주소로 바꾸는 마법
핵심 개념
- 해시 함수
- 임의의 데이터를 고정 길이 숫자로 변환하는 함수
- 해시 테이블
- 해시 함수로 키→인덱스 매핑하여 값을 저장하는 구조
- 나머지 연산
- hash(key) % size로 배열 범위 내 인덱스를 생성
Python 매핑
- dict
- HashMap — 키:값 쌍 저장, O(1) 조회
- set
- HashSet — 값의 존재 여부만 저장, O(1) 조회
해시 테이블 = 도서관 분류 번호. 키가 곧 주소이므로 직행 가능!
시각 자료
핵심 정리
- 1해시 함수 = 키 → 고정 크기 숫자 변환
- 2해시 테이블 = 해시값을 인덱스로 쓰는 배열
- 3Python dict/set = 해시 테이블 기반 → O(1) 조회
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작