들어가기 전에
Object의 hashCode() 메서드는 객체를 구별하는 정수 값을 반환한다. hashCode() 메서드에도 equals() 메서드와 같이 규약이 존재하는데 해당 내용은 다음과 같다.
1. 자바 응용 프로그램이 실행되는 동안 동일한 객체에 대해 hashCode() 메서드가 두 번 이상 호출될 때 비교에 사용되는 정보가 수정되지 않는 이상 동일한 정수 값을 일관되게 반환해야 한다. 동일한 응용 프로그램이라고 할지라도 각각의 다른 실행에서 이 값은 다를 수 있다.
2. 두 객체에 대한 equals() 메서드 호출 결과가 true라면 hashCode() 메서드를 호출했을 때 동일한 정수 값이 반환되어야 한다.
3. 두 객체에 대한 equals() 메서드 호출 결과가 false라면 hashCode() 메서드를 호출했을 때 서로 다른 정수 값이 반환되어야 한다. 이렇게 서로 다른 두 객체에 대해 구별되는 정수 값을 생성해냄으로써 해시 테이블의 성능을 높이게 된다
Object.equals() 메서드에 대해 정리하면서 두 객체의 내부 값을 비교해서 논리적 동치성을 확인하고자 equals() 메서드를 재정의할 때 hashCode() 메서드를 같이 재정의해야 한다는 이야기를 했었다. 그 이유는 위의 hashCode() 규약에서 확인할 수 있다. equals() 메서드를 통해 비교했을 때 true인 두 객체는 hashCode()에서도 동일한 정수 값을 반환해야 같은 객체임을 나타낼 수 있기 때문이다.
Object.hashCode()
hashCode()의 내부 구현을 보면 처음 보는 어노테이션이 있고 native method로 구현되어있는 것을 알 수 있다.
@HotSpotIntrinsicCandidate
public native int hashCode();@HotSpotIntrinsicCandidate 어노테이션은 해당 메서드의 성능을 향상시키기 위해서 HotSpot VM(Virtual Machine)에 의해 JVM이 내부적으로 효율적인 구현 방법을 찾아서 활용할 수도 있다는 의미로 사용된다. hashCode() 메서드가 native method로 만들어진 이유 또한 자바 코드보다는 C나 C++과 같이 다른 언어로 작성된 해시 알고리즘을 활용해서 성능을 높이기 위해서이다.
Hashing
결국 hashCode()가 하는 일은 해싱 알고리즘을 이용해서 객체를 구분할 수 있는 정수 값을 반환한다는 것인데 이 동작은 어떻게 이루어지는 것일까? 참고로 자바에서 사용하는 성능이 높은 알고리즘에는 정수 값을 저장할 때 HashMap이나 HashSet과 같은 컬렉션 구현체들이 사용된다.
해싱으로 고유한 정수 값을 생성할 때 분포도를 좋게 하기 위해서는 최대한 중복되지 않는 값을 산출해내야 한다.
// 출처 : baeldung.com/java-hashcode
@Override
public int hashCode() {
int result = (int) (id ^ (id >>> 32));
result = 31 * result + name.hashCode();
result = 31 * result + email.hashCode();
return result;
}일반적으로 IDE의 도움을 받거나 Object.hashCode()를 재정의한 메서드들의 구현 코드들을 보면 "31"이라는 숫자를 사용하는 것을 알 수 있다. 31은 어떻게 선택된 숫자일까? 이펙티브 자바를 통해 알아본 이유는 다음과 같다.
31이 선택된 이유
1. 31은 소수이면서 홀수이기 때문이다.
2. 만약 짝수를 사용할 때 오버플로우가 발생한다면 정보를 잃게 된다. 2를 곱하는 것은 시프트 연산과 같은 결과를 내기 때문이다.
3. 소수를 곱하는 이유는 명확하지 않으며 관례와 같다.
4. 결과적으로 31을 이용하면, 이 곱셈을 시프트 연산과 뺄셈으로 대체해 최적화할 수 있다.
(31 * i는 i << 5 - i와 같다.)
출처 : <Effective Java> Chapter 3, Item 9: Always override hashcode when you override equals
그리고 스택 오버 플로우에서 이와 관련된 여러 의견들을 보다가 조슈아 J. 블로치가 java.lang.String.hashCode 명세의 해시 알고리즘의 문제를 거론하면서 여러 가지 숫자로 해시 함수의 성능을 테스트한 글을 발견했다. 참고로 조슈아 J. 블로치는 자바 플랫폼의 설계와 구현을 주도한 개발자이면서 이펙티브 자바의 저자이다.
Of the remaining four, I'd probably select P(31), as it's the cheapest to calculate on a RISC machine (because 31 is the difference of two powers of two). P(33) is similarly cheap to calculate, but it's performance is marginally worse, and 33 is composite, which makes me a bit nervous.
- Josh
출처 : https://bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622
마지막에 남은 4개의 숫자 중 성능적인 면에서 31과 33이 크게 다르지 않았지만 33은 합성수이기 때문에 좀 더 확실한 31을 선택했다는 내용이다. 위의 글을 보면 알 수 있듯이 결국에는 조금 꺼림칙하다는 이유로 하나의 숫자를 선택한 것이다. 그렇다면 다른 라이브러리들은 어떤 숫자를 사용할까?
우리가 hashCode() 메서드 구현을 Apache Commons Lang's HashCodeBuilder class를 통해 하게 된다면 사용하는 숫자는 17과 37이다.
// 출처 : https://commons.apache.org/proper/commons-lang/apidocs/org/apache/commons/lang3/builder/HashCodeBuilder.html
public class Person {
String name;
int age;
public int hashCode() {
return new HashCodeBuilder(17, 37).
append(name).
append(age).
toHashCode();
}
}
Lombok의 hashCode() 구현에는 59가 사용된다.
// 출처 : https://projectlombok.org/features/EqualsAndHashCode
@Override public int hashCode() {
final int PRIME = 59;
int result = 1;
final long temp1 = Double.doubleToLongBits(this.score);
result = (result*PRIME) + (this.name == null ? 43 : this.name.hashCode());
result = (result*PRIME) + (int)(temp1 ^ (temp1 >>> 32));
result = (result*PRIME) + Arrays.deepHashCode(this.tags);
return result;
}
결과적으로 모두 소수이자 홀수를 사용하는 것은 똑같다. 31이라는 숫자에 의미를 두기 보다는 2의 배수를 사용하지 않고 소수이자 홀수를 사용함으로써 해시코드 값의 분포도를 좋게 하는 것이 중요하다는 것을 알면 되겠다.
하지만 이 숫자들을 사용하는 것만으로 모든 해시코드 값을 중복되지 않게 만들 수 있는 것인가? 그것은 아니다. 해시코드 값은 고정된 길이의 정수 값이기 때문이다. 예를 들어, 비둘기가 5마리일 때 비둘기 집이 4개라면 아무리 비둘기에게 집을 잘 분배하려고 노력하더라도 어쩔 수 없이 한 집에는 두 마리의 비둘기가 살 수밖에 없듯이 해시코드 값도 중복될 수밖에 없는 것이다. 이렇게 해시코드 값이 중복으로 발생하는 것을 해시 충돌이라고 한다.
Hash collision
해시 충돌이란 서로 다른 두 키가 똑같은 해시코드 값을 가지는 것이다. 먼저 해시 충돌을 해결하기 위한 전략들을 살펴보고 Java에서는 어떤 전략을 사용하는지 알아보겠다. 이 포스팅에서 다룰 전략은 세 가지로 다음과 같다.
- Separate chaining
- Open Addressing
- Linear probing
- Quadratic probing
- Double hashing
1. Separate chaining
Separate chaining 전략은 동일한 해시코드 값이 생성되었을 때 버킷에 링크드 리스트 형식으로 저장하는 방식이다.
위의 그림과 같이 각각의 버킷에 데이터가 저장되어있을 때 이미 값이 있는 1번 버킷과 아무것도 저장되어있지 않은 4번 버킷에 데이터가 저장되어야 한다면 어떻게 될까?
이미 값이 있는 1번 버킷은 해시 충돌이 발생하기 때문에 이미 존재하는 데이터에 새로운 데이터를 연결해서 저장하지만 값이 없다면 버킷 하나에만 값이 저장될 것이다. 그러니까 최초로 버킷에 저장되는 값들을 제외하고는 모두 링크드 리스트 형식으로 데이터가 저장되는 것이다.
그렇기 때문에 Separate chaining 전략은 구현이 비교적 간단하고 데이터를 얼마나 자주 삽입하거나 삭제할지 알 수 없을 때도 사용이 가능하다. 하지만 아래에서 확인할 수 있듯이 충돌이 많아질수록 O(n) 시간복잡도를 가지게 되고 사용하지 않는 공간들로 인해서 메모리가 낭비될 확률이 있다.
2. Open Addressing
Open Addressing 전략은 충돌이 발생했을 때 비어있는 공간에 데이터를 저장하는 방식이다. Separate chaining 전략처럼 링크드 리스트 형식을 사용하지 않기 때문에 반대로 키의 빈도나 수를 알고 있을 때 사용한다.
1) 선형 탐색 (Linear probing)
해시 충돌이 발생하면 해당 인덱스의 다음 인덱스부터 비어있는 인덱스를 발견할 때까지 한 칸씩 이동해서 찾으면 데이터를 저장한다. 하지만 이렇게 데이터를 저장하게 되면 특정 위치에 데이터가 모여있게 되고(primary clustering) 버킷이 많아질수록 탐색 시간이 길어진다.
2) 제곱 탐샘(Quadratic probing)
해시 충돌이 발생하면 해당 인덱스부터 충돌횟수 n의 제곱칸만큼 이동하면서 비어있는 인덱스를 찾아 데이터를 저장한다. 하지만 처음 인덱스 값이 같으면 이후의 계산되는 값이 동일하기 때문에 충돌이 반복해서 발생하는 문제점(secondary clustering)이 있다.
3) 이중 해시(Double hashing)
제곱 탐색에서 발생하는 secondary clustering을 방지하기 위해서 두 개의 해시함수를 사용한다. 첫 번째 해시함수는 최초의 해시코드 값을 얻는 것이고, 두 번째 해시함수는 해시 충돌이 일어났을 때 이동할 폭을 얻는 것이다.
자바는 이중에 어떤 방식을 사용해서 해시 충돌을 해결하는지 알아보자.
Hash collision in Java
Java의 HashMap은 해시 충돌을 해결하기 위해서 Separate chaining 전략을 사용한다. Java 8 이후부터는 버킷의 링크드 리스트 데이터 수가 특정 임계치를 초과하면 트리로 전환된다. 그래서 시간복잡도가 최악의 경우일 때 O(n)에서 O(log n)으로 성능을 향상시킬 수 있었다. 자세한 내용은 JPE 180: Handle Frequent HashMap Collision with Balanced Trees에서 확인할 수 있다. 참고로 이때 사용되는 트리는 Red-Black Tree이며 트리를 사용하기 위해 Entry 클래스 대신 Node 클래스를 사용한다.
실제로 HashMap 클래스의 구현부를 보면 아래와 같은 상수 값들을 확인할 수 있다. 각 주석의 내용을 보면 하나의 버킷에 8개의 데이터가 모이면 링크드 리스트를 트리로 변경하고 데이터가 삭제되어 개수가 6개가 된다면 다시 링크드 리스트로 변경하는 것을 알 수 있다.
// Bins are converted to trees
// when adding an element to a bin with at least this many nodes
static final int TREEIFY_THRESHOLD = 8;
// Should be less than TREEIFY_THRESHOLD,
// and at most 6 to mesh with shrinkage detection under removal.
static final int UNTREEIFY_THRESHOLD = 6;
그리고 이렇게 하나씩 데이터를 추가하다가 저장할 공간이 더 이상 존재하지 않을 때 크기를 확장한다.
Constructs an empty {@code HashMap} with the default initial capacity (16) and the default load factor (0.75).
HashMap의 기본 초기 용량은 16이고 Load factor는 0.75이다. Load factor는 map size의 몇 퍼센트를 차지하는지를 나타내는데 이 퍼센트가 크기를 동적으로 확장할지 말지를 결정짓는 척도가 된다. 그리고 초기 용량에 Load Factor 값을 곱한 개수를 초과하면 크기를 두 배로 늘린다.
말로 이해하기가 어려울 때는 아래의 계산 법을 보자.
16 (default initial capacity) X 0.75 (Load Factor) = 12
위의 계산 결과인 12개까지는 capacity를 16개로 유지하다가 13번째 데이터를 삽입할 때는 2⁴(16)에서 2⁵(32)로 버킷 개수를 늘린다. 참고로 이렇게 크기를 확장한 이후에는 기존의 데이터를 가져와서 저장하는데, 이때 삽입과 탐색의 시간복잡도를 O(1)로 유지하기 위해서 기존의 데이터들의 해시코드 값을 다시 해싱해서 삽입하는 것을 re-hashing이라고 한다.
하지만 이렇게 크기를 두 배로 확장하면 해시코드 값을 고르게 생성할 수가 없는데 이때 사용하는 것이 보조 해시 함수이다. Java 8 이후에는 이전과 달리 더 단순해진 보조 해시 함수를 사용한다. 이유는 Java HashMap은 어떻게 동작하는가?를 통해서 더 자세히 알 수 있다. 이 글에서는 Java 8 이전에는 어떤 방식으로 구현했는지에 대한 설명도 알 수 있지만 간략하게 이유만 알고 싶을 때는 아래를 참고하면 된다.
Java 8 HashMap 보조 해시 함수는 상위 16비트 값을 XOR 연산하는 매우 단순한 형태의 보조 해시 함수를 사용한다. 이유로는 두 가지가 있는데, 첫 번째는 Java 8에서는 해시 충돌이 많이 발생하면 링크드 리스트 대신 트리를 사용하므로 해시 충돌 시 발생할 수 있는 성능 문제가 완화되었기 때문이다. 두 번째로는 최근의 해시 함수는 균등 분포가 잘 되게 만들어지는 경향이 많아, Java 7까지 사용했던 보조 해시 함수의 효과가 크지 않기 때문이다. 두 번째 이유가 좀 더 결정적인 원인이 되어 Java 8에서는 보조 해시 함수의 구현을 바꾸었다.
출처: https://d2.naver.com/helloworld/831311
면접 예상 질문
- 해시 충돌이란 무엇인가요?
- 해시 충돌이 발생하는 이유는 무엇인가요?
- 해시 충돌이 일어날 때 해결할 수 있는 방법은 무엇인가요?
- 두 방법 중 하나를 선택하는 기준은 무엇인가요?
- Java에서 re-hashing을 사용하는 이유는 무엇인가요?
참고
'Java' 카테고리의 다른 글
| [Java] MessageFormat (0) | 2023.05.27 |
|---|---|
| [Java] Object.clone() (0) | 2023.03.04 |
| [Java] Object.equals() (0) | 2023.02.14 |
| [Java] Socket에 관하여 (0) | 2023.02.08 |
| [Java] 다중 상속이 가지는 문제 (0) | 2023.02.03 |
