[JAVA] HashMap 원리

정의

• 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)하여 관리하는 방법