해시 테이블 적재율 계산기 쉽게 이해하기 — 개념과 원리

해시 테이블의 적재율 α는 저장된 항목 수를 버킷 수로 나눈 값으로, 검색 속도를 예측하는 가장 중요한 지표입니다. 이 계산기는 α와 함께 선형 탐사에서 커누스가 유도한 평균 탐사 횟수, 체이닝의 평균 체인 길이, 비어 있을 것으로 기대되는 버킷 수를 보여 줍니다.

α = 0.7이면 키가 뭉쳐서, 없는 키를 찾을 때 빈칸까지 평균 약 6칸을 지나갑니다.

계산 방법

적재율: α = n ÷ m(항목 수 ÷ 버킷 수)
선형 탐사, 성공 검색: ½ · (1 + 1 ÷ (1 − α))회
선형 탐사, 실패 검색·삽입: ½ · (1 + 1 ÷ (1 − α)²)회
체이닝 평균 체인 길이: α
빈 버킷 기댓값: m · e^(−α)

α ≥ 1이면 개방 주소법에서는 빈 칸이 없으므로 경고를 표시합니다.

원리

좋은 해시 함수를 쓰면 각 항목이 거의 무작위로 버킷에 들어갑니다. 그러면 한 버킷에 들어가는 항목 수는 평균이 α인 푸아송 분포를 따르고, 버킷이 비어 있을 확률은 e^(−α)가 됩니다. 선형 탐사는 충돌이 나면 다음 칸으로 넘어가므로 차 있는 칸들이 길게 뭉치는 1차 군집이 생깁니다. 커누스는 이 비용이 성공 검색에서는 1 ÷ (1 − α), 실패 검색에서는 1 ÷ (1 − α)²에 비례해 커진다는 것을 보였습니다. 그래서 테이블이 찰수록 성능이 급격히 나빠집니다.

예제 풀이

입력값: 항목 7,000개, 버킷 10,000개입니다.
α = 7,000 ÷ 10,000 = 0.7입니다.
성공 검색: ½ · (1 + 1 ÷ 0.3) = ½ · 4.333 = 2.166666667회입니다.
실패 검색: ½ · (1 + 1 ÷ 0.09) = ½ · 12.111 = 6.055555556회입니다.
체이닝 평균 체인 길이는 0.7입니다.
빈 버킷: 10,000 · e^(−0.7) ≈ 4,965.853038개입니다.

다른 값은 그대로 두고 “버킷 수”만 바꿔 계산기를 다시 돌린 결과입니다. 금색 점이 예제 값이며, 위에 값을 입력하면 내 값으로 다시 그려집니다.

버킷 수	적재율 α
2,500	2.8
5,000	1.4
7,500	0.9333333333
10,000	0.7
12,500	0.56
15,000	0.4666666667
20,000	0.35

결과 해석

선형 탐사에서는 α를 0.5~0.7 정도로 유지하면 성공·실패 검색이 모두 빠르지만, α = 0.9에서는 실패 검색 한 번에 약 50회를 탐사합니다. 체이닝은 더 높은 적재율도 견디므로 많은 라이브러리가 0.75 부근에서 크기를 늘리며, 자바 HashMap의 기본 적재율도 0.75입니다. α = 0.7에서 버킷의 절반 가까이가 비어 있는 것은 정상입니다.

흔한 실수

α = 0.7을 버킷의 70%가 쓰인다는 뜻으로 오해합니다. 실제로는 약 50%만 쓰입니다.
약한 해시 함수나 규칙적인 키에 이 공식을 그대로 적용합니다.
개방 주소법에서 삭제 표시가 남아 탐사 횟수가 줄지 않는다는 점을 잊습니다.

주의: 이 공식은 균일한 무작위 해싱과 충분히 큰 테이블을 가정합니다. 실제 성능은 캐시와 해시 함수에 따라 달라지므로 실제 키로 측정해 보십시오.

자주 묻는 질문

적재율은 얼마로 정하면 좋나요?

개방 주소법은 0.5~0.75, 체이닝은 0.75~1 정도가 흔합니다.

테이블을 늘릴 때 왜 두 배로 키우나요?

비싼 재해싱이 점점 드물어져 삽입 한 번의 평균 비용이 일정하게 유지되기 때문입니다.

버킷 수는 꼭 소수여야 하나요?

단순한 나머지 해싱에서는 도움이 되지만, 잘 섞는 해시 함수라면 2의 거듭제곱도 충분합니다.

출처: D. E. Knuth, The Art of Computer Programming, Vol. 3, Section 6.4 Hashing, Addison-Wesley · Oracle, Java SE API 문서, java.util.HashMap

2026년 11월 8일 확인. 표준 공식과 RFC/IEEE 정의를 사용해 브라우저 안에서만 계산합니다. 입력한 내용은 어디에도 전송되지 않습니다.

입력값