[JAVA] HashMap 원리
·
JAVA
정의 Key-Value가 1:1로 Mapping되는 자료구조 Mapping으로 인해 삽입, 삭제, 검색이 평균적으로 O(1)인 자료구조 Key에 대한 해시값을 기반으로 값을 저장 및 조회하는 자료구조 개념 정리 HashMap은 기본적으로 내부구조는 배열로 되어 있음 Key는 직접 내부 배열의 인덱스가 될 수 있으며, 이를 버킷이라고 함 인덱스는 hashcode()에서 리턴하는 int값(정수값) % 실제 표현이 가능한 정수범위(n)보다 작은 M개의 원소로 만들어짐, 해당 인덱스는 1 / M 확률로 동일한 값으로 발생할 수 있으며, 이를 해시충돌이라고 함 해시충돌 방지 기법으로 Open Addressing 방식과 Seperate Chaning 방식이 있으며, Java HashMap 같은 경우 Seperate..