Java HashMap 내부 구조 완벽 이해하기

Java HashMap 내부 구조 완벽 이해하기

Java 실무에서 가장 많이 사용하는 자료구조를 하나만 뽑으라면 거의 무조건:

HashMap

입니다.

실제로:

• 캐시
• 로그인 세션
• API 응답 저장
• DB 조회 결과
• Spring 내부 구조

전부 HashMap과 깊게 연결됩니다.

하지만 많은 사람들이 단순히:

 

map.put(key, value);

 

정도만 사용하고 내부 동작은 잘 모르는 경우가 많습니다.

실제로 HashMap 내부에는:

• hashCode()
• bucket
• collision
• resize
• linked list
• red-black tree

같은 중요한 자료구조 개념이 숨어 있습니다.

이번 글에서는:

• HashMap 동작 원리
• hashCode 역할
• bucket 구조
• 충돌 처리
• resize
• JDK8 TreeNode 최적화

까지 실무 관점으로 깊게 정리해보겠습니다.

---

1. HashMap이란?

HashMap 은:

key-value 기반 Hash 자료구조

입니다.

특징:

빠른 조회
빠른 삽입

 

가능.

---

2. 핵심 목표

HashMap 목표:

조회 속도 O(1)

 

입니다.

즉:

 

map.get(key);

 

를 매우 빠르게 수행하는 것이 목적.

---

3. 내부 구조 전체 그림 (HashMap 동작 원리)

HashMap 내부는 사실:

배열(Array)
+
LinkedList
+
Red-Black Tree

 

조합 구조입니다.

---

4. 가장 핵심 구조: bucket 배열

내부적으로 대략 이런 느낌.

 

Node<K,V>[] table;

 

즉:

Node 배열

 

기반.

---

5. bucket이란?

bucket은:

데이터를 저장하는 슬롯(slot)

입니다.

예:

[0][1][2][3][4]

 

각 칸이 bucket.

---

6. put() 동작 시작

예시:

 

map.put("Apple", 1000);

 

HashMap은 먼저:

hashCode()

 

호출.

---

7. hashCode란?

모든 객체는:

 

hashCode()

 

메서드 보유.

즉:

객체를 숫자로 변환

 

하는 함수.

---

8. 왜 숫자로 바꿀까? (hashCode 역할)

목표:

배열 index 계산

 

하기 위해.

---

9. 실제 흐름

key.hashCode()
↓
hash 계산
↓
bucket index 결정
↓
저장

 

---

10. bucket index 계산

대략 내부적으로:

 

index = hash % arrayLength

 

비슷한 계산 수행.

실제로는 비트 연산 최적화 사용.

---

11. 예시

예:

Apple.hashCode() = 1234

 

배열 크기:

16

 

이면:

1234 % 16

 

결과 bucket 선택.

---

12. 왜 빠를까?

핵심:

배열 직접 접근 가능

 

즉:

O(1)

 

수준 접근 가능.

---

13. 문제 발생: Hash Collision

매우 중요합니다.

다른 key인데:

같은 bucket 위치

 

가능.

이를:

Hash Collision

이라고 함.

---

14. 예시

"A" -> bucket 3
"B" -> bucket 3

 

둘 다 같은 위치 가능.

---

15. 충돌 처리 방식

JDK8 이전:

LinkedList 연결

 

사용.

---

16. 구조 예시 (bucket 구조)

bucket[3]
 ↓
[A] -> [B] -> [C]

 

형태.

---

17. 조회 시 문제

 

map.get("B");

 

실제로:

bucket 탐색
↓
equals() 비교 반복

 

필요.

---

18. 그래서 equals() 중요

HashMap은:

hashCode()
+
equals()

 

둘 다 사용.

---

19. hashCode만 같으면 안 된다 (충돌 처리)

예:

같은 bucket 위치

 

까지는 가능.

진짜 동일 key 확인은:

equals()

 

수행.

---

20. 왜 equals/hashCode 같이 재정의해야 할까?

매우 중요.

잘못 구현하면:

Map 조회 실패

 

가능.

---

21. 안 좋은 예

 

equals만 재정의
hashCode 미재정의

 

문제 발생 가능.

---

22. HashMap resize

