Object 클래스의 hashCode() native code 밑바닥까지 파헤치기

 결론부터 말하자면, OpenJDK 기준 Java 8 이후 부터는 hash값을 생성할 때, 객체의 메모리 주소는 활용하지 않으며, 쓰레드의 상태값을 활용하여 해시값을 생성합니다. 다른 JVM 구현체는 다를 수도 있습니다.

 

---

 

 

 

hashCode() 메서드에 대해서 알아보기 전에, 이 글을 포스팅하게 된 이유를 말하고자 한다.

 

( 참고로, 이 포스팅은, Java 11 공식문서 와 openjdk github source 를 기준으로 확인한 것입니다. )

 

 equals() 메서드에 의해 동일하다고 취급되는 객체가, HashTable 계열의 자료구조에서 사용될 때, 동일한 KEY로서 인식되기 위해, equals() 메서드를 오버라이딩하면, 반드시 hashCode() 메서드도 오버라이딩해줘야한다.왜냐하면, Hash~ 자료구조에서 Key를 비교할 때, (1) hashCode() 비교 -> (2) equals() 비교 를 수행하여 비교하기 때문이다.

 

아래의 내용은 Java 11 공식문서에 정의된 내용이다.

 

 위 내용은 하도 많이 봐서, 머리에 박힌 내용인데, 정작 자바에서 'hashCode() 메서드는 어떠한 로직을 수행하는지' 를 정확히 알지 못해 답답해서 이 글을 통해 정리하고자 한다.

 

 

Object 클래스의 hashCode() 소스코드(C++ native)

 

시작하자 마자, 문제에 봉착했다... hashCode() 메서드는 native 메서드 라서, 내부 소스코드를 볼 수 없다...

 그러나, 스택오버플로우의 힘을 빌려, 해시값을 생성하는 메서드가 무엇인지 알아냈다. 아래 소스코드는 C++로 작성된 것이다. 소스코드 분석은 '주석 번역' -> 'line by line 해석' 순서로 진행한다. 하나하나씩 끝까지 파헤쳐보자.

 

// hashCode() generation :
//
// Possibilities:
// * MD5Digest of {obj,stw_random}
// * CRC32 of {obj,stw_random} or any linear-feedback shift register function.
// * A DES- or AES-style SBox[] mechanism
// * One of the Phi-based schemes, such as:
//   2654435761 = 2^32 * Phi (golden ratio)
//   HashCodeValue = ((uintptr_t(obj) >> 3) * 2654435761) ^ GVars.stw_random ;
// * A variation of Marsaglia's shift-xor RNG scheme.
// * (obj ^ stw_random) is appealing, but can result
//   in undesirable regularity in the hashCode values of adjacent objects
//   (objects allocated back-to-back, in particular).  This could potentially
//   result in hashtable collisions and reduced hashtable efficiency.
//   There are simple ways to "diffuse" the middle address bits over the
//   generated hashCode values:

static inline intptr_t get_next_hash(Thread* current, oop obj) {
  intptr_t value = 0;
  if (hashCode == 0) {
    // This form uses global Park-Miller RNG.
    // On MP system we'll have lots of RW access to a global, so the
    // mechanism induces lots of coherency traffic.
    value = os::random();
  } else if (hashCode == 1) {
    // This variation has the property of being stable (idempotent)
    // between STW operations.  This can be useful in some of the 1-0
    // synchronization schemes.
    intptr_t addr_bits = cast_from_oop<intptr_t>(obj) >> 3;
    value = addr_bits ^ (addr_bits >> 5) ^ GVars.stw_random;
  } else if (hashCode == 2) {
    value = 1;            // for sensitivity testing
  } else if (hashCode == 3) {
    value = ++GVars.hc_sequence;
  } else if (hashCode == 4) {
    value = cast_from_oop<intptr_t>(obj);
  } else {
    // Marsaglia's xor-shift scheme with thread-specific state
    // This is probably the best overall implementation -- we'll
    // likely make this the default in future releases.
    unsigned t = current->_hashStateX;
    t ^= (t << 11);
    current->_hashStateX = current->_hashStateY;
    current->_hashStateY = current->_hashStateZ;
    current->_hashStateZ = current->_hashStateW;
    unsigned v = current->_hashStateW;
    v = (v ^ (v >> 19)) ^ (t ^ (t >> 8));
    current->_hashStateW = v;
    value = v;
  }

  value &= markWord::hash_mask;
  if (value == 0) value = 0xBAD;
  assert(value != markWord::no_hash, "invariant");
  return value;
}

 

 

 

OpenJDK , hashCode 생성과 관련된 주석 번역

 

해시값을 생성하는데 사용가능한 알고리즘은 총 6개이다.

('obj'는 객체의 주소, 'stwRandom'은 OS가 생성해주는 랜덤값을 의미한다)

• MD5(515) : 객체의 주소와 OS가 생성한 랜덤한 값을 조합하여 MD5(128비트 암호화 해시 함수)로 요약
• CRC32(516) : 객체 주소와 OS가 생성한 랜덤 값의 조합에 체크섬 적용, 또는 LSFR 방식(특정 로직을 수행하여 레지스터 가장 앞단에 도출된 값을 추가하는 방식)
• DES or AES(517) : 대칭키 암호방식
• Phi-based schemes(518 ~ 520) : (수학을 잘몰라서 이부분은 모르겠다...)
• Marsaglia's shift-xor RNG scheme(521) : (유명한 난수 생성기 알고리즘인 듯 하다.,,)
• 객체 주소와 랜덤한 값을 XOR(522 ~ 527) : 매력적인 방법이지만, 해시 테이블에서의 해시 충돌을 야기할 수도 있다. 해시코드 값의 중간 주소 비트를 분산시키는 방법으로 간단하게 해결할 수 있다.

위와 같이 6개의 알고리즘을 사용하여 해시값을 생성하는데, 위의 알고리즘들을 사실 어려워서 잘 모르겠다. 다만, 중요한 것은 hashCode를 생성하는 native 코드에서 객체의 메모리 주소와 난수를 사용하여 해시값을 생성한다는 것이다.

 

 

get_next_hash C++ 함수 분석

결론부터 말하자면, ' Marsaglia's shift-xor RNG scheme' 이 방법이 사용된다. Java 8 부터는 기본적으로 아래 이미지 처럼, hashCode 값을 5로 지정하고 있다. 따라서, get_next_hash 코드 함수에서 마지막에 있는 알고리즘이 실행된다. 더 자세한 사항은 스택오버플로우 글을 참조하자.

 

 

 

결론

OpenJDK 8 이후부터, hashCode() 메서드는 'Thread의 상태'와 비트연산을 사용하여 해시값을 생성한다. 객체의 주소는 사용하지 않는다.

 

 

 

참고자료

OKKY - java.lang.Object.hashcode() 값은 실제 메모리 주소와 어떤 연관이 있나요?

 

Understanding how Java's Object.hashCode() can be related to memory address with native implementation

 

https://github.com/openjdk/jdk/blob/a474b37212da5edbd5868c9157aff90aae00ca50/src/hotspot/share/runtime/synchronizer.cpp#L992