해시 테이블 적재율 계산기

테이블 크기와 원소 수로 적재율 α를 구하고 체이닝·선형 탐사·이중 해싱의 성공·실패 평균 탐색 횟수를 계산합니다. α가 0.7을 넘을 때 선형 탐사가 무너지는 지점을 표로 확인할 수 있습니다.

테이블 크기

칸

버킷(슬롯) 개수입니다.

담은 원소 수

개

적재율 α

0.75

768 ÷ 1,024 = 75% 참

선형 탐사 · 실패 탐색8.5회

선형 탐사 · 성공 탐색2.5회

이중 해싱 · 실패 탐색4회

이중 해싱 · 성공 탐색1.85회

체이닝 · 실패 탐색0.75회 비교

체이닝 · 성공 탐색1.38회 비교

실패 탐색이 언제나 더 비쌉니다. 찾는 것이 있으면 만나는 순간 멈추지만, 없다는 것을 확인하려면 빈 칸에 닿을 때까지 가 봐야 하기 때문입니다. 삽입 비용도 실패 탐색과 같습니다 — 넣을 자리를 찾는 일이 곧 없다는 것을 확인하는 일이라서입니다. 지금 α에서 선형 탐사로 하나를 새로 넣으면 평균 8.5칸을 들여다봅니다.

적재율 α	선형 실패	이중 실패	선형 성공	체이닝 성공
0.1	1.12	1.11	1.06	1.05
0.25	1.39	1.33	1.17	1.13
0.5	2.5	2	1.5	1.25
0.7	6.06	3.33	2.17	1.35
0.75	8.5	4	2.5	1.38
0.8	13	5	3	1.4
0.9	50.5	10	5.5	1.45
0.95	200.5	20	10.5	1.48
0.99	5,000	100	50.5	1.5

α가 0.7을 넘으면 선형 탐사가 급격히 무너집니다. 실패 탐색 식 ½(1 + 1/(1−α)²)의 분모가 «제곱»이기 때문입니다. 0.5에서 2.5회, 0.7에서 6.06회로 완만하다가 0.9에서 50.5회, 0.95에서 200.5회로 뜁니다. 이중 해싱은 분모가 (1−α)의 1제곱이라 같은 구간에서 10회, 20회에 그칩니다. 런타임들이 테이블을 두 배로 키우는(리해싱) 임계를 0.7 언저리에 둔 이유가 이 곡선입니다.

자바 HashMap 임계 α0.75

파이썬 dict 임계 α0.67 · 지금은 넘었습니다

C++ unordered_map 임계 α1

α를 0.75 이하로 두려면1,024칸 이상

체이닝은 α가 1을 넘어도 됩니다. 칸 안에 리스트를 달아 두므로 자리가 모자랄 일이 없고, 비용이 α에 «비례»해서만 늘어납니다 (성공 1+α/2, 실패 α). 대신 리스트 노드마다 포인터가 붙어 메모리를 더 쓰고, 흩어진 노드를 따라가느라 캐시 적중률이 떨어집니다. 개방주소법은 그 반대로 메모리가 촘촘하고 캐시에 잘 맞지만 α에 목이 매입니다.

지금 테이블에서 빈 칸으로 남을 비율은 약 47.2%입니다((1−1/m)ⁿ). α가 1이어도 3분의 1 넘는 칸이 비어 있고 다른 칸에는 여럿이 몰립니다 — 해시가 «고르게» 흩뿌린다는 것이 «한 칸에 하나씩»이라는 뜻은 아니기 때문입니다. 체이닝에서 원소가 든 칸의 평균 리스트 길이는 1.42개로, α보다 큽니다.

이 수치는 낙관적인 하한에 가깝습니다. 세 식 모두 해시가 완벽히 고르게 흩뿌린다고 가정하고, 특히 이중 해싱 식은 빈 칸 순열이 무작위라는 «균등 해싱»을 가정한 근사입니다. 선형 탐사에는 여기에 더해 한 번 뭉친 자리가 다음 충돌을 빨아들이는 1차 군집이 있어 실제 측정값은 대개 이보다 나쁩니다. 해시 함수가 치우치면 α가 낮아도 성능이 무너질 수 있습니다.

사용 방법