배열 꽉 차면:

resize 발생

 

즉:

더 큰 배열 생성
↓
데이터 재배치

 

수행.

---

23. 왜 비용이 클까?

모든 데이터 다시:

rehash

 

해야 하기 때문.

---

24. Load Factor란?

대표 값:

0.75

 

입니다.

---

25. 의미

예:

배열 16칸

 

이면:

12개 저장 시 resize

 

발생.

---

26. 왜 0.75 사용할까?

너무 낮으면:

메모리 낭비

 

너무 높으면:

충돌 증가

 

즉 균형값.

---

27. JDK8 이전 문제

충돌 많아지면:

LinkedList 길어짐

 

최악:

O(N)

 

성능 가능.

---

28. JDK8 개선

JDK8부터:

충돌 너무 많으면 Tree 변환

 

합니다.

---

29. TreeNode 등장

즉:

LinkedList
↓
Red-Black Tree

 

변환.

---

30. 왜 Tree로 바꿀까?

LinkedList:

검색 O(N)

 

Tree:

검색 O(logN)

 

가능.

---

31. Tree 변환 조건

대표 기준:

bucket node >= 8

 

정도.

---

32. 다시 줄어들면?

node 수 감소 시:

다시 LinkedList 복귀

 

가능.

---

33. HashMap은 Thread-safe 아니다

매우 중요.

멀티스레드 환경에서:

동시 수정 위험

 

존재.

---

34. 왜 위험할까?

예:

• resize 동시 발생
• 데이터 유실
• 무한 루프

과거엔 실제 발생 가능.

---

35. 멀티스레드에서는?

대신:

 

ConcurrentHashMap

 

사용.

---

36. HashMap에서 null 허용

HashMap 특징:

항목	허용 여부
null key	O (1개)
null value	O

---

37. TreeMap과 차이

TreeMap 은:

정렬 지원

 

하지만:

O(logN)

 

성능.

HashMap보다 느림.

---

38. LinkedHashMap

LinkedHashMap 은:

입력 순서 유지

 

가능.

내부적으로:

LinkedList 추가 유지

 

구조.

---

39. Spring 내부에서도 HashMap 많이 사용

대표 사례:

• Bean 저장
• Cache
• Request Parameter
• Session

등.

---

40. 실무 성능 팁

매우 중요.

---

초기 용량 지정

 

new HashMap<>(10000);

 

resize 감소 가능.

---

mutable key 사용 금지

매우 위험.

---

41. 왜 mutable key 위험할까?

예:

user.name 변경

 

하면:

hashCode 값 변경 가능

 

즉:

Map에서 못 찾는 상황

 

가능.

---

42. 그래서 key는 보통 immutable 사용

대표:

• String
• Integer
• UUID

등.

---

43. HashMap 시간복잡도

작업	평균
put	O(1)
get	O(1)
remove	O(1)

충돌 심하면:

O(logN)

 

가능.

---

44. 실무에서 자주 하는 실수

1) equals/hashCode 미구현

조회 실패 가능.

2) mutable 객체를 key로 사용

매우 위험.

3) resize 비용 무시

대량 데이터 시 성능 영향 가능.

4) 멀티스레드에서 HashMap 사용 

동시성 문제 가능.

---

45. 핵심 흐름 요약

key.hashCode()
↓
bucket 위치 계산
↓
충돌 시 equals 비교
↓
저장/조회 수행

 

---

46. 가장 중요한 핵심 한 줄

HashMap은
“배열 + Hash + 충돌 처리 구조를 이용해
빠른 조회를 제공하는 자료구조”

 

입니다.

---

47. 정리

HashMap은 단순 key-value 저장소가 아닙니다.

실제로는:

• Hash 알고리즘
• bucket 구조
• collision 처리
• Tree 최적화
• resize 전략

전체와 연결되는 Java 핵심 자료구조입니다.

특히 실무에서는:

• hashCode()/equals()
• collision
• resize
• ConcurrentHashMap
• immutable key

를 정확히 이해하는 것이 매우 중요합니다.

다음 글에서는:

Hash 충돌 처리 방식

을 chaining, open addressing, TreeNode, hash flooding 공격 대응까지 포함해서 깊게 정리해보겠습니다.