[JAVA8] HashMap 성능 / 내부구조

모던 자바 인 액션을 보고 있는데 몰랐던 흥미로운 사실이 있어서 포스팅을 한다

Java8 에서 HashMap의 내부구조를 바꿔 성능을 개선했다고 한다

- Java8 이전

키로 생성한 해시코드로 접근할 수 있는 버켓에 저장
같은 해시코드의 키인 경우 LinkedList 버킷 반환
O(n) 시간소요

- Java8

이전과 동일
동일 해시코드를 반환하는 키가 8개 이상일 경우 정렬된 트리를 이용해 동적으로 치환
O(log(n)) 시간소요
키가 String, Number 클래스 같은 Comparable의 형태여야만 정렬된 트리 지원됨

모던자바인액션 책에는 "버킷이 너무 커질 경우" 이를 정렬된 트리로 바꿔준다는데 그 뜻이 명확하게 와닿지않아서 검색해보니 아래와 같이 실험정신 투철하신 분의 멋진 포스팅을 발견하여 궁금증이 풀렸다
(포스팅을 카페에서 급히 하다보니 집에 가서 코드로 직접 봐보고싶다)
좀 더 상세히 보고싶으시다면 아래 블로그를 방문하시길 추천 : )

https://ohtaeg.tistory.com/7

HashMap 내부는 충돌시 언제 트리 구조로 변경될까?