item11: equals를 재정의하려거든 hashCode도 재정의하라

[joona95]

💡 주제

item11: equals를 재정의하려거든 hashCode도 재정의하라

📌 TO DO

• 발표 내용 작성
• 질문 작성

[joona95]

곱할 숫자를 31로 정한 이유는 31이 홀수이면서 소수이기 때문이다. 만약 이 숫자가 짝수이고 오버플로가 발생한다면 정보를 잃게 된다.

• 여기서 “정보 손실”은 해시 충돌 증가를 뜻합니다.
• 이때, 만약 계수가 짝수(예: 32)라면 곱할 때 하위 비트가 항상 0이 됩니다.
• 하위 비트 정보가 사라짐. → 해시 분포가 고르지 않음 → 충돌 확률 증가

결과적으로 31을 이용하면, 이 곱셈을 시프트 연산과 뺄셈으로 대체해 최적화할 수 있다(31 * i는 (i << 5) - i와 같다).

• “시프트 연산으로 최적화할 수 있다”는 말은 31 * i 를 (i << 5) - i 로 시프트 연산을 활용할 수 있어, 자바 컴파일러나 JIT이 내부적으로 최적화해서 수행한다는 의미입니다.

---

단, 해시 충돌이 더욱 적은 방법을 꼭 써야 한다면 구아바의 com.google.common.hash.Hashing을 참고하자.

Q. 무슨 차이가 있길래 해시 충돌이 더욱 적은지?

• 구아바 Hashing은 “더 넓은 비트폭 + 훨씬 강한 비트 섞기(mixing)”를 제공해서, 우리가 보통 쓰는 31 * result + field 방식보다 균등 분포와 충돌 저항성이 훨씬 좋음

1. 비트폭(출력 크기)이 훨씬 크다

• 보통 hashCode()는 int(32비트) 하나.

• Guava는 32비트/64비트/128비트까지 선택 가능 (murmur3_32, murmur3_128 등).

• 출력 비트가 커질수록(특히 128비트) 생일 문제에 따른 충돌 확률이 기하급수적으로 낮아짐.

2. 강한 mixing(아발란시 효과) 알고리즘

• 31 * result + x는 선형(polynomial) 조합이라 특정 패턴(0, 작은 값 반복 등)에 약하고, 하위 비트가 고르게 섞이지 않기도 해요.

• Murmur3, SipHash 같은 해시는 rotate, xor, shift, multiply를 조합하는 비선형 혼합을 반복 → 입력의 1비트만 달라도 출력 모든 비트가 랜덤처럼 뒤집히는 아발란시 효과.

• 실제로 Murmur3는 SMHasher 같은 분포 테스트에서 균등성·독립성이 훨씬 좋게 나옵니다.

3. 필드 순서/스케일에 덜 민감

• 31-다항식은 “앞 필드가 크고 뒤가 작으면 영향 불균형” 같은 편향이 생기기 쉬움.

• Guava 해시는 스트리밍 Hasher에 각 필드 타입별로 바이트 단위로 넣어서 섞기 때문에(putInt/putLong/putString 등), 필드의 배치나 스케일 편향을 강하게 완화합니다.

4. 충돌 저항성을 올리면서도 빠름

• murmur3_32/murmur3_128은 비암호학적 해시라 매우 빠르고 분포가 우수.

• (보안 공격 저항이 필요하면 sipHash24 같은 경량 보안지향 해시 선택 가능. 일반 업무에는 murmur가 충분.)

Q. 언제 써야 유의미한가?

• 큰 해시 테이블에서 충돌이 성능에 민감할 때(예: 대량 데이터 키, 복합키)

• Bloom Filter, Cuckoo/Consistent Hashing, Sharding 키처럼 균등 분포가 성능/품질에 직결될 때

• 크로스-프로세스/언어 간 동일한 해시가 필요할 때(알고리즘을 명시적으로 고정하니 재현 가능)

• 단, 자바의 컬렉션 키로 쓰려면 여전히 hashCode()는 int여야 하므로, 128비트 해시라도 최종적으로 asInt()로 접어 넣게 됩니다(그래도 내부 mixing이 좋아 충돌은 줄어듭니다). 또는 64/128비트를 별도 인덱싱/샤딩 키로 활용하세요.

---

String과 Integer를 포함해, 자바 라이브러리의 많은 클래스에서 hashCode 메서드가 반환하는 정확한 값을 알려준다.

Q. 정확한 값을 알려준다는 게 무슨 의미인지? 어떻게 알려준다는 것인지?

• 자바 표준 라이브러리 클래스(String, List, Set, Map 등) 는 hashCode()의 계산 방법이 Javadoc(공식 명세) 에 “고정된 수식” 형태로 명시되어 있습니다.

• OpenJDK Javadoc String.hashCode()

public int hashCode()
Returns a hash code for this string. The hash code for a String object is computed as
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, and ^ indicates exponentiation. (The hash value of the empty string is zero.)