로빈 후드 해싱 계산기
홈 슬롯 순서를 입력하면 로빈 후드 해싱의 교체 과정과 최종 탐사거리(PSL)를 일반 선형탐사와 나란히 시뮬레이션합니다.
칸
해시값을 테이블 크기로 나눈 나머지. 줄바꿈·쉼표·공백 아무거나 됩니다.
최대 탐사거리(PSL)
로빈후드 2 vs 선형탐사 3
평균 PSL은 둘 다 1.25로 같습니다 — 분산만 로빈후드가 더 작습니다(0.688 vs 1.188)
교체 발생 횟수1회
슬롯 2에서키#3가 키#2를 밀어냄
| 삽입 순서 | 홈 슬롯 | 로빈후드 PSL | 선형탐사 PSL |
|---|---|---|---|
| #0 | 0 | 0 | 0 |
| #1 | 0 | 1 | 1 |
| #2 | 1 | 2 | 1 |
| #3 | 0 | 2 | 3 |
삽입 도중 지금 자리를 차지한 원소보다 자신이 더 멀리서 왔으면(탐사거리, PSL이 더 크면) 자리를 빼앗습니다. 평균 탐사거리는 적재율만으로 정해져 일반 선형탐사와 이론상 같지만, 최대 탐사거리의 분산은 크게 줄어듭니다.
사용 방법
- 1테이블 크기를 입력합니다.
- 2삽입 순서대로 각 키의 홈 슬롯(해시값을 테이블 크기로 나눈 나머지)을 쉼표나 공백으로 구분해 입력합니다.
- 3교체가 일어난 지점과 최종 탐사거리(PSL) 분포를 일반 선형탐사와 비교해 확인합니다.
자주 묻는 질문
개방주소법(open addressing)의 변형으로, 삽입 도중 지금 자리를 차지한 원소보다 자신이 더 멀리서 왔으면(탐사거리, PSL이 더 크면) 자리를 빼앗습니다. 부자(짧게 온 원소)에게서 가난한 자(멀리서 온 원소)에게 자리를 준다는 뜻의 이름입니다.
아니요. 평균은 적재율만으로 정해져 이론상 일반 선형탐사와 같습니다. 로빈 후드 해싱이 줄이는 것은 최대 탐사거리의 분산입니다 — 누가 얼마나 오래 걷는지를 재분배할 뿐입니다.
평균은 같아도 어떤 조회가 극단적으로 오래 걸리는 일(꼬리 지연시간)이 줄어들기 때문입니다. 실시간 시스템에서는 평균보다 최악의 경우가 더 중요할 때가 많습니다.
전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄집니다.
알아두면 좋은 점
- 실제 해시 함수 대신 이미 계산된 홈 슬롯(해시값 mod 테이블 크기)을 직접 입력받습니다.
함께 보면 좋은 도구
해시 적재율테이블 크기와 원소 수로 적재율 α를 구하고 체이닝·선형 탐사·이중 해싱의 성공·실패 평균 탐색 횟수를 계산합니다.쿠쿠 필터원소 수와 목표 오탐률에서 지문 비트 수와 필요한 메모리를 구하고 블룸 필터와 견줍니다.gitignore 판정.gitignore 규칙과 경로를 넣으면 그 파일이 무시되는지, 어느 줄이 마지막으로 이겼는지 알려줍니다.울프람 규칙규칙 번호 0~255를 8비트로 풀어 세 칸 이웃에 대응시키고 세대를 쌓아 무늬를 그립니다.2-SAT「둘 중 하나는 참」인 조건을 여럿 넣으면 참·거짓 배정이 가능한지 판정하고 배정을 하나 찾아 줍니다.
마지막 검증: 2026년 9월 5일 · 결과는 참고용 추정치입니다.