자바 컬렉션 한눈에 보기 1편: 해시부터 hashCode, equals, 충돌까지

자바 컬렉션 한눈에 보기 1편: 해시부터 hashCode, equals, 충돌까지

---

들어가며

HashMap, HashSet, ConcurrentHashMap을 제대로 이해하려면 제일 먼저 hash를 잡아야 한다.
문제는 hash를 처음 배우면 설명이 지나치게 압축돼 있다는 점이다.

• 입력을 고정 길이 값으로 바꾼다
• 빠른 탐색을 위해 쓴다
• 충돌이 난다

틀린 말은 아니지만, 이 정도 설명만으로는 왜 HashMap이 빠른지,
왜 equals()와 hashCode()를 함께 구현해야 하는지까지 연결되지 않는다.

이번 글은 hash를 수학적 정의보다
왜 비교를 줄이기 위해 hash라는 우회로를 쓰는가라는 관점에서 정리한다.

---

목차

• 1) 해시란 무엇인가
• 2) Java hashCode는 어떻게 동작하는가
• 3) equals와 hashCode는 왜 같이 가야 하는가
• 4) 해시 충돌은 왜 생기고 어떻게 해결할까

---

1) 해시란 무엇인가

1-1) 왜 hash가 필요할까

데이터가 리스트에만 들어 있다면, 특정 원소를 찾기 위해 보통 앞에서부터 하나씩 비교해야 한다.

for (User user : users) {
    if (user.getId().equals(1024L)) {
        return user;
    }
}

데이터가 몇 개 없으면 별 문제 없다.
하지만 데이터가 커질수록 "매번 처음부터 끝까지 훑는 비용"은 부담이 된다.

이때 필요한 것은 값을 직접 전부 비교하기 전에,
저장 위치 후보를 빠르게 좁힐 수 있는 주소 체계다.

hash는 바로 그 역할을 한다.

1-2) hash를 가장 실무적으로 정의하면

hash는 어떤 key를 받아 정수 값으로 바꾸고,
그 값을 이용해 저장 위치 후보를 빠르게 좁히는 방식이다.

예를 들어 "user:1024"라는 문자열 자체를 배열 인덱스로 쓸 수는 없다.
하지만 hashCode()를 거치면 정수 값으로 압축할 수 있다.

"user:1024" -> 18392041
18392041 % 16 = 9

그러면 전체 공간을 전부 탐색하는 대신
"9번 bucket부터 보자"라는 전략이 가능해진다.

1-3) hash의 본질은 유일성보다 후보 축소다

중요한 오해가 하나 있다.
hash는 서로 다른 key를 절대 겹치지 않는 숫자로 바꾸는 마법이 아니다.

진짜 본질은 이것이다.

• 전체를 비교하지 않고
• 저장 위치 후보를 빠르게 좁히고
• 그 좁혀진 범위 안에서만 최종 비교하게 만든다

즉 hash는 비교 자체를 없애는 기술이 아니라,
비교 범위를 줄이는 기술이다.

1-4) 그림으로 보면 더 쉽다

hash가 없는 경우는 전체를 선형 탐색하기 쉽다.

hash가 있는 경우는 먼저 bucket 후보를 고른다.

즉 전체 탐색에서 bucket 내부 비교로 탐색 범위가 줄어든다.

---

2) Java hashCode는 어떻게 동작하는가

2-1) hashCode()가 필요한 이유

HashMap이나 HashSet은 key 전체를 매번 처음부터 끝까지 비교하지 않는다.
먼저 hashCode()를 호출해 bucket 후보를 정하고,
그 다음에야 equals()로 최종 확인한다.

즉 hashCode()는 "같은가"를 직접 판정하는 메서드가 아니라
"어디서 먼저 찾아볼까"를 빠르게 정하는 힌트다.

2-2) 좋은 hashCode()의 핵심은 세 가지다

좋은 hashCode()는 보통 아래 조건을 만족해야 한다.

• 동등한 객체는 같은 hash 값을 가져야 한다
• 실행 중 객체 상태가 바뀌지 않는다면 hash 값도 안정적이어야 한다
• 다른 객체들은 가능하면 고르게 퍼지는 편이 좋다

즉 절대적인 유일성이 아니라 일관성 + 분산이 중요하다.

2-3) 왜 31이 자주 등장할까

Java 예제에서 흔히 보이는 패턴은 이렇다.

int result = 1;
result = 31 * result + Objects.hashCode(id);
result = 31 * result + Objects.hashCode(name);

이 식은 필드 값을 단순히 더하는 것이 아니라,
기존 결과값에 새 필드 hash를 순서 있게 섞어 넣는 역할을 한다.

31이 많이 쓰이는 이유는 보통 아래처럼 설명한다.

• 홀수 소수라 분산에 유리하다
• 너무 큰 수가 아니라 계산 비용이 과하지 않다
• 31 * x는 오래전부터 구현/최적화 측면에서 실용적인 선택으로 여겨졌다

즉 31은 신비한 숫자라기보다,
오래 검증된 관습적 선택지라고 이해하면 충분하다.

2-4) String.hashCode()도 같은 아이디어다

개념적으로 String은 아래처럼 누적 계산한다고 보면 된다.

int h = 0;
for (char c : value) {
    h = 31 * h + c;
}

이 덕분에 문자열의 순서 정보가 반영된다.
즉 "abc"와 "cba"는 같은 문자 집합이라도 다른 hash가 나오기 쉽다.

2-5) 실무에서는 무엇을 기억해야 할까

요즘은 직접 31 공식을 쓰기보다 Objects.hash(...)를 많이 쓴다.

@Override
public int hashCode() {
    return Objects.hash(id, email);
}

