[Java] JDK 부수기 - (1) java.lang.Object - 3. hashCode

 

---

3. hashCode()

해당 객체의 해시 코드 값을 리턴한다.

 

JVM 뜯어보기

 

 Object.hashCode() 메서드는 해당 객체의 해시 코드 값을 리턴하는 메서드다. 해시 코드를 생성하는 해시 함수가 자바에서 어떻게 구현되어 있는지 궁금해진다.

 

// src/java.base/java/lang/Object.java

public class Object {

    @IntrinsicCandidate
    public native int hashCode();
        
}

 

 역시 Object의 hashCode() 메서드도 네이티브 메서드로 구현되어 있다. JVM에서 해당 구현 코드를 찾아보자.

 

// src/hotspot/share/prims/jvm.cpp

JVM_ENTRY(jint, JVM_IHashCode(JNIEnv* env, jobject handle))
  // as implemented in the classic virtual machine; return 0 if object is null
  return handle == nullptr ? 0 :
         checked_cast<jint>(ObjectSynchronizer::FastHashCode (THREAD, JNIHandles::resolve_non_null(handle)));
JVM_END

 

 해당 부분은 JVM_IHashCode로 구현되어 있다. 자바 객체를 handle 파라미터로 받은 뒤 비어있다면(null) 해시 코드로 0을 리턴하고, 아니라면 FashHashCode 함수로 다시 값을 넘겨주어 해시 코드를 생성하고 자바 int타입인 jint로 다시 리턴해주는 코드다. 그럼 다시 FastHashCode함수를 살펴보자.

 

// src/hotspot/share/runtime/synchronizer.cpp

