Java에서 해시 충돌을 처리하기 위해 사용하는 2가지 방법

Java 8 이전: Linked-List를 통한 충돌 처리

• [ ] 기본적으로 해시 테이블 구조를 사용하기 때문에 해시 충돌이 발생하면, 동일한 버킷에 속한 여러 개의 키-값 쌍을 **연결 리스트**로 저장하여 충돌을 해결한다 !
• [ ] 해시 충돌이 발생한 키-값 쌍은 리스트의 맨 앞이나 맨 뒤에 추가되며, 특정 키를 찾으려면 연결 리스트를 순차적으로 탐색해야 한다 ! → 최악의 경우, 충돌된 키들이 모두 하나의 연결 리스트에 저장되면 성능이 O(n)까지 저하될 수 있다. ( n: 해당 버킷에 저장된 키-값 쌍의 개수 )

Java 8 이후: Linked-List에서 Red-Black Tree로의 전환

• [ ] Java 8부터는 해시 충돌이 발생할 때 **연결 리스트 대신 레드-블랙 트리**를 사용하는 방식으로 성능을 개선했다 ! → O(log n)

전환 기준

• [ ] 버킷의 키-값 쌍이 8개 이상일 때 전환 !

• 충돌이 발생해 하나의 해시 버킷에 8개 이상의 키-값 쌍이 모이면, 기존의 연결 리스트는 **레드-블랙 트리**로 변환된다. → 이는 동일한 해시 값을 가진 데이터가 많을수록 연결 리스트를 순차적으로 탐색하는 데 시간이 오래 걸리기 때문에, 트리 구조를 사용해 성능을 개선하기 위함이다 !

• [ ] 6개 이하로 줄어들면 다시 연결 리스트로 !

• 반대로, 버킷의 키-값 쌍이 6개 이하로 감소하면 레드-블랙 트리에서 다시 연결 리스트로 변환된다 ! → 그 이유는 트리는 메모리 사용량이 더 많으며, 데이터가 적을 때는 연결 리스트와 트리의 성능 차이가 크지 않기 때문입니다.

상수로 정해진 기준

• [ ] Java 8의 HashMap 내부에는 해시 충돌로 인한 구조 변경 기준이 상수로 정해져 있다.
• 8개 이상: 연결 리스트 → 레드-블랙 트리
• 6개 이하: 레드-블랙 트리 → 연결 리스트

HashSet에서의 해시 충돌 처리

• [ ] HashSet은 내부적으로 HashMap을 사용하여 데이터를 관리합니다. 따라서 해시 충돌 처리 방식도 동일하게 적용된다 !