HashMap 내부 작동 방식
초기화 및 배열 크기
- 기본 크기: 초기 배열 크기는 16. 생성자를 통해 커스텀 크기 설정 가능.
- 리사이즈: 요소 수가 배열 크기의 75%를 초과하면 배열 크기가 두 배로 증가. 이때 재해싱 발생.
저장
-
해시 계산: 키의
hashCode()
메서드를 사용하여 해시 값 계산. - 인덱스 결정: 해시 값 % 배열 길이로 인덱스 결정.
-
충돌 처리:
- 링크드 리스트: 충돌 시 동일 인덱스에 노드를 연결 리스트 형태로 저장.
- 트리 구조: 노드 수가 8개 이상이면 레드-블랙 트리로 변환.
조회
-
해시 계산: 저장 시와 동일하게 키의
hashCode()
로 해시 값 계산. - 인덱스 검색: 해시 값 % 배열 길이로 인덱스 결정.
-
노드 탐색:
- 리스트 탐색: 링크드 리스트를 순차적으로 탐색. (같은 해시 Key가 8개 미만이라는 뜻)
- 트리 탐색: 트리 구조를 사용해 빠르게 탐색.