hashCode
hashCode는 객체를 빠르게 분류하기 위한 정수값이다.
자바의 모든 객체는 Object 클래스를 상속받으므로 hashCode() 메서드를 가지고 있다.
hashCode는 HashMap, HashSet 등 해시 기반 자료구조의 성능을 위해 존재한다.
hashCode를 사용하면 평균적으로 O(1)에 가까운 탐색이 가능하다.
String의 hashCode
String은 31 * h + char 공식으로 hashCode를 계산한다.
"Java"의 hashCode 계산:
J(74) → h = 74
a(97) → h = 31 × 74 + 97 = 2,391
v(118) → h = 31 × 2,391 + 118 = 74,239
a(97) → h = 31 × 74,239 + 97 = 2,301,506
->"Java".hashCode() = 2,301,506
31을 곱하는 이유
31은 소수이면서 비트 연산으로 최적화 가능한 숫자다.
"충돌을 줄이는 수학적 특성(소수)", "빠른 계산(비트 최적화)", "안정적인 동작(적당한 크기)"을 모두 만족하는 숫자가 31이다.
equals와의 관계
equals를 재정의하면 hashCode도 반드시 재정의해야 한다.
계약 3원칙:
- 일관성: 같은 객체는 항상 같은 hashCode 반환
- equals true → hashCode 같음 (필수)
- hashCode 같음 → equals는 true/false 가능 (충돌 허용)
Person p1 = new Person("sejin", 19);
Person p2 = new Person("sejin", 19);
// equals만 재정의한 경우
p1.equals(p2); // true (내용 같음)
map.put(p1, "데이터");
map.get(p2); // null (hashCode가 달라서 못 찾음)
// 올바른 경우
@Override equals() { ... }
@Override hashCode() { return Objects.hash(name, age); }
-> 정상 동작해시 충돌
서로 다른 객체가 같은 hashCode를 가질 수 있다.
hashCode는 int타입으로 42억개의 값으로 표현할 수 있는데 객체가 그것보다 많은면 겹칠 수 있다.
HashMap은 같은 hashCode를 가지면 같은 버킷에 저장한다.
이때 HashMap은 체이닝방식을 사용한다. 이미 버킷에 "a"가 있다면, "b"를 LinkedList처럼 "a" 뒤에 연결한다.
즉, 한 버킷에 여러 개의 노드가 체인처럼 이어지는 구조가 된다.
