해시 충돌(Hash Collision)이란?

해시 충돌은 서로 다른 두 데이터가 동일한 해시값을 가질 때 발생하는 현상입니다.
Java에서는 객체의 hashCode() 값을 기반으로 해시 자료구조(HashMap, HashSet 등)를 구성하기 때문에, 해시 충돌이 발생할 수 있습니다.

🔹 왜 해시 충돌이 발생할까?

해시 함수는 무한한 입력(객체)을 제한된 크기의 숫자(해시값)로 변환합니다.
따라서 서로 다른 객체가 동일한 해시값을 가지는 경우가 자연스럽게 발생할 수밖에 없습니다.

ex)

Object A → hashCode() → 1234  
Object B → hashCode() → 1234  
// 서로 다른 객체인데 해시값은 같음

🔹 Java에서 해시 충돌의 예

public class User {
    String name;

    public User(String name) {
        this.name = name;
    }

    @Override
    public int hashCode() {
        return 42; // 일부러 모든 객체의 해시값을 동일하게 설정
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User)) return false;
        return name.equals(((User) o).name);
    }
}

이처럼 모든 객체의 hashCode()가 같다면, HashMap은 충돌을 자주 겪게 됩니다.
그러나 equals() 메서드가 잘 정의되어 있다면, 충돌을 구분해서 처리할 수 있습니다.

🔹 해시 충돌 시 문제점

성능 저하

원래 해시 기반 자료구조는 O(1) 속도를 기대하지만,
충돌이 많이 발생하면 O(n)까지 느려질 수 있습니다.

정확도 문제

equals()가 제대로 구현되지 않으면,
충돌로 인해 서로 다른 객체가 같다고 판단될 수 있습니다.

🔹 Java의 충돌 처리 방식 (HashMap 기준)

체이닝 방식 (Chaining)

같은 해시값을 가진 여러 엔트리를 LinkedList로 연결해 저장합니다.

트리화(Treeify)

Java 8부터, 한 해시 버킷에 저장된 엔트리 수가 많아지면
Red-Black Tree로 전환하여 탐색 성능을 O(log n)으로 개선합니다.

equals() 비교

같은 해시값을 가지더라도, 객체의 실질적 동등 여부는 equals()로 판단합니다.

✅ 정리

해시 충돌은 해시함수가 서로 다른 객체에 대해 같은 값을 반환할 때 발생합니다.

hashCode()와 equals()를 올바르게 구현하면 충돌을 안전하게 처리할 수 있습니다.

HashMap은 충돌에 대비한 구조(체이닝, 트리화)를 통해 안정적인 동작을 보장합니다.