해시 자료구조의 평균 성능이 충돌 처리 방식 위에 얹혀 있다는 점을 이해하는지, 두 전략의 동작 차이와 트레이드오프를 함께 설명할 수 있는지를 가른다.
해시 충돌은 서로 다른 키가 같은 해시값으로 계산돼 같은 버킷에 떨어지는 현상이다. 해결 전략은 크게 두 갈래로 나뉜다. 개방 주소법은 빈 버킷을 다시 탐사해 자리를 찾는 방식이고(선형·제곱·이중 해싱), 분리 연결법은 버킷에 연결 리스트나 트리를 매달아 충돌 키를 함께 보관한다. 어느 쪽이든 로드 팩터가 높아질수록 충돌이 늘면서 평균 O(1)이 깨지므로, 리사이징 임계값을 함께 봐야 한다.
캐시 hit율은 괜찮은데 특정 키 패턴에서 지연이 튀어 프로파일링한 적이 있다면 충돌 군집화 이야기와 연결할 수 있다
HashMap을 쓰다가 키 객체의 hashCode/equals를 잘못 구현해 조회가 느려졌던 경험이 있다면 해시 함수 품질과 묶을 수 있다
Redis나 인메모리 캐시에서 리사이징·rehash 타이밍에 지연이 튀는 걸 본 적이 있다면 로드 팩터 임계값 결정 이야기로 잇는다
아직 공개된 답변이 없어요. 첫 공개 답변을 남겨보세요.