intptr_t ObjectSynchronizer::FastHashCode(Thread* current, oop obj) {

  while (true) {
    ObjectMonitor* monitor = nullptr;
    markWord temp, test;
    intptr_t hash;
    markWord mark = read_stable_mark(obj);
    if (VerifyHeavyMonitors) {
      assert(LockingMode == LM_MONITOR, "+VerifyHeavyMonitors requires LockingMode == 0 (LM_MONITOR)");
      guarantee((obj->mark().value() & markWord::lock_mask_in_place) != markWord::locked_value, "must not be lightweight/stack-locked");
    }
    if (mark.is_neutral()) {               // if this is a normal header
      hash = mark.hash();
      if (hash != 0) {                     // if it has a hash, just return it
        return hash;
      }
      hash = get_next_hash(current, obj);  // get a new hash
      temp = mark.copy_set_hash(hash);     // merge the hash into header
                                           // try to install the hash
      test = obj->cas_set_mark(temp, mark);
      if (test == mark) {                  // if the hash was installed, return it
        return hash;
      }
      // Failed to install the hash. It could be that another thread
      // installed the hash just before our attempt or inflation has
      // occurred or... so we fall thru to inflate the monitor for
      // stability and then install the hash.
    } else if (mark.has_monitor()) {
      monitor = mark.monitor();
      temp = monitor->header();
      assert(temp.is_neutral(), "invariant: header=" INTPTR_FORMAT, temp.value());
      hash = temp.hash();
      if (hash != 0) {
        // It has a hash.

        // Separate load of dmw/header above from the loads in
        // is_being_async_deflated().

        // dmw/header and _contentions may get written by different threads.
        // Make sure to observe them in the same order when having several observers.
        OrderAccess::loadload_for_IRIW();

        if (monitor->is_being_async_deflated()) {
          // But we can't safely use the hash if we detect that async
          // deflation has occurred. So we attempt to restore the
          // header/dmw to the object's header so that we only retry
          // once if the deflater thread happens to be slow.
          monitor->install_displaced_markword_in_object(obj);
          continue;
        }
        return hash;
      }
      // Fall thru so we only have one place that installs the hash in
      // the ObjectMonitor.
    } else if (LockingMode == LM_LIGHTWEIGHT && mark.is_fast_locked() && is_lock_owned(current, obj)) {
      // This is a fast-lock owned by the calling thread so use the
      // markWord from the object.
      hash = mark.hash();
      if (hash != 0) {                  // if it has a hash, just return it
        return hash;
      }
    } else if (LockingMode == LM_LEGACY && mark.has_locker() && current->is_lock_owned((address)mark.locker())) {
      // This is a stack-lock owned by the calling thread so fetch the
      // displaced markWord from the BasicLock on the stack.
      temp = mark.displaced_mark_helper();
      assert(temp.is_neutral(), "invariant: header=" INTPTR_FORMAT, temp.value());
      hash = temp.hash();
      if (hash != 0) {                  // if it has a hash, just return it
        return hash;
      }
      // WARNING:
      // The displaced header in the BasicLock on a thread's stack
      // is strictly immutable. It CANNOT be changed in ANY cases.
      // So we have to inflate the stack-lock into an ObjectMonitor
      // even if the current thread owns the lock. The BasicLock on
      // a thread's stack can be asynchronously read by other threads
      // during an inflate() call so any change to that stack memory
      // may not propagate to other threads correctly.
    }

    // Inflate the monitor to set the hash.

    // An async deflation can race after the inflate() call and before we
    // can update the ObjectMonitor's header with the hash value below.
    monitor = inflate(current, obj, inflate_cause_hash_code);
    // Load ObjectMonitor's header/dmw field and see if it has a hash.
    mark = monitor->header();
    assert(mark.is_neutral(), "invariant: header=" INTPTR_FORMAT, mark.value());
    hash = mark.hash();
    if (hash == 0) {                       // if it does not have a hash
      hash = get_next_hash(current, obj);  // get a new hash
      temp = mark.copy_set_hash(hash)   ;  // merge the hash into header
      assert(temp.is_neutral(), "invariant: header=" INTPTR_FORMAT, temp.value());
      uintptr_t v = Atomic::cmpxchg((volatile uintptr_t*)monitor->header_addr(), mark.value(), temp.value());
      test = markWord(v);
      if (test != mark) {
        // The attempt to update the ObjectMonitor's header/dmw field
        // did not work. This can happen if another thread managed to
        // merge in the hash just before our cmpxchg().
        // If we add any new usages of the header/dmw field, this code
        // will need to be updated.
        hash = test.hash();
        assert(test.is_neutral(), "invariant: header=" INTPTR_FORMAT, test.value());
        assert(hash != 0, "should only have lost the race to a thread that set a non-zero hash");
      }
      if (monitor->is_being_async_deflated()) {
        // If we detect that async deflation has occurred, then we
        // attempt to restore the header/dmw to the object's header
        // so that we only retry once if the deflater thread happens
        // to be slow.
        monitor->install_displaced_markword_in_object(obj);
        continue;
      }
    }
    // We finally get the hash.
    return hash;
  }
}

 

 해시코드를 산출하는 FastHashCode()함수는 다음과 같다. 전체적인 흐름을 보면 안정적인 결과를 산출하기 위해 while문으로 루프를 돌리고 그 안에서 if ~ else - if문을 반복해 경우의 수에 따라 해시코드를 다르게 처리한다. 해시코드를 산출하려는 객체의 상태가 잠겨있거나 다른 스레드에 의해 사용중일 수도 있으므로 이 부분을 반복적으로 체크해 올바른 결과를 내기 위해 while문을 사용한 것으로 보인다. 경우의 수 중 객체가 neutral한 일반적인 경우를 살펴보자.

 

if (mark.is_neutral()) {               // if this is a normal header
      hash = mark.hash();
      if (hash != 0) {                     // if it has a hash, just return it
        return hash;
      }
      hash = get_next_hash(current, obj);  // get a new hash
      temp = mark.copy_set_hash(hash);     // merge the hash into header
                                           // try to install the hash
      test = obj->cas_set_mark(temp, mark);
      if (test == mark) {                  // if the hash was installed, return it
        return hash;
      }
      // Failed to install the hash. It could be that another thread
      // installed the hash just before our attempt or inflation has
      // occurred or... so we fall thru to inflate the monitor for
      // stability and then install the hash.
}

 

 mark는 각각의 자바 객체가 가지고 있는 markWord필드다. markWord는 객체의 해시 코드나 lock 여부, GC 관련된 데이터와 같은 메타 데이터를 담고 있다. 따라서 위 코드의 if문에서 해당 객체가 neutral한 상태라면 코드 블록 안의 코드가 실행된다. mark.hash()로 해당 객체의 해시코드를 계산하고 만약 이미 해시코드가 존재한다면 존재하는 해시코드를 리턴한다. 그렇지 않다면 get_next_hash() 함수로 새로운 해시코드를 계산한다. 그 아래의 나머지 코드들은 산출된 해시코드를 다시 해당 객체의 markWord에 설정하고 제대로 설정되었는지 검증하는 절차다.

 

 그럼 다시 get_next_hash() 함수가 어떻게 구현되어 있는지 확인해보자.

 

