Java Hash 충돌(Hash Collision) 처리 방식 완벽 이해하기

Java Hash 충돌(Hash Collision) 처리 방식 완벽 이해하기

Java의 HashMap 을 공부하다 보면 반드시 등장하는 핵심 개념이 바로:

Hash 충돌(Hash Collision)

입니다.

HashMap의 핵심 목표는:

빠른 조회 O(1)

 

입니다.

그런데 현실에서는:

서로 다른 key인데
같은 bucket 위치

 

가 나올 수 있습니다. (버킷은 16개 뿐인데 hashCode는 40억 개 이상 가능 : A 65%16=1, Q 81%16 = 1 )

즉:

hashCode()가 달라도
최종 bucket index는 같아질 수 있음

 

입니다.

이 문제를 해결하는 것이 바로:

Hash 충돌 처리 방식

입니다.

이번 글에서는:

• Hash Collision 원리
• Chaining
• Open Addressing
• JDK8 TreeNode
• Hash Flooding 공격
• 실무 성능 이슈

까지 깊게 정리해보겠습니다.

---

1. Hash 충돌이란?

Hash 충돌은:

서로 다른 key가 같은 bucket 위치로 들어가는 현상

입니다.

---

2. 왜 발생할까? (Hash Collision 원리)

예:

배열 크기 = 16

 

인데:

hash 값은 수억 개 가능

 

합니다.

즉:

16칸에 무한한 값을 넣어야 함

 

이므로 충돌은 필연적.

---

3. 예시

"A".hashCode() = 100
"B".hashCode() = 116

 

배열 길이:

16

 

이면:

100 % 16 = 4
116 % 16 = 4

 

즉:

둘 다 bucket 4

 

충돌 발생.

---

4. 충돌 없애는 건 불가능할까?

완전히 제거는 현실적으로 어려움.

대신 목표는:

충돌을 효율적으로 처리

 

하는 것.

---

5. 대표 충돌 처리 방식

대표적으로:

방식	설명
Chaining	bucket 내부 연결
Open Addressing	다른 빈칸 탐색

---

6. Java HashMap 방식

Java HashMap은 기본적으로:

Separate Chaining

 

사용.

---

7. Chaining이란?

충돌 발생 시:

같은 bucket 내부 연결

 

방식.

---

8. 구조 예시

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

 

형태.

---

9. 왜 가능한가?

bucket 하나가 실제로는:

Node 시작점

 

이기 때문.

---

10. 내부 Node 구조

대략 이런 느낌.

 

class Node<K,V> {

    int hash;
    K key;
    V value;
    Node<K,V> next;
}

 

---

11. put() 시 동작

예:

 

map.put("A", 1);
map.put("B", 2);

 

둘 다 같은 bucket이면:

LinkedList 연결

 

수행.

---

12. 조회 시 동작

 

map.get("B");

 

실제로:

bucket 찾기
↓
LinkedList 순회
↓
equals() 비교

 

수행.

---

13. 왜 equals() 중요할까?

충돌 상황에서는:

hash만으로 구분 불가

 

하기 때문.

즉:

equals()로 최종 확인

 

필요.

---

14. Chaining 장점

장점	설명
구현 단순	O
충돌 대응 쉬움	O
삭제 쉬움	O

---

15. Chaining 단점

충돌 많아지면:

LinkedList 길어짐

 

즉:

검색 O(N)

 

가능.

---

16. 최악의 경우

모든 key가 같은 bucket이면:

사실상 LinkedList

 

됩니다.

즉:

HashMap인데 O(N)

 

상황 가능.

---

17. 그래서 JDK8 개선 등장

Java 8부터:

충돌 너무 많으면 Tree 변환

 

도입.

---

18. TreeNode 구조

즉:

LinkedList
↓
Red-Black Tree

 

변환.

---

19. 왜 Tree 사용할까?

LinkedList:

검색 O(N)

 

Tree:

검색 O(logN)

 

가능.

---

20. Tree 변환 기준

대표 기준:

bucket node >= 8

 

정도.

---

21. 다시 줄어들면?

node 감소 시:

Tree → LinkedList 복귀

 

가능.

---

22. 왜 항상 Tree 안 쓸까?

Tree는:

