평균 가정 표시
Map/Set 연산의 O(1)은 균등한 해시 분포와 적절한 resize가 있을 때의 평균입니다.
average충돌 모델 확인
체이닝, 오픈 어드레싱, 트리 버킷 등 충돌 처리 방식에 따라 최악 비용이 달라집니다.
collision공격 가능성 분리
외부 사용자가 키를 고를 수 있으면 hash flooding으로 서버 CPU를 소모시킬 수 있습니다.
adversarial정렬 대안 비교
해시가 불안정하거나 순서가 필요하면 balanced tree, sort 후 two pointer 같은 대안을 검토합니다.
alternativeLoad factor
버킷 대비 원소 수가 높으면 충돌과 resize가 늘어남
대량 삽입에서는 resize 비용이 순간적으로 튈 수 있습니다.
capacity
String key
키 생성과 해시 계산 자체가 길이에 비례
O(1) 조회라도 긴 문자열을 매번 만들면 전체 비용이
커집니다.
key cost
Salted hash
의도적 충돌을 어렵게 만드는 방어
보안 맥락에서는 재현 가능한 단순 해시보다 무작위성이 필요할 수
있습니다.
defense