앞서 Any의 오버라이드 가능 메서드 중 equals를 이야기했다면 이번엔 hashCode를 이야기해보자
왜 이 hashCode가 필요할까?
해시 테이블
배열 또는 링크드 리스트를 기반으로 만들어진 컬렉션은 요소가 포함되어 있는지 확인하는 성능이 좋지 않다. 수백 만 개의 텍스트를 선형으로 비교한다면, 꽤 오랜 시간이 걸릴 것이다.
그래서 이 성능을 좋게 만드는 해결 방법이 바로 해시 테이블이다. 해시 테이블은 각 요소에 숫자를 할당하는 함수가 필요한데, 이 함수를 해시 함수라고 부르며, 같은 요소라면 같은 숫자를 리턴한다.
추가로 해시 함수가 다음과 같은 특성이 있으면 좋다.
- 빠르다
- 충돌이 적다 (다른 값이라면 최대한 다른 숫자를 리턴한다는 의미이다)
해시 함수는 각각의 요소에 특정한 숫자를 할당하고, 이를 기반으로 요소를 다른 버킷에 넣는다. 또한 해시 함수의 기본적인 조건에 의해서, 같은 요소는 항상 동일한 버킷에 넣게 된다.
버킷은 버킷 수와 같은 크기의 배열인 해시 테이블에 보관된다. 요소를 추가하는 경우에는 해시 함수로 배치할 버킷을 계산하고 이 버킷 안에 요소를 추가한다. (버킷은 배열처럼 구현)
해시 함수의 속도는 빨라야하므로 이 처리는 굉장히 빠르게 이루어진다.
요소를 찾는 경우에도 해시 함수로 만들어지는 숫자를 활용해 버킷을 찾은 뒤, 버킷 내부에서 원하는 요소를 찾는다. 해시 함수는 같은 요소라면 같은 값을 리턴하므로 다른 버킷을 확인할 필요 없이 바로 원하는 것이 들어 있는 버킷을 찾을 수 있다!
예를 들면 아래와 같다
-
text: "How much wood wolud ad woodchunk chunk", hashcode: 3
-
text: "Peter piper picked a peck of pickled peppers", hashcode: 2
-
text: "Betty bought a bit of butter", hashcode: 1
-
text: "She sells seashells by the seashore", hashcode: 2
이 숫자를 기반으로 아래 해시테이블이 만들어진다
-
index 0 : []
-
index 1 : ["Betty bought a bit of butter"]
-
index 2 : ["Peter piper picked a peck of pickled peppers", "She sells seashells by the seashore"]
-
index 3 : ["How much wood wolud ad woodchunk chunk"]
그래서 텍스트가 해시 테이블에 있는지 확인할 때 해시코드를 계산한다.
0이면 없고 2라면 두 개의 텍스트와 비교하겠지
가변성과 관련된 문제
요소가 추가 될 때만 해시 코드를 계산한다.
위 특성은 아주 중요하다.
요소가 변경되도 해시 코드는 계산되지 않으며 버킷 재배치도 이루어지지 않는다
만약 객체 속 프로퍼티가 가변이라 변경된다 하더라도 원하는 대로 본질은 변하지 않는다.
그래서 세트와 맵의 키로 mutable 요소를 사용하면 안되고 사용하더라도 요소를 변경해서는 안된다.
hashCode 규약
hashCode는 명확한 규약이 있다
-
어떤 객체를 변경하지 않았다면 (equals에서 비교에 사용된 정보가 수정되지 않는 이상), hashCode는 여러 번 호출해도 그 결과가 항상 같아야 한다.
-
equals 메서드의 실행 결과로 두 객체가 같다고 나온다면, hashCode 메서드의 호출 결과도 같다고 나와야 한다.
hashCode는 equals와 같이 일관성 있는 동작을 해야 한다.
즉, 같은 요소는 반드시 같은 해시 코드를 가져야 한다는 의미고 그렇지 않으면 컬렉션 내부에 요소가 들어 있는지 제대로 확인하지 못하는 문제가 발생한다.
그래서 코틀린은 equals 구현을 오버라이드 할때 hashCode도 함께 오버라이드 하는 것을 추천한다.
또한 지켜야하는 요구사항이 있는데 hashCode는 최대한 요소를 넓게 퍼뜨려야 한다. 다른 요소라면 최대한 다른 해시 값을 갖게 하자.
왜냐하면 hashCode가 항상 같은 값을 리턴하면 해시 테이블을 사용할 필요가 없다.
또한 equals 메서드 실행회수도 더 많아진다.
hashCode 구현하기
일반적으로 data 한정자를 붙이면 코틀린이 적당한 equals와 hashCode를 정의해주므로 이를 직접 정의할 일이 없다.
다만 equals를 따로 정의했다면 반드시 hashCode도 함께 정의해주자!! (반대 상황도 마찬가지다)
관례적으로 모든 해시 코드의 값을 더하고 이전까지의 결과에 31을 곱한 뒤 더해준다.
data 한정자도 이렇게 구현된다.
해시코드를 따로 구현할 때 유용한 함수로는 코틀린/JVM의 Object.hashCode가 있다.
코틀린 stdlib에는 이런 함수가 따로 없어서 구현해서 사용해야 한다.
override fun hashCode(): Int = hashCodeOf(timeZone, millis)
inline fun hashCodeOf(vararg values: Any?) = values.fold(0) { acc, value ->
(acc * 31) + value.hashCode()
}다시 당부하지만 hashCode를 구현할 때 가장 중요한 규칙은 언제나 equals와 일관된 결과가 나와야 한다이다.
같은 객체라면 언제나 같은 값을 리턴하게 만들어 주자.