1테이블 크기(버킷 개수)를 넣습니다.
2담은 원소 수를 넣으면 적재율 α = 원소 수 ÷ 테이블 크기가 나옵니다.
3체이닝·선형 탐사·이중 해싱의 성공·실패 평균 탐색 횟수를 견줍니다. 삽입 비용은 실패 탐색과 같습니다.
4표에서 α를 올렸을 때 각 방식이 어떻게 나빠지는지 보고 리해싱 임계값을 정합니다.

자주 묻는 질문

적재율 α = 담은 원소 수 ÷ 테이블 크기입니다. 1024칸에 768개를 담았다면 α = 0.75입니다. 개방주소법(선형 탐사·이중 해싱)은 원소를 테이블 안에 두므로 α가 1을 넘을 수 없고, 체이닝은 칸마다 리스트를 달아 두므로 1을 넘어도 됩니다.

체이닝은 성공 1+α/2·실패 α, 선형 탐사는 성공 ½(1+1/(1−α))·실패 ½(1+1/(1−α)²), 이중 해싱은 성공 (1/α)·ln(1/(1−α))·실패 1/(1−α)입니다. Knuth의 TAOCP 3권 6.4절에 있는 닫힌 식이며, 해시가 고르게 흩뿌린다는 가정에서 나옵니다.

선형 탐사의 실패 탐색 비용이 (1−α)의 제곱에 반비례해서 α가 1에 가까워질 때 폭발하기 때문입니다. α 0.5에서 2.5회, 0.75에서 8.5회지만 0.9에서 50.5회, 0.95에서 200.5회가 됩니다. 자바 HashMap이 0.75, 파이썬 dict가 2/3을 임계로 두는 이유가 이 곡선입니다.

없다는 것을 확인하려면 빈 칸에 닿을 때까지 끝까지 가 봐야 하기 때문입니다. 찾는 것이 있으면 만나는 순간 멈추지만, 없을 때는 탐사 순열을 계속 따라가야 합니다. 삽입 비용도 실패 탐색과 같습니다 — 넣을 자리를 찾는 일이 곧 없다는 것을 확인하는 일이라서입니다.

적재율이 높다면 이중 해싱이 확실히 낫습니다. α 0.9에서 실패 탐색이 이중 해싱 10회, 선형 탐사 50.5회로 다섯 배 벌어집니다. 다만 선형 탐사는 다음 칸을 순서대로 보므로 CPU 캐시에 잘 맞아, α를 0.5 아래로 낮게 유지한다면 실측이 더 빠를 수 있습니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.

알아두면 좋은 점

세 식 모두 해시가 균등하게 흩뿌린다는 가정에서 나온 근사입니다. 특히 이중 해싱 식은 빈 칸 순열이 무작위라는 «균등 해싱»을 가정한 것으로, 실제 이중 해싱은 이보다 조금 나쁩니다.
선형 탐사에는 한 번 뭉친 자리가 다음 충돌을 빨아들이는 1차 군집이 있어 실제 측정값이 식보다 나쁜 쪽으로 벌어집니다. 여기 수치는 하한에 가깝습니다.
체이닝 수치는 리스트를 따라가며 «비교한 횟수»입니다. 칸 자체를 보는 것을 한 번으로 세는 교재는 여기에 1을 더해 성공 1+α/2 대신 실패를 1+α로 적기도 합니다.
삭제가 잦은 개방주소법 테이블에서는 삭제 표식(tombstone)이 쌓여 실질 적재율이 계산값보다 높아집니다. 그때는 원소 수가 줄어도 탐색이 느려집니다.
α가 낮아도 해시 함수 자체가 치우치면 성능이 무너집니다. 적재율은 필요조건이지 충분조건이 아닙니다.

마지막 검증: 2026년 9월 1일 · 결과는 참고용 추정치입니다.

사용 방법

자주 묻는 질문

해시 테이블 적재율(load factor)은 어떻게 계산하나요?

적재율에 따른 평균 탐색 횟수 공식은 무엇인가요?

적재율이 0.75를 넘으면 왜 리해싱을 하나요?

실패 탐색이 성공 탐색보다 비싼 이유는 무엇인가요?

선형 탐사와 이중 해싱 중 어느 것이 나은가요?

입력한 값이 서버로 전송되나요?

알아두면 좋은 점

함께 보면 좋은 도구