[Effective Kotlin] 41 - hashCode의 규약을 지켜라

Any 클래스에는 오버라이드 할 수 있는 hashCode 함수가 있습니다. hashCode 함수는 수많은 컬렉션과 알고리즘에 사용되는 자료 구조인 해시 테이블을  구축할 때 사용됩니다.

 

해시 테이블

컬렉션에 요소를 빠르게 추가하고, 컬렉션에서 요소를 빠르게 추출해야 할때 사용할 수 있는 컬렉션으로 Set와 Map이 있습니다. 이 둘은 중복을 허용하지 않습니다. 따라서 요소를 추가할 때, 일단 동일한 요소가 이미 들어 있는지 확인해야 합니다.

배열 또는 링크드 리스트를 기반으로 만들어진 컬렉션은 요소가 포함되어 있는지 확인하는 성능이 좋지 않습니다. 요소가 포함되어 있는지 확인할 때 하나 하나 모든 요소와 비교해야 하기 때문입니다. 

이럴 때 사용할 수 있는 컬렉션이 해시 테이블입니다. 해시 테이블은 각 요소에 숫자를 할당하는 함수가 필요합니다. 이 함수를 해시 함수라고 부르며 같은 요소라면 항상 같은 숫자를 리터합니다.

해시 테이블의 개념은 컴퓨터 과학에서 매우 많이 사용됩니다. 예를 들어 데이터베이스, 인터넷 프로토콜, 여러 언어의 표준 라이브러리 컬렉션에서 사용됩니다. 코틀린/JVM에 있는 기본 Set(LinkedHashSet)와 기본 Map(LinkedHashMap)도 이를 사용합니다.

(일반적으로 hashCode 함수는 Int를 리턴하므로, 32비트 부호 있는 정수(4,294,967,296)만큼 버킷이 만들어집니다.)

 

 

 

가변성과 관련된 문제

요소가 추가될 때만 해시 코드를 계산합니다. 요소가 변경되어도 해시 코드는 계산되지 않습니다. 또한 버킷 재배치도 이루어지지 않습니다. 그래서 기본적인 LinkedHashSet와 LinkedHashMap의 키는 한 번 추가한 요소를 변경할 수 없습니다.

data class FullName {
	var name: String,
    var surname: String
}

val person = FullName("Maja", "Markiewicz")
val s = metableSetOf<FullName>()
s.add(person)
person.surname = "Moskala"
print(person) // FullName(name=Maja, surname=Moskala)
print(person in s) // false
print(s.first() == person) // true

그래서 해시 등의 'mutable 프로퍼티로 요소를 조합하는 자료 구조'에서는 mutable 객체가 사용되지 않습니다. 따라서 Set와 Map의 키로 mutable 요소를 사용하면 안되며, 사용하더라도 요소를 변경해서는 안됩니다.

 

hashCode의 규약

• 어떤 객체를 변경하지 않았다면(equals에서 비교에 사용된 정보가 수정되지 않는 이상), hashCode는 여러 번 호출해도 그결과가 항상 같아야 합니다.
  • 일관성을 유지하기 위해서 hashCode가 필요하는 것입니다.
• equals 메서드의 실행 결과로 두 객체가 같다고 나온다면, hashCode 메서드의 호출 결과도 같다고 나와야 합니다.
  • 이 조건을 충족하지 않으면 컬렉션 내부에 요소가 들어가 있는지 제대로 확인할 수 없습니다.

이 밖에 필수는 아니지만, 제대로 사용하려면 지켜야 하는 요구 사항이 있는데, 바로 최대한 요소를 넓게 퍼뜨려야 한다는 것입니다. (다른 요소라면 최대한 다른 해시 값을 갖는 것이 좋습니다.)

 

hashCode 구현하기

일반적으로 data 한정자를 붙이면, 코틀린이 알아서 적당한 equals와 hashCode를 정의해 주므로, 이를 직접 정의할 일은 거의 없습니다. 다만 equals를 따로 정의했다면, 반드시 hashCode도 함께 정의해 줘야 합니다. equals를 따로 정의하지 않았다면, 정당한 이유가 없는 이상 hashCode를 따로 정의하지 않는 것이 좋습니다. (equals로 같은 요소라고 판정되는 요소는 hashCode가 반드시 같은 값을 리턴해야 합니다.)

 

일반적으로 해시 코드는 모든 해시 코드 값들을 더해서 만들게 됩니다. 더하는 과정마다 이전까지의 결과에 31을 곱한 뒤 더해 줍니다. (물론 31일 필요는 없지만, 관례적으로 31을 많이 사용합니다.)