중요한 것은 31 공식을 외우는 것이 아니라,
동등성 판단에 쓰는 필드를 기준으로 hash도 같이 만들어야 한다는 점이다.

---

3) equals와 hashCode는 왜 같이 가야 하는가

3-1) 역할이 다르다

두 메서드는 비슷해 보이지만 같은 일을 하지 않는다.

• hashCode(): bucket 후보를 좁힌다
• equals(): 그 안에서 진짜 같은지 최종 판단한다

즉 HashMap과 HashSet의 동등성 판단은
한 번의 비교가 아니라 2단계 협업이다.

3-2) 왜 equals()만 재정의하면 안 될까

예를 들어 아래 객체를 생각해 보자.

Member a = new Member(1L, "kim");
Member b = new Member(1L, "kim");

개발자 입장에서는 같은 회원이라고 보고 싶어 equals()만 재정의할 수 있다.
하지만 hashCode()를 그대로 두면 두 객체가 서로 다른 bucket으로 갈 수 있다.

그러면 HashSet이나 HashMap은 아예 같은 bucket 안에서 둘을 만나 보지도 못한다.

즉:

• equals()는 true
• 그런데 hashCode()는 다름
• 그러면 서로 다른 bucket으로 분산
• 결국 같은 값으로 인식되지 않을 수 있음

이것이 "같으면 hashCode도 같아야 한다"는 계약의 본질이다.

3-3) 반대 방향은 괜찮다

반대로 hash 값이 같아도 equals()가 false일 수는 있다.
이건 해시 충돌일 뿐이다.

즉 허용되는 방향은 이쪽이다.

• hashCode()는 같을 수 있다
• 하지만 equals()는 false일 수 있다

허용되지 않는 방향은 이거다.

• equals()가 true인데
• hashCode()가 다르다

3-4) 코드 예시로 보면 더 명확하다

잘못된 예시는 보통 이런 모양이다.

public class Member {
    private final Long id;
    private final String name;

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (!(o instanceof Member other)) {
            return false;
        }
        return Objects.equals(id, other.id);
    }
}

올바른 방향은 동등성 기준과 hash 기준을 맞추는 것이다.

public class Member {
    private final Long id;
    private final String name;

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (!(o instanceof Member other)) {
            return false;
        }
        return Objects.equals(id, other.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}

---

4) 해시 충돌은 왜 생기고 어떻게 해결할까

4-1) 충돌은 피할 수 없는 전제다

입력 key 공간은 매우 넓다.
반면 hash table bucket 수는 유한하다.

예를 들어 bucket이 16개라면,
아무리 좋은 hash 함수를 써도 수많은 key를 16칸 안에 분산해야 한다.

즉 서로 다른 key가 같은 bucket으로 가는 일은 구조적으로 피할 수 없다.
이것을 해시 충돌(collision)이라고 부른다.

중요한 점은 충돌이 "버그"가 아니라,
hash 기반 자료구조라면 원래 감수해야 하는 기본 조건이라는 것이다.

4-2) 충돌이 생겨도 왜 괜찮을까

충돌은 "서로 다른 key가 같은 bucket 후보를 가졌다"는 뜻이지,
같은 key라는 뜻이 아니다.

결국 bucket 안에서 다시 비교하면 된다.

즉 hash는 전체 비교를 없애는 것이 아니라,
충돌이 있더라도 평균적으로 비교 범위를 많이 줄여 주는 구조다.

4-3) 대표적인 충돌 해결 방식 1: 체이닝

체이닝(chaining)은 같은 bucket에 들어온 원소를
연결 리스트나 트리 구조로 매다는 방식이다.

Java HashMap은 기본적으로 이 방식에 가깝다.
Java 8+에서는 충돌이 많아지면 bucket 내부를 트리화해서 탐색 비용을 낮춘다.

4-4) 대표적인 충돌 해결 방식 2: 오픈 어드레싱

오픈 어드레싱(open addressing)은 충돌이 나면
같은 bucket 내부 구조를 확장하는 대신,
table 안의 다른 빈 칸을 찾아가는 방식이다.

예를 들어 선형 탐사는 이런 감각이다.

원래 자리 충돌 -> 다음 칸 확인 -> 또 충돌 -> 다시 다음 칸 확인

대표 방식은 아래와 같다.

• 선형 탐사
• 제곱 탐사
• 이중 해싱

Java HashMap이 이 방식을 쓰는 것은 아니지만,
해시 충돌 해결 전략을 이해할 때 체이닝과 함께 반드시 같이 나오는 축이다.

4-5) 결국 핵심은 충돌 자체보다 관리 방식이다

해시 자료구조를 볼 때 중요한 질문은 "충돌이 있느냐"가 아니다.
충돌은 원래 있다.

진짜 질문은 이거다.

• 충돌이 났을 때 bucket 안에서 어떻게 탐색하는가
• 충돌이 심해지면 어떻게 구조를 바꾸는가
• table 크기는 언제 늘리는가

이 질문이 다음 글의 HashMap 내부 동작으로 자연스럽게 이어진다.

---

마치며

Hash를 이해하고 나면 HashMap과 HashSet이 갑자기 덜 신비해진다.
둘 다 결국 같은 원리 위에 서 있기 때문이다.

• 먼저 hashCode()로 후보를 좁히고
• 그 후보 안에서 equals()로 최종 판단하고
• 충돌은 기본 전제로 받아들이며 관리한다

이 세 가지를 이해하면 Collection의 절반은 이미 풀린 셈이다.

---

한 줄 정리

hash의 핵심은 "유일한 숫자를 만드는 것"이 아니라,
전체 비교를 하지 않기 위해 저장 위치 후보를 빠르게 좁히고, 충돌은 관리 가능한 전제로 다루는 것이다.