HashMap의 자료구조
Key-Value가 1:1로 Mapping 되는 자료구조이며 Mapping으로 인해 삽입, 삭제, 검색이 평균적으로 O(1)인 자료구조이다. Key는 중복을 허용하지 않지만, Value는 중복을 허용
- 내부구조는 배열로 되어 있다
- key는 직접 내부 배열의 인덱스가 될 수 있으면 이를 버킷이라함
- hash함수를 사용할 때 해시 버킷이 적다면 메모리를 절약할 수 있지만 해시충돌의 빈도가 높아진다.
- 특정 수치가 넘어가면 해시 버킷을 2배로 확장
- 해시함수를 구할 때 float으로 되어 있다면 해시충돌을 낮출 수 있지만 자바는 int로 되어있어 해시 충돌을 낮추기 위해 보조 해시 함수를 사용해 해시 값을 변영한다.
최악의 케이스
- Java 8 부터 HashMap, LinkedHashMap의 퍼포먼스가 향상
- 기존에는 키 충돌이 많은 아이템들을 linked list로 관리했는데, 8이후로는 balanced tree로 관리
- 최악의 경우 시간 복잡도가 O(n)에서 O(log n)으로 향상됐다.
- 충돌되는 키가 많은 해시 저장소는 linked list에 저장하지 않고 balanced tree에 저장
- 번경되는 사항은 HashMap, LinkedHashMap, ConcurrentHashMap에만 적용
해시 버킷의 아이템 수가 특정 임계 값을 초과하면, linked list를 balanced tree로 바꾼다.
참조
https://johngrib.github.io/wiki/java8-performance-improvement-for-hashmap/
remind