41장 - hashCode의 규약을 지켜라

해시 테이블

해시 테이블은 각 요소에 숫자를 할당하는 함수가 필요합니다.

이 함수를 해시 함수라고 부릅니다.

같은 요소라면 항상 같은 숫자를 리턴합니다.

 

해시 함수가 다음과 같은 특성을 가지는 것이 좋습니다.

• 빠르다.
• 충돌이 적다

해시 함수는 각각의 요소에 특정한 숫자를 할당하고, 이를 기반으로 요소를 다른 버킷에 넣습니다.

해시 함수의 기본조건인 같은 요소라면 항상 같은 숫자를 리턴한다에 의해 같은 요소는 항상 동일한 버킷에 넣게 됩니다.

 

가변성과 관련된 문제

요소를 추가할 때만 해시 코드를 계산합니다.

즉, 요소가 변경되어도 해시 코드는 계산되지 않으며 버킷의 재배치로 이루어지지 않습니다.

Set과 Map의 키로 mutable 요소를 사용하면 안 되며, 사용하더라도 요소를 변경하면 안 됩니다.

 

hasCode의 규약

• 어떤 객체를 변경하지 않았다면, hashCode는 여러 번 호출해도 그 결과가 항상 같아야 한다
• equals 메서드의 실행 결과로 두 객체가 같다고 나온다면, hashCode 메서드의 호출 결과도 같아야 한다.

 

그렇지 않다면 컬렉션 내부에 요소가 들어 있는지 제대로 확인하지 못하는 문제가 발생할 수 있습니다.

class FullName(
    var name: String,
    var surname: String,
){
    override fun equals(other: Any?): Boolean {
        return other is FullName
                && other.name == name
                && other.surname == surname
    }
}

fun main() {
    val set = mutableSetOf<FullName>()
    set.add(FullName("Marcin","Moskala"))
    val fullName = FullName("Marcin","Moskala")
    print(fullName in set) //false
    print(fullName == set.first()) //true
}

 

또한 hashCode가 극단적으로 동일한 숫자를 리턴한다면 성능이 크게 떨어집니다.

 

hashCode 직접 만들기

class FullName(
    var name: String,
    var surname: String,
){
    override fun equals(other: Any?): Boolean {
        return other is FullName
                && other.name == name
                && other.surname == surname
    }

    override fun hashCode(): Int {
        var result = name.hashCode()
        result = result * 31 + surname.hashCode()
        return result;
    }
}

fun main() {
    val set = mutableSetOf<FullName>()
    set.add(FullName("Marcin","Moskala"))
    val fullName = FullName("Marcin","Moskala")
    println(fullName in set) //true
    println(fullName == set.first()) //true
}

일반적으로 모든 해시 코드의 값을 더하며 관례적으로 31을 사용합니다.

코틀 stdlib에는 hashcode를 지원하는 함수가 없습니다.

기본적으로 지원하지 않는 이유는 직접 구현할 일이 거의 없기 때문입니다.

가장 중요한 규칙은 equals와 일관된 결과가 나와야 한다입니다.

같은 객체라면 언제나 같은 값을 리턴하게 만들어주세요.

 

31을 사용하는 이유

31N = 32N - N입니다.

32는 2^5로 어떤 수에 대한 32를 곱한 값은 shift 연산을 통해 쉽게 구현할 수 있습니다.

따라서 31 * i = (i << 5) - i의 식이 성립합니다.

곱셈보다 비트 연산이 성능이 훨씬 빠르기 때문에 31이라는 값을 선택한 것입니다.