공통수학2
+ 정보과학
기초
이공
해시 함수와 충돌
비둘기집 원리
'자료구조' 학년별 심화 로드맵 보기탐구 방법
[해시 충돌 실험] 파이썬에서 간단한 모듈러 해시 함수로 무작위 문자열을 해싱하여 버킷 분포의 균등성을 히스토그램으로 분석하고, 충돌이 처음 발생하기까지의 시도 횟수를 반복 측정해 생일 역설 예측값과 비교
확장 연결
생일 역설을 이용하여 해시 충돌이 직관보다 훨씬 빠르게(약 √N 시도) 발생하는 확률을 계산하고, 이것이 해시 길이 설계와 무결성 검증에 주는 함의를 탐구
추천 탐구 주제
해시 테이블의 충돌 해결(체이닝, 개방 주소법)
암호학적 해시 함수(SHA-256)의 눈사태 효과
블룸 필터의 확률적 자료구조 원리