HashMap은 해시 충돌을 어떤 방식으로 처리하는가?

Java의 HashMap은 개별 체이닝(Separate Chaining) 방식으로 해시 충돌을 처리한다.

같은 해시 값을 가지는 키가 들어오면 해당 버킷에 연결 리스트로 노드를 잇는다. Java 8부터는 검색 성능을 높이려고 버킷 내부 구조를 동적으로 바꾼다.

한 버킷의 노드가 8개 이상이고 전체 용량이 64 이상이면 레드-블랙 트리로 전환한다. 탐색 시간 복잡도가 O(N)에서 O(log N)으로 줄어든다. 노드가 6개 이하로 줄어들면 다시 연결 리스트로 되돌아간다.

개방 주소법 대신 개별 체이닝을 쓰는 주요 이유는 삭제 연산 때문이다. 개방 주소법은 삭제 시 탐색 불능을 막는 가짜 노드가 필요해서 오버헤드가 크지만 체이닝은 노드 연결만 끊으면 된다.