Java8에서부터 HashMap이 어떻게 개선됐는지 설명해주세요

[eunjungL]

.

[PgmJun]

HashMap은 사용 중 값을 동시에 저장시키는 충돌(collision)이 발생한 경우 Separate chaining을 수행한다.

Java8 이전까지의 Separate chaining은 충돌(collision)이 발생한 경우 LinkedList 형태로 충돌난 값들을 모두 저장하곤 했다.

하지만 LinkedList는 조회 시 O(N) 의 시간복잡도를 가진다는 단점이 있어서,
충돌로 인해 LinkedList에 저장된 값의 개수가 임계값을 넘어가면 Red-Black Tree 형태로 저장하여 O(log N) 시간복잡도로 조회할 수 있도록 성능을 개선하였다.

Red-Black Tree로 변하는 임계값은 8 이상이며, 다시 LinkedList로 돌아오기 위한 값은 6 이하이다.

[PgmJun]

꼬리질문: Red-Black Tree란 무엇인가요?