[Java] hashCode() Implementation

배경

hashCode()는 주로 해시 기반의 컬렉션에서 객체를 저장하고 검색하는 데 사용됩니다. 오늘은 data class, Integer, Boolean, String에서 이 함수가 각각 어떻게 구현되었는지 알아보고자 합니다.

hashCode() for data class

data class User(
    val id: Int,
    val age: Int,
    val isStudent: Boolean,
    val firstName: String,
    val lastName: String,
) {
    init {
        hashCode()
    }
}

위 코틀린 data class를 디컴파일 하면 아래와 같은 자바 코드가 생성됩니다.

public int hashCode() {
  int var10000 = ((Integer.hashCode(this.id) * 31 + Integer.hashCode(this.age)) * 31 + Boolean.hashCode(this.isStudent)) * 31;
  String var10001 = this.firstName;
  var10000 = (var10000 + (var10001 != null ? var10001.hashCode() : 0)) * 31;
  var10001 = this.lastName;
  return var10000 + (var10001 != null ? var10001.hashCode() : 0);
}

• int, boolean에 대해 hashCode를 호출하고 31을 곱해 더해줍니다.
• string 또한 널 체크를 해준 뒤 hashCode()를 호출하고 31을 곱해 더해줍니다.
• lastName에 대해서만 31을 곱하지 않고 그대로 더해줍니다.

Integer.hashCode()

public static int hashCode(int var0) {
    return var0;
}

• 값을 그대로 반환합니다.

Boolean.hashCode()

public static int hashCode(boolean var0) {
    return var0 ? 1231 : 1237;
}

• 불리언 값에 따라 1231, 1237이라는 임의의 소수를 반환합니다.
• 소수를 반환하는 이유는 나누어 떨어지지 않게 함으로써 해시 충돌을 최소화하기 위함입니다. 반대로 boolean에 대해 소수가 아닌 1000, 2000을 반환한다고 가정하면, 해시테이블의 크기가 8인 경우 1000 % 8 == 2000 % 8이므로 true 및 false가 구분이 되지 않습니다.
• 2, 3 같은 작은 소수가 아니라 1231, 1237이라는 큰 소수를 사용한 이유는, 해시테이블 객체를 고르게 분산시키기 위함입니다.

hashCode() for String

// StringUTF16.class
public static int hashCode(byte[] var0) {
    int var1 = 0;
    int var2 = var0.length >> 1;

    for(int var3 = 0; var3 < var2; ++var3) {
        var1 = 31 * var1 + getChar(var0, var3);
    }

    return var1;
}

• 문자가 “banana”이라고 하면, [’b’ * 31 * 31 + ‘a’ * 31 + ‘n’]를 반환합니다.
• var0.length >> 1: 절반까지만 반복문을 돌기 위함입니다. hashCode()의 속도를 2배 빠르게 하는 대신, 해시 충돌 확률이 조금 올라가는 트레이드 오프가 발생합니다.
• 왜 31을 곱하는가?(GPT 4.0)
  1. 좋은 해시코드 분포: 31은 소수(prime number)입니다. 소수를 해시 함수에서 곱셈 상수로 사용하는 것은 해시 충돌을 줄이고, 해시 테이블 전체에 걸쳐 키의 분포를 더 균일하게 만드는 데 도움이 됩니다. 이는 특히 크기가 소수인 해시 테이블에서 유리합니다.
  2. 곱셈과 시프트 연산의 최적화: 31을 곱하는 것은 컴퓨터에서 비교적 효율적으로 수행할 수 있습니다. 특히, 31은 2^5 - 1과 같이 표현될 수 있어, 곱셈을 비트 시프트와 뺄셈으로 대체할 수 있습니다(예: x * 31은 x << 5 - x와 동일). 이는 곱셈 연산보다 더 적은 CPU 사이클을 사용하여 실행할 수 있어 성능상의 이점을 제공합니다.
  3. 역사적인 이유와 전통: Joshua Bloch가 "Effective Java"에서 언급했듯이, 31을 해시코드 계산에 사용하는 관행은 오래된 전통에 기반하고 있으며, 이 숫자가 제공하는 성능과 분포상의 이점으로 인해 널리 받아들여져 왔습니다.
  결론적으로, 31을 곱하는 것은 해시코드 생성시 충돌을 줄이고, 데이터의 균일한 분포를 도모하며, 계산 효율성을 높이기 위한 선택입니다. 이러한 이유로, Java를 포함한 많은 프로그래밍 언어와 라이브러리에서 문자열이나 다른 복합 데이터 타입의 해시 함수를 구현할 때 31을 사용하는 것을 볼 수 있습니다.
• ⇒ 요약: 소수이면서 32 - 1이라는 값이어서 비트 연산에 유리하기 때문에 관행적으로 사용합니다.

References

https://stackoverflow.com/questions/3912303/boolean-hashcode