Java Map의 내부 구현

Java Map?

Java에서 Map은 키와 값을 연결하는 자료구조를 제공한다.
이 Map 인터페이스는 여러 클래스에 의해 구현될 수 있으며 그 중 대표적인 것은 HashMap이다.

1. 기본 구조 - 배열 + 연결 리스트

   • HashMap의 핵심은 배열이다.
     배열의 각 슬롯은 연결 리스트 또는 트리로 이루어져 있다.
   • 만약 우리가 키-값 쌍을 저장하려고 한다면 먼저 키의 해시 값을 계산한다.
     이 해시 값이 결정하는 배열의 위치에 데이터를 저장한다.

2. 충돌 처리

   • 여러 키가 동일한 배열의 위치에 저장되어야 할 때 이를 충돌이라고 한다.
   • 이런 충돌을 해결하기 위해 그 위치에 연결 리스트를 사용한다.
     이 연결 리스트에는 동일한 위치에 저장되어야 하는 모든 키-값 쌍이 저장된다.

3. 배열 크기 조절

   • 만약 HashMap이 너무 많은 데이터를 저장하게 되면 배열의 크기를 늘려야 한다.

   • 이 과정을 재해싱이라고 부르며 기존의 데이터를 새로운 크기의 배열로 옮기게 된다.

4. 트리화

   • 특정 위치에서 연결 리스트의 크기가 너무 크다면 검색의 효율성을 높이기 위해 연결 리스트를 이진 트리로 변환한다.