해시 충돌이 발생했을 때의 해결책은 무엇인가?

체이닝은 한 버킷에 여러 값을 잇는다. 오픈 어드레싱은 배열 안에서 다른 빈 칸을 찾는다.

체이닝은 버킷에 여러 데이터를 연결해 저장한다. 데이터가 많아지면 리스트가 길어져 탐색 시간은 O(N)으로 늘어난다. 자바 8 이후 HashMap처럼 한 버킷이 임계치를 넘으면 리스트를 레드-블랙 트리로 바꾸는 구현도 있다. 해시 테이블 일반의 동작은 아니다.

오픈 어드레싱은 빈 칸을 찾을 때까지 다른 칸을 탐색한다. 선형 탐색을 쓰면 데이터가 뭉치는 클러스터링이 발생해 성능이 급격히 떨어진다. 이를 막기 위해 2차 해시 함수를 쓰거나 무작위로 탐색하는 방식을 사용한다.