먼저 기본적으로 자료구조 시간에 배우는 해시 충돌의 해결법 두 가지를 알아보자.
1. 체이닝 (Separate Chaining)
충돌이 발생하면 키에 해당하는 데이터들을 LinkedList 형태로 연결하는 방식이다.
2. 개방 주소법 (Open Addressing)
충돌이 발생하면 다음 칸 또는 제곱만큼 건너뛴 칸 또는 다른 해시를 한 번 더 적용한 칸에 저장하는 방식이다.
그럼 자바의 HashMap은 해시 충돌이 발생할 경우 어떻게 해결할까?
HashMap은 체이닝 기법을 사용한다.
체이닝 기법은 개방 주소법보다 remove 면에서 유리하다.
또한 개방 주소법은 데이터의 밀도가 높아질수록 검색에 오랜 시간이 걸리게 될 것이므로 결국 체이닝 기법보다 불리하다.
자바 8 이전에는 체이닝을 할 때 무조건 LinkedList를 사용했지만 자바 8부터는 체이닝되는 데이터의 개수가 threshold(8개) 이상인 경우 binary tree 로 형태를 변환(treeifyBin)한다. (검색 효율성을 위해)
자바 내부 코드는 정말 보면 볼수록 대단하다...
'Java' 카테고리의 다른 글
| Collections.synchronizedMap(hashMap) 과 ConcurrentHashMap 의 차이 (0) | 2022.10.23 |
|---|---|
| Object 객체의 equals와 hashCode (0) | 2022.01.03 |