해시 충돌이 생기면 어떤 방법으로 푸는가?

체이닝과 오픈 어드레싱으로 해결한다. 충돌이 발생한 데이터를 연결 리스트나 빈 공간으로 밀어내는 방식이다.

체이닝은 버킷으로 리스트를 구현하여 데이터가 계속 늘어나도 수용 가능하다. 다만 리스트가 길어지면 탐색 시간이 O(1)에서 O(n)으로 늘어난다.

오픈 어드레싱은 빈 칸을 찾을 때까지 계속 탐색한다. 데이터가 꽉 찰수록 충돌이 잦아져 성능이 급격히 떨어진다. 이를 막기 위해 로드 팩터를 관리하고 리사이징을 수행한다.