HashMap 내부 작동 방식

초기화 및 배열 크기

• 기본 크기: 초기 배열 크기는 16. 생성자를 통해 커스텀 크기 설정 가능.
• 리사이즈: 요소 수가 배열 크기의 75%를 초과하면 배열 크기가 두 배로 증가. 이때 재해싱 발생.

저장

• 해시 계산: 키의 hashCode() 메서드를 사용하여 해시 값 계산.
• 인덱스 결정: 해시 값 % 배열 길이로 인덱스 결정.
• 충돌 처리:
  • 링크드 리스트: 충돌 시 동일 인덱스에 노드를 연결 리스트 형태로 저장.
  • 트리 구조: 노드 수가 8개 이상이면 레드-블랙 트리로 변환.

조회

• 해시 계산: 저장 시와 동일하게 키의 hashCode()로 해시 값 계산.
• 인덱스 검색: 해시 값 % 배열 길이로 인덱스 결정.
• 노드 탐색:
  • 리스트 탐색: 링크드 리스트를 순차적으로 탐색. (같은 해시 Key가 8개 미만이라는 뜻)
  • 트리 탐색: 트리 구조를 사용해 빠르게 탐색.