버킷 안에 목록을 둔다
충돌 원소를 같은 버킷에 연결하므로 구현은 직관적이지만 한 버킷이 길어지면 탐색이 느려집니다.
해시 충돌 전략 선택 기준
해시는 평균 O(1)이라는 기대와 충돌 처리 비용이 함께 있으므로 키 분포와 삭제 정책을 같이 설계합니다.
다음 빈 칸 탐색
배열 안에서 해결해 locality는 좋지만 군집화와 삭제 표식 처리가 성능을 좌우합니다.
테이블 여유를 유지
원소 수가 버킷 수에 가까워질수록 충돌이 늘기 때문에 재해시 기준을 정해야 합니다.
제출 전 남길 증거
키 함수
나머지 연산 전에 음수와 범위 끝값을 안전하게 처리합니다.
충돌 로그
같은 해시값이 몰리는 입력을 만들어 버킷 상태를 출력합니다.
삭제 정책
오픈 어드레싱은 단순 비우기 대신 tombstone 또는 재배치를
검토합니다.