해시 충돌의 해결 방법에는 크게 두 가지가 있다.
- Separate Chaining
- Open Addressing.
Separate Chaining:
연결 리스트를 이용하여 한 버킷에 들어갈 수 있는 엔트리 수의 제한을 없애는 방법. 각 버킷이 연결 리스트를 가지고 있어, 충돌이 발생한 항목들을 리스트에 저장한다.
Open Addressing:
충돌이 발생하면 다른 주소에 데이터를 저장하는 방법. 충돌이 발생할 때 새로운 빈 버킷을 찾는 방식.
다들 기본적으로 알고있는 지식이지만, java에서 실제 해시 충돌이 일어났을 때 어떻게 처리하는지 알고 있는 사람은 많지 않은 것 같다.
💡 Java에서 해시 충돌 해결 방법
Java에서 채택한 방식 -> ❗️Separate Chaining❗️
하지만 Separate Chaining 방식에도 단점이 있다.
너무 많은 해시 충돌이 발생하여 한 버킷에 많은 연결 리스트 항목이 생기면 검색 시 O(n)의 시간 복잡도가 발생하여 해시의 장점인 빠른 검색 속도가 떨어지게 된다.
이를 보완하기 위해 Java 8부터는 연결 리스트의 항목 수가 임계치를 초과하면 레드-블랙 트리 방식으로 전환하여 해시 충돌 데이터를 관리한다. 이 방식은 검색 시 O(log N)의 시간 복잡도를 제공하므로, 기존의 연결 리스트만을 이용한 방식에 비해 성능이 크게 향상시킨 것이다.
📌결론
Java에서는 Separate Chaining + red black tree 를 활용해 해시충돌 해결!