// src/hotspot/share/runtime/synchronizer.cpp

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;
}

 

 드디어 실제로 해시코드를 산출하는 구현 코드다. 코드에 따르면 해시코드가 생성되는 방식을 결정하는 hashCode 값에 따라 해시코드가 다른 방식으로 생성되는 것을 알 수 있다. hashCode가 0이라면, OS로 난수를 생성해 그대로 해시값으로 사용한다. hashCode가 1이라면, 객체의 메모리 주소를 기반으로 한 안정적(stable)인 해시 알고리즘을 사용해 해시값으로 사용한다. hashCode가 2라면, 해시코드가 프로그램에 어떤 영향을 미치는지 확인하기 위한 안정성 테스트를 위해 해시값을 1로 고정한다. hashCode가 3이라면, 전역 시퀀스를 사용해 순차적으로 증가(++)하는 해시값을 사용한다. hashCode가 4라면, 객체의 메모리 주소 자체를 해시값으로 사용한다. hashCode가 그 이상일 경우에는 Geroge Marsaglia가 발명한 Xorshift 스킴을 이용해 해시값을 산출한다. Xorshift는 반복적인 비트 연산으로 빠르게 품질이 좋은 난수를 발생시키는 알고리즘이다. 주석에 설명된 것처럼 Xorshift가 자바의 해시코드 생성의 기본 알고리즘인 것을 알 수 있다. 실제로 내 JVM 환경의 hashCode가 설정된 부분을 봐도 5로 설정되어 있다.

 

// src/hotspot/share/runtime/globals.hpp

#define RUNTIME_FLAGS(develop,                                              \
                      develop_pd,                                           \
                      product,                                              \
                      product_pd,                                           \
                      notproduct,                                           \
                      range,                                                \
                      constraint)                                           \

  product(intx, hashCode, 5, EXPERIMENTAL,                                  \
               "(Unstable) select hashCode generation algorithm")           \

 

 이렇게 되면 새롭게 알 수 있는 사실이 있다. 일반적으로 객체의 해시코드는 객체가 저장된 메모리 주소를 기반으로 생성되는 줄 알았는데, 내 JVM에서는 xor-shift를 이용해 생성된 난수가 객체의 해시코드가 되므로 자바의 해시코드는 메모리 주소랑 전혀 상관이 없었다.

 

오?

 

사용해보기

 

public class Person {
    int id;

    public Person(int id) {
        this.id = id;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;

        if (obj instanceof Person obj2)
            return this.id == obj2.id;

        return false;
    }

    @Override
    public int hashCode() {
        return super.hashCode();
    }
}

public class Main {
    public static void main(String[] args) {
        Person person_1 = new Person(988515);
        Person person_2 = new Person(988515);

        System.out.println(person_1 == person_2);
        System.out.println(person_1.equals(person_2));
        
        System.out.println(person_1.hashCode());
        System.out.println(person_2.hashCode());
    }
}

false
true
379110473
99550389

 

 equals() 메서드 관련해 앞에서 쓴 글에도 언급했던 것처럼 equals() 메서드로 두 객체가 동일하다면 해시코드도 같아야 한다는 규칙이 있다. 현재는 Object 클래스의 hashCode() 메서드를 그대로 오버라이딩했기 때문에 두 객체는 equals() 메서드를 통한 결과로 true를 출력했음에도 불구하고 서로 다른 해시코드를 가지고 있다. 이것은 올바르지 않기 때문에 적당히 hashCode() 메서드를 수정해보자.

 

 

public class Person {
    int id;

    public Person(int id) {
        this.id = id;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;

        if (obj instanceof Person obj2)
            return this.id == obj2.id;

        return false;
    }

    @Override
    public int hashCode() {
        return this.id ;
    }
}

false
true
988515
988515

 

 더 좋은 알고리즘도 있겠지만 equals() 메서드가 Person 객체의 id값을 기준으로 판단하므로 해시코드로 id값 자체를 사용했다. 어차피 id는 int범위 안에 있는 유일한 값이며 특별히 암호화할 필요가 없다고 생각했다. 만약 암호화가 필요한 민감한 값이라면 암호화 알고리즘을 이용해 해당 id값을 한번 감싸주면 될 것 같다.