DATA STRUCTURE
해시 테이블 (Hash Table)
키를 해시 함수에 넣어 저장할 위치(버킷)를 즉시 계산하는 구조를 확인하세요. 서로 다른 키가 같은 버킷으로 계산되는 "충돌"이 나면 체이닝으로 뒤에 연결하는 것도 함께 볼 수 있습니다. 사물함 배정, 전화번호부 검색 같은 시나리오로 평균 O(1)이 어떻게 가능한지, 그리고 해시 함수가 나쁘면 어떻게 느려지는지 직접 체감할 수 있습니다.
재생 버튼을 누르거나 다음 단계 버튼으로 해시 테이블 연산을 시작하세요.
삽입 0회 · 검색 0회 · 삭제 0회
1 / 1
PSEUDOCODE
idx ← hash(key) % TABLE_SIZEinsert(key, value): buckets[idx]에 (key, value) 추가 (있으면 뒤에 체이닝)search(key): buckets[idx]를 앞에서부터 순회 key가 일치하면 발견 끝까지 못 찾으면 "찾을 수 없음" 오류delete(key): search로 찾은 뒤 buckets[idx]에서 제거어떻게 동작하나요
해시 테이블은 키를 해시 함수에 넣어 나온 숫자를 배열의 인덱스(버킷 번호)로 그대로 사용합니다. 이 페이지는 hash(key) = key % 7이라는 단순한 함수를 씁니다.
서로 다른 키가 같은 버킷으로 계산되면 "충돌"이 발생하는데, 이 경우 그 버킷 안에 여러 항목을 체이닝(연결 리스트처럼 뒤에 이어붙임)으로 저장합니다.
충돌이 적을수록 버킷마다 항목이 하나뿐이라 검색이 즉시 끝나지만(O(1)), 충돌이 몰리면 그 버킷 안을 순서대로 뒤져야 해서 연결 리스트처럼 느려집니다(O(n)) — 해시 함수의 품질이 성능을 좌우하는 이유입니다.
시간·공간 복잡도
- 삽입 (평균)
- O(1)
- 검색·삭제 (평균)
- O(1)
- 최악 (모두 충돌)
- O(n)
- 공간 복잡도
- O(n)
"최악의 해시 함수" 시나리오에서 모든 키가 한 버킷에 몰리는 것을 보면, 왜 좋은 해시 함수가 골고루 흩어지도록 설계되어야 하는지 체감할 수 있습니다.
다른 자료구조(힙·이진 탐색 트리)도 이어서 시각화할 예정입니다 — Algorithm 코스로 돌아가기