해시 테이블(Hash Table)의 평균 시간 복잡도와 최악 시간 복잡도는 왜 다르게 나타나나요?

이렇게 답해 보세요 (핵심 답변)

해시 테이블은 키를 해시 함수로 변환해 버킷 인덱스를 바로 찾고, 충돌은 체이닝이나 개방 주소법(탐사)으로 처리합니다. 해시값이 고르게 분포하고 부하율(Load Factor)이 적절히 관리된다는 가정에서는 조회·삽입·삭제가 기대(평균) O(1)이지만, 많은 키가 한 버킷으로 몰리는 충돌이 발생하면 결국 모두 비교해야 해서 최악 O(n)이 될 수 있습니다. 따라서 키의 동등성 계약을 지키면서 입력을 고르게 분산시키는 해시 함수와 리사이징 정책이 중요합니다.

함께 설명하면 좋은 이유 (꼬리질문 대비)

1. 버킷 배열을 확장하고 재해싱하는 순간에는 O(n) 비용이 들지만, 여러 번의 삽입 전체로 나누어 보면 상환(Amortized) O(1) 비용으로 설명할 수 있습니다.
2. 키가 긴 문자열이라면 버킷을 찾기 전에 해시값을 계산하는 시간 자체가 키 길이에 비례해 늘어난다는 점도 함께 고려합니다.

면접에서 자주 하는 실수

일반 해시 테이블의 해시 함수가 암호학적 충돌 저항성까지 자동으로 갖추고 있다거나 모든 입력에서 최악 O(1)을 보장한다고 가정하면 안 됩니다.