728x90
정의
- Key-Value가 1:1로 Mapping되는 자료구조
- Mapping으로 인해 삽입, 삭제, 검색이 평균적으로 O(1)인 자료구조
- Key에 대한 해시값을 기반으로 값을 저장 및 조회하는 자료구조
개념 정리
- HashMap은 기본적으로 내부구조는 배열로 되어 있음
- Key는 직접 내부 배열의 인덱스가 될 수 있으며, 이를 버킷이라고 함
- 인덱스는 hashcode()에서 리턴하는 int값(정수값) % 실제 표현이 가능한 정수범위(n)보다 작은 M개의 원소로 만들어짐, 해당 인덱스는 1 / M 확률로 동일한 값으로 발생할 수 있으며, 이를 해시충돌이라고 함
- 해시충돌 방지 기법으로 Open Addressing 방식과 Seperate Chaning 방식이 있으며, Java HashMap 같은 경우 Seperate Chaning 방식으로 처리함
충돌 방지 기법
- Open Addressing : 해시충돌 발생시 인접 인덱스 값을 구해서 해시 충돌을 우회하는 방법
- Separate Chaining : 동일한 해시 값이 있을 경우 LinkedList로 관리하고, 8개 이상인 경우 Tree로 변경(6개 이하가되면 다시 LinkedList)하여 관리하는 방법
'JAVA' 카테고리의 다른 글
| [JAVA] List Collection(ArrayList / LinkedList / Vector) (0) | 2021.06.26 |
|---|---|
| [JAVA] String / StringBuilder / StringBuffer (0) | 2021.06.20 |
| [JAVA] 일급컬렉션 (0) | 2021.06.10 |
| [JAVA] Map / getOrDefault (0) | 2021.06.10 |
| [JAVA] 예외(Exception) (0) | 2021.06.07 |