Prime Number 31

🔬 자바에서 hashCode() 구현 시 사용되는 숫자 31의 의미와 이유

1. 서론 – hashCode()는 왜 중요한가?

자바의 hashCode()는 단순한 도우미 메서드가 아닙니다. 이는 HashMap, HashSet, Hashtable과 같은 해시 기반 컬렉션의 핵심 엔진으로, 객체의 논리적 동일성 여부를 빠르게 판단하고, 해시 버킷을 정확하게 분배하는 역할을 합니다.

"좋은 해시코드란, 같은 객체에 대해서는 항상 같은 값을 반환하고, 다른 객체에 대해서는 해시 충돌 없이 분산되는 값이어야 한다."

 

2. 해시코드 계산에 사용되는 상수 31의 정체

🔹 기본 구현 형태

@Override
public int hashCode() {
    int result = 17;
    result = 31 * result + (name != null ? name.hashCode() : 0);
    result = 31 * result + age;
    return result;
}

여기서 곱셈 계수로 사용된 31은 단순한 숫자가 아니라, 아래와 같은 수학적·컴퓨터공학적 이유에 기반하여 선택된 상수입니다.

 

3. 수학적 관점: 소수(Prime Number)는 충돌 회피의 열쇠

✅ 3.1 소수는 해시 공간을 균일하게 분산시킨다

• 필드들이 같은 값을 갖더라도 순서가 다르면 다른 해시코드가 되도록 해야 합니다.
• 이때 가중치로 소수(prime number)를 곱하면 다양한 조합에 대해 충돌을 줄일 수 있습니다.
• 수학적으로도 소수는 mod 연산 기반의 해시 테이블에서 최대 분산 효과를 보입니다.

예) "abc"와 "acb"는 순서만 다르지만, 31을 곱함으로써 다른 해시값 생성

 

✅ 3.2 거듭제곱 효과

문자열의 경우 다음과 같이 31의 거듭제곱을 이용해 가중치를 부여합니다:

s[0] * 31ⁿ⁻¹ + s[1] * 31ⁿ⁻² + ... + s[n-1]

이는 "문자의 위치"에 따라 해시코드가 완전히 달라지게 하며, 순열 간 해시 충돌을 효과적으로 줄입니다.

 

4. 컴퓨터 구조 관점: 31은 비트 연산 최적화에 적합한 수

✅ 4.1 31은 2⁵ - 1 (즉, 32 - 1)

• JVM과 컴파일러는 31 * x를 (x << 5) - x로 변환해 곱셈을 빠른 비트 연산으로 최적화합니다.
• x << 5는 32를 곱하는 연산이며, 이에서 x를 빼면 곧 31을 곱한 결과가 됩니다.

int hash = 31 * x;
// 실제로는 다음처럼 최적화됨
int hash = (x << 5) - x;

👉 CPU에서 곱셈보다 비트 연산이 훨씬 빠르므로, 이 구조는 hashCode()의 계산 속도를 향상시킵니다.

 

5. 자바 설계 관점: 표준 클래스들과의 일관성

자바의 표준 API 내부에서도 hashCode() 구현에는 대부분 31이 사용됩니다:

✅ 예시: java.lang.String

@Override
public int hashCode() {
    int h = 0;
    for (int i = 0; i < value.length; i++) {
        h = 31 * h + value[i];
    }
    return h;
}

• String은 해시코드를 자주 사용하는 대표적인 불변 객체이므로, 이 설계는 수많은 컬렉션에 영향을 미칩니다.
• 31은 그 설계의 핵심 키입니다.

 

6. 다른 수는 왜 안 되는가?

물론 다른 소수(37, 53, 97)도 사용 가능하지만, 다음과 같은 이유로 31이 널리 채택됩니다:

기준	이유
최적화	(x << 5) - x로 빠르게 연산 가능
분산성	해시 충돌 분산에 충분한 효과
짧은 길이	거듭제곱 계산 시 오버플로우 위험 적음
표준성	String, List, Map 등 자바 코어 API가 채택

🚨 너무 큰 소수를 사용하면 오히려 정수 오버플로우 위험이 커지고, 해시 공간이 비효율적으로 사용될 수 있습니다.

 

7. 실무 팁: 해시코드 설계 시 고려사항

항목	권장 사항
초기값	17 또는 1 (소수)
곱셈 계수	31 (또는 다른 소수)
null 필드	Objects.hashCode(field) 또는 (field != null ? field.hashCode() : 0)
순서 고려	필드의 순서가 중요하면 해시 순서도 동일하게 유지

 

✅ 요약

• 31은 단순한 마법 숫자가 아닌, 수학적 설계, CPU 최적화, 표준화 관점에서 완성된 선택입니다.
• 이는 자바 언어의 설계자들이 실제 운영 환경에서의 성능과 해시 충돌 문제를 해결하기 위해 전략적으로 선택한 소수입니다.
• 실무에서 hashCode()를 커스터마이징할 때도 31을 사용하는 것이 성능, 안정성, 일관성 면에서 가장 합리적인 선택입니다.

 

📘 참고 자료

• Effective Java by Joshua Bloch – Item 11: Always override hashCode() when you override equals()
• OpenJDK source code (String.java, AbstractList.java)
• JVM HotSpot Optimization Techniques