• 메모리 더 사용
• 구조 더 복잡
• 작은 데이터엔 비효율

즉 상황 따라 선택.

---

23. Open Addressing이란?

다른 충돌 처리 방식.

구조:

충돌 시 다른 빈 bucket 탐색

 

---

24. 예시

bucket[4] 충돌
↓
bucket[5] 확인
↓
비었으면 저장

 

---

25. 대표 방식

방식	설명
Linear Probing	순차 탐색
Quadratic Probing	제곱 간격
Double Hashing	추가 hash 사용

---

26. Open Addressing 장점

장점	설명
메모리 locality 좋음	O
추가 Node 불필요	O

---

27. Open Addressing 단점

문제:

삭제 구현 어려움

 

그리고:

충돌 많아지면 성능 급락

 

가능.

---

28. Java HashMap은 왜 Chaining 선택했을까?

주요 이유:

구현 안정성

 

과:

충돌 대응 유연성

 

입니다.

---

29. Load Factor 중요

HashMap 기본값:

0.75

 

---

30. 의미

배열 16칸이면:

12개 저장 시 resize

 

발생.

---

31. 왜 resize 할까?

목표:

충돌 감소

 

입니다.

---

32. resize 시 문제

모든 데이터:

rehash

 

필요.

즉 비용 큼.

---

33. Hash Flooding 공격

매우 중요한 보안 이슈.

---

34. Hash Flooding이란?

공격자가:

같은 bucket으로 몰리는 key 생성

 

하는 공격.

---

35. 결과

HashMap 성능 O(N)

 

까지 저하 가능.

즉 CPU 폭주 가능.

---

36. 실제로 발생했나?

실제로 여러 언어에서 문제 발생.

대표:

• Java
• PHP
• Python

등.

---

37. Java 대응

JDK8부터:

TreeNode 도입

 

으로 대응 강화.

즉:

최악 O(logN)

 

수준 방어 가능.

---

38. hashCode 품질 중요

좋은 hashCode 특징:

고르게 분산

 

되는 것.

---

39. 안 좋은 hashCode 예시

 

return 1;

 

이러면:

모든 객체 충돌

 

가능.

---

40. String hashCode는 잘 설계됨

String 의 hashCode는:

분산 효율 매우 좋게 설계

 

되어 있음.

---

41. mutable key 위험

예:

 

user.name 변경

 

하면:

hashCode 달라질 수 있음

 

즉:

Map 조회 실패 가능

 

---

42. 그래서 immutable key 추천

대표:

• String
• Integer
• UUID

등.

---

43. 실무 성능 팁⭐⭐⭐⭐⭐

초기 크기 지정 - resize 감소 가능.

new HashMap<>(10000);

 

hashCode 잘 구현  - 충돌 감소 중요.

equals/hashCode 같이 구현 - 반드시 세트.

---

44. 시간복잡도 정리

상황	성능
일반	O(1)
충돌 많음	O(N)
TreeNode 사용	O(logN)

---

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

1) equals만 구현

Map 동작 이상 가능.

2) hashCode 품질 무시

충돌 증가 가능.

3) mutable 객체 key 사용

매우 위험.

4) HashMap은 항상 O(1)이라고 믿음

충돌 많으면 아님.

---

46. 핵심 흐름 요약

hashCode 계산
↓
bucket 결정
↓
충돌 발생 시
LinkedList 또는 Tree 저장
↓
equals() 비교로 최종 확인

 

---

47. 가장 중요한 핵심 한 줄

Hash 충돌은 피할 수 없지만
효율적으로 처리하는 것이 HashMap의 핵심이다

 

입니다.

---

48. 정리

Hash 충돌 처리 방식은 단순 자료구조 개념이 아닙니다.

실제로는:

• HashMap 성능
• 보안 공격 대응
• Tree 최적화
• equals/hashCode 설계
• JVM 컬렉션 성능

전체와 연결되는 매우 중요한 핵심 개념입니다.

특히 실무에서는:

• Chaining
• TreeNode
• collision
• resize
• hash flooding

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

다음 글에서는:

equals()와 hashCode()

를 Object 계약(contract), Set/Map 동작 원리, Lombok 주의점, 실무 장애 사례까지 포함해서 깊게 정리해보겠습니다.