쿠쿠 해싱 시뮬레이터
해시 테이블 두 개와 해시 함수 두 개로 충돌을 해결하는 쿠쿠 해싱의 삽입·축출(evict) 연쇄 과정을 스텝별로 보여줍니다.
키 목록 (줄바꿈 또는 쉼표로 구분, 순서대로 삽입)
table1 (해시 함수1)
0
·
1
·
2
·
3
·
4
RAT
5
CAT
6
·
7
OWL
table2 (해시 함수2)
0
·
1
DOG
2
·
3
·
4
·
5
·
6
BAT
7
·
삽입 로그
CAT→ table1[5]에 안착
DOG→ table1[7]에 안착
BAT→ table1[4]에 안착
RAT→ table1[4]에서 "BAT" 축출→ table2[6]에 안착
OWL→ table1[7]에서 "DOG" 축출→ table2[1]에 안착
어떤 키든 항상 table1[h1(키)] 또는 table2[h2(키)] 둘 중 한 자리에만 있어 탐색은 언제나 두 자리만 확인하면 됩니다. 축출 연쇄가 테이블 크기의 합을 넘으면 사이클로 보고 재해싱이 필요하다고 판단합니다.
사용 방법
- 1테이블 크기를 정하고, 키를 하나씩 순서대로 입력해 삽입합니다.
- 2삽입 스텝(축출 연쇄)과 두 테이블의 현재 상태를 확인합니다.
- 3축출이 정해진 횟수를 넘으면 재해싱이 필요하다는 안내를 확인합니다.
자주 묻는 질문
키를 해시 함수1로 table1의 자리에 넣으려 합니다. 그 자리가 비어 있으면 끝이지만, 차 있으면 기존 키를 "쫓아내고(evict)" 그 자리를 차지합니다. 쫓겨난 키는 해시 함수2로 table2의 자리에 다시 넣기를 시도하고, 또 차 있으면 다시 쫓아내는 식으로 연쇄됩니다.
어떤 키든 반드시 table1[h1(키)] 또는 table2[h2(키)] 둘 중 한 자리에만 있습니다. 그래서 탐색은 이 두 자리만 확인하면 끝나 항상 O(1)입니다.
이론적으로 축출 연쇄가 사이클을 이뤄 끝나지 않을 수 있습니다. 실전에서는 정해진 횟수(maxKicks)를 넘으면 사이클로 보고 해시 함수를 바꿔 테이블 전체를 다시 해싱(rehash)합니다. 이 계산기도 같은 방식으로 판단합니다.
쿠쿠 필터는 쿠쿠 해싱의 축출 아이디어를 빌려 쓰지만, 실제 키 자체가 아니라 키의 짧은 지문(fingerprint)만 저장해 "있을 수도 있다/확실히 없다"만 확인하는 확률적 자료구조입니다. 이 도구는 실제 키를 저장하는 진짜 해시 테이블을 시뮬레이션합니다.
알아두면 좋은 점
- 테이블 크기 4에서 CAT·DOG·BAT·RAT를 순서대로 넣었을 때의 해시값·축출 연쇄(RAT가 BAT를 쫓아내고 BAT가 table2로 옮겨감)를 실제로 계산해 대조 검증했습니다.
- 이미 삽입된 키를 다시 넣으면 테이블을 바꾸지 않고 성공을 보고하는지, 삽입되지 않은 키는 탐색에서 찾아지지 않는지 확인했습니다.
- 두 번의 축출이 필요한 상황에서 허용 횟수를 1로 제한하면 사이클(재해싱 필요)로 정확히 판정하는지 검증했습니다.
함께 보면 좋은 도구
쿠쿠 필터원소 수와 목표 오탐률에서 지문 비트 수와 필요한 메모리를 구하고 블룸 필터와 견줍니다.해시 적재율테이블 크기와 원소 수로 적재율 α를 구하고 체이닝·선형 탐사·이중 해싱의 성공·실패 평균 탐색 횟수를 계산합니다.gitignore 판정.gitignore 규칙과 경로를 넣으면 그 파일이 무시되는지, 어느 줄이 마지막으로 이겼는지 알려줍니다.울프람 규칙규칙 번호 0~255를 8비트로 풀어 세 칸 이웃에 대응시키고 세대를 쌓아 무늬를 그립니다.2-SAT「둘 중 하나는 참」인 조건을 여럿 넣으면 참·거짓 배정이 가능한지 판정하고 배정을 하나 찾아 줍니다.
마지막 검증: 2026년 9월 2일 · 결과는 참고용 추정치입니다.