해시 테이블이란?
해시 테이블(Hash Table)은 키(key)를 해시 함수로 배열 인덱스로 바꿔, 평균 O(1)에 값을 저장하고 찾는 자료구조입니다. 파이썬의 dict, 자바의 HashMap, 자바스크립트의 Map/객체가 모두 이 원리로 동작합니다.
핵심 한 줄: "키를 계산해서 바로 그 자리로 간다." 정렬이나 순차 탐색 없이, 키만 알면 곧장 위치를 계산해 접근합니다.
핵심: 해시 함수 + 충돌 처리
해시 함수는 임의의 키를 정수로 바꾸고, % 용량으로 배열 인덱스를 만듭니다. 좋은 해시 함수는 키들을 인덱스 전체에 고르게 흩뿌립니다.
문제는 충돌(collision) — 서로 다른 키가 같은 인덱스를 가리키는 경우입니다. 두 가지 대표적 해결책이 있습니다.
- •체이닝(chaining): 각 버킷을 연결 리스트로 만들어 충돌한 항목을 줄줄이 매답니다.
- •개방 주소법(open addressing): 충돌하면 정해진 규칙(선형 탐사 등)으로 다음 빈 칸을 찾아갑니다.
동작 원리
1단계. 삽입: idx = hash(key) % cap 위치 버킷에 (키, 값)을 넣습니다. 이미 차 있으면 충돌 처리 규칙을 따릅니다.
2단계. 검색: 같은 방식으로 idx를 구한 뒤, 그 버킷에서 키를 직접 비교해 원하는 항목을 찾습니다(해시가 같아도 키는 다를 수 있으므로).
3단계. 리사이즈(재해싱): 채워진 비율(로드 팩터)이 임계값을 넘으면 배열을 키우고 모든 항목을 새 용량으로 다시 해싱합니다. 충돌이 줄어 평균 성능이 유지됩니다.
알고노트 시각화는 키가 어느 버킷으로 가는지, 충돌이 어떻게 풀리는지 단계별로 보여줍니다.
시간복잡도와 공간복잡도
| 연산 | 평균 | 최악 |
|---|---|---|
| 삽입/검색/삭제 | O(1) | O(n) |
| 공간 | O(n) | O(n) |
최악(모든 키가 한 버킷에 몰림)은 O(n)이지만, 좋은 해시 함수와 적절한 로드 팩터 관리로 평균 O(1)을 얻습니다.
예시로 따라가기
용량 5, 체이닝, hash(k)=k라고 합시다.
- •12 삽입 → 12%5=2번 버킷
- •17 삽입 → 17%5=2번 버킷 → 12와 충돌 → 같은 버킷에 줄줄이(체이닝)
- •검색 17 → 2번 버킷의 리스트를 따라가며 키 17을 찾음
자주 하는 실수
- •나쁜 해시 함수: 인덱스가 한쪽으로 몰리면 충돌이 폭증해 O(n)에 가까워집니다.
- •로드 팩터 방치: 리사이즈를 안 하면 버킷마다 항목이 쌓여 느려집니다.
- •가변 키 사용: 넣은 뒤 키를 바꾸면 해시값이 달라져 다시 못 찾습니다.
알고노트에서 직접 확인하세요
키가 해시되어 버킷에 들어가고, 충돌이 체이닝으로 풀리는 과정을 알고노트에서 단계별로 확인할 수 있습니다.