해시 충돌 발생 시 해결 방법은 무엇인가?

체이닝과 개방 주소법을 사용한다. 체이닝은 연결 리스트로 데이터를 엮고, 개방 주소법은 빈 공간을 찾아 저장한다.

체이닝은 삭제가 쉽고 테이블이 꽉 차지 않는다. 하지만 리스트가 길어지면 탐색 시간이 O(n)으로 늘어난다. 자바 8부터는 한 버킷에 쌓인 수가 임계치를 넘고 표 용량이 64 이상일 때 그 버킷을 트리로 바꾼다. 용량이 작으면 트리 대신 표를 먼저 키운다.

개방 주소법은 추가 메모리가 없지만, 데이터가 뭉치는 클러스터링 현상이 발생한다. 선형 탐색은 인접한 빈칸을 찾으므로 뭉침이 심해 효율이 떨어진다.

해시 함수가 균등하게 분산시키지 못하면 충돌이 잦아진다. 이 경우 시간 복잡도가 최악의 경우 O(n)까지 떨어진다.