[java] Hash

 

---

---

📌 Hash?

해시란 주어진 키를 숫자로 변환하는 값이다. 이 숫자는 HashMap 내부 배열의 인덱스를 결정하는데 사용된다.

 

간단한 해시함수의 예시이다.

 

예시에서는 나머지를 이용하여 해시 테이블에서 인덱스로 활용하고 있다. 하지만 이러한 해시 함수에서는 필연적으로 충돌이 발생 할 수 있다.

 

아래의 예시를 확인해보자 값2의 키값이 만약 22라면 해시함수를 지나면 2가 된다. 하지만 이미 값1이 해시함수를 지나 나온 해시 코드가 2임으로 충돌이 발생한다.

 

Java에서는 어떠한 알고리즘으로 해시 충돌을 피하고, 해시 함수를 정의 하는지 궁금하다. 알아보자

Java의 HashMap에서는 Object 클래스의 hashCode() 메서드를 사용해 키의 해시코드를 생성한다. 코드를 확인해 보자

 

Object의 해시코드

 

음.. 모르겠다. GPT에게 물어보자

 

• @IntrinsicCandidate 어노테이션:
  • 이 어노테이션은 JVM이 특정 메서드를 "핫스팟" 최적화나 JIT(Just-In-Time) 컴파일러가 인식할 수 있도록 하는 표시입니다. 즉, 이 메서드는 JVM이 성능 최적화를 위해 특별하게 취급하는 메서드 중 하나라는 뜻입니다.
  • 이 어노테이션을 통해 JVM은 hashCode() 메서드를 더 빠르게 실행할 수 있는 방법을 적용할 수 있습니다.
• native 키워드:
  • native 키워드는 이 메서드가 Java가 아닌 네이티브 코드로 구현되었다는 것을 의미합니다.
  • 즉, 이 메서드는 Java 언어로 직접 구현된 것이 아니라 JVM의 네이티브 코드에서 실행되며, 이는 Java와 외부 시스템 간의 상호작용을 가능하게 해줍니다.
  • 여기서 hashCode() 메서드는 JVM이 객체의 메모리 주소나 특정 메모리 상태를 기반으로 고유한 정수값을 반환하도록 구현된 것으로 추정됩니다. 이 값이 해시 테이블에서 객체를 고유하게 식별하는 데 사용됩니다.
• hashCode() 메서드:
  • 이 메서드는 Object 클래스의 기본 메서드로, 객체의 해시 코드를 반환합니다.
  • 객체의 해시 코드는 주로 HashMap, HashSet 등 해시 기반 자료구조에서 키로 사용되는 객체를 빠르게 찾기 위한 값입니다.
  • hashCode()는 Java에서 각 객체마다 고유한 해시 값을 생성하기 위한 메서드로, 기본적으로 객체의 메모리 주소를 기반으로 값을 생성합니다.

---

📌 Open JDK에서의 Hash에 관련된 것들

 

더 물어보니 정확한 native코드는 자바에서 확인이 불가능 하다고 한다. 그래서 openJdk에 자바 구현체에 가서 확이해보자

 

https://github.com/openjdk/jdk

 

구현파일은 해당 위치에 있다고 알아냈다.

openjdk/hotspot/src/share/vm/oops/oop.cpp

 

신기하게도 자바 jdk의 구현체인데도 cpp로 작성이 되어있다. 이것도 궁금한데 지금은 Hash에 집중하겠다.

 

hash코드를 생성하는 부분을 찾았다.

intptr_t oopDesc::slow_identity_hash() {
  // slow case; we have to acquire the micro lock in order to locate the header
  Thread* current = Thread::current();
  return ObjectSynchronizer::FastHashCode(current, this);
}

 

아래는 FashHashCode메서드이다. (jdk/src/hotspot/share/runtime/synchronizer.cpp)

intptr_t ObjectSynchronizer::FastHashCode(Thread* current, oop obj) {
  if (UseObjectMonitorTable) {
    // Since the monitor isn't in the object header, the hash can simply be
    // installed in the object header.
    return install_hash_code(current, 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_unlocked() || (LockingMode == LM_LIGHTWEIGHT && mark.is_fast_locked())) {
      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;
      }
      if (LockingMode == LM_LIGHTWEIGHT) {
        // CAS failed, retry
        continue;
      }
      // 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_LEGACY && mark.has_locker()
               && current->is_Java_thread()
               && JavaThread::cast(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.

    // There's no need to inflate if the mark has already got a monitor.
    // NOTE: an async deflation can race after we get the monitor and
    // before we can update the ObjectMonitor's header with the hash
    // value below.
    monitor = mark.has_monitor() ? mark.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(monitor->metadata_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() && !UseObjectMonitorTable) {
        // 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;
  }
}

 

뭐가 엄청 많다. 하나씩 차근차근 보자

 

반환 타입인 intptr_t는 정수 포인터 타입을 저장할 수 있는 정수형 자료형이다. 포인터와 같은 크기를 가지는 정수형 자료형이다.

 

1. 옵션에 따른 해시 생성

  if (UseObjectMonitorTable) {
    // Since the monitor isn't in the object header, the hash can simply be
    // installed in the object header.
    return install_hash_code(current, obj);
  }

UseObjectMonitorTable 플래그가 설정된 경우, 해시 코드가 객체 헤더에 저장되지 않고 모니터 테이블에 저장된다. 이 경우 install_hash_code를 호출해 해시 코드를 생성하고 바로 반환한다. 그렇지 않다면, 아래의 세부 로직을 따르게 됩니다.

 

2. 객체의 markWord 확인

markWord mark = read_stable_mark(obj);

객체의 markWord는 객체의 상태를 나타내는 필드로, 락 상태, 해시 코드, 모니터 포인터 등을 호함할 수 있습니다. 이 코드는 객체의 현재 상태를 읽어온다.

 

3. 객체가 락을 걸지 않은 경우

if (mark.is_unlocked() || (LockingMode == LM_LIGHTWEIGHT && mark.is_fast_locked())) {
    hash = mark.hash();
    if (hash != 0) {
        return hash;
    }

만약 객체가 unlock이거나 fast_locked이면 기존에 해시 코드가 있는지 확인한다.

해시 코드가 이미 있다면 -> 바로 반환

해시코드가 없다면 -> 새로운 해시 코드를 생성하는 get_next_hash함수를 호출하고, 객체의 markWord에 해시를 병합하려고 시도

 

4. CAS를 사용한 해시 설치

test = obj->cas_set_mark(temp, mark);
if (test == mark) {
    return hash;
}

CAS(Compare-And-Swap)를 사용하여 해시를 객체의 markWord에 설치한다. 성공하면 해시 코드를 반환하고, 실패하면 다시 시도한다(락 경쟁 상황 대비)

 

5. 모니터에 해시가 있는 경우

if (mark.has_monitor()) {
    monitor = mark.monitor();
    temp = monitor->header();
    hash = temp.hash();
    if (hash != 0) {
        return hash;
    }

객체가 모니터를 가지고 있는 경우, 모니터에서 해시 코들르 확인한다.

해시 코드가 이미 있으면 그 값을 반환한다.

없다면 새로운 해시를 설치하기 위해 모니터를 inflation한다.

 

6. Inflate (확장) 및 해시 설치

monitor = inflate(current, obj, inflate_cause_hash_code);

객체가 스택 락을 가지고 있는 경우에도, 안전하게 해시 코드를 설정하기 위해 모니터를 확장한다. 모니터가 없는 경우에도 모니터를 새로 만들어 객체에 연결한 후 해시를 설치한다.

---

📌 CPP로 작성된 해시를 만드는 함수

Open JDK 에서 해시를 직접 만드는 get_next_hash(Thread* current, oop obj) 함수를 보자! (이것도 역시 cpp이다)

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

 

해시를 만드는 방법은 if문으로 여러가지 방법을 사용 하는 것 같다 여기서 flag가 되는 hashCode를 찾아 보았지만, 이 hashCode는 JVM내부에서 환겯변수 처럼 설정 되어 있다고 해서 찾지 못하였다. 각 방법들을 살펴 보면서 충돌 가능성을 확인해 보자.

 

✏️ 그러면 Hash 충돌에 안전할까?

결론부터 말하자면 완벽히 Hash 충돌을 막는 것은 불가능 하다.

하지만 여러가지 설계를 통해 충돌을 최소화 하는 방식으로 해시를 생성한다. Java Open JDK 에서의 예시를 들어보면 여러가지 방법을 사용한다.

 

1. 랜덤값 생성 (hashCode == 0)

이 방법은 시스템의 랜덤 값 생성기를 사용하여 해시 값을 생성한다. 통상적으로 랜덤 값은 고유하고 충돌을 일으킬 확률이 매우 낮다. 그러나 충돌을 완전히 방지할 수는 없다.

 

2. 주소 기반 해시 (hashCode == 1)

객체의 주소를 해시 값으로 변환하는 방식이다. 객체 주소를 기반으로 해시를 만들면 주소가 동일한 객체는 동일한 해시 값을 가질 수 밖에 없습니다. 그러나 객체의 주소는 보통 고유하며, 주소 기반 해시는 충돌 확률을 낮추는 방식이다.

 

3. 고정 값 반환 (hashCode == 2)

디버깅용 고의 충돌

 

4. 순차 번호 (hashCode == 3)

이 방법은 전역 변수 hc_sequence를 증가시켜 해시 값을 생성한다. 해시 값이 순차적으로 증가하므로, 고유한 해시값을 얻을 수 있다. 다만, 순차적으로 증가하는 값이기 때문에 다양한 객체에 대해 해시값을 부포시키기 어려울 수 있다.

 

5. 객체 주소 그대로 사용 (hashCode == 4)

객체의 주소를 그대로 해시 값으로 사용하는 방법, 객체의 주소가 고유하므로 해시 값이 고유할 확률이 높습니다. 다만, 주소 충돌이 발생할 수 있기 때문에, 일반적으로 다른 방식과 결합하여 사용한다.

 

6. Marsaglia의 XOR-Shift 방식 (hashCode == 기타 경우)

XOR-Shift 알고리즘은 빠르고 효과적인 난수 생성기로 알려져 있다. 이 방법은 스레드의 상태를 기바능로 해시 값을 생성하는데, 스레드 마다 고유한 해시 상태를 유지하여 충돌을 최소화하려는 효과가 있다. 상태 기반 해시는 해시 값이 충돌하지 않도록 분산 효과를 얻을 수 있다. 

 

 

hashCode를 찾지 못했지만 제일 좋은 XOR-Shift방식을 사용하지 않을까 싶다.

찾았다 (jdk/src/hotspot/share/runtime/globals.hpp)

역시 5번 XOR-Shift방식을 사용한다.

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

 

 

---

📌 XOR-Shift

XOR-Shift가 얼마나 좋길래 어떤 알고리즘인지 궁금하다.

OpenJDK에서 구현된 XOR-Shift를 확인해보자

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;

 

요약

이 코드는 XOR-Shift 알고리즘을 사용하여 난수를 생성하는 과정입니다. 상태(state)는 current->_hashStateX, current->_hashStateY, current->_hashStateZ, current->_hashStateW 변수들로 관리되며, 각 상태는 시프트 연산과 XOR 연산을 통해 변경되고 결합됩니다. 이를 통해 새로운 난수가 생성되고, 그 결과는 후속 연산이나 반환값으로 사용됩니다.

• 시프트 연산(<<, >>)은 비트 단위로 데이터를 이동시키고, 이때 데이터가 왜곡되어 더 고른 분포를 가지게 됩니다.
• XOR 연산(^)은 두 값을 비교하여 다른 비트만 1로 설정하므로, 난수의 예측 불가능성을 높이고, 여러 비트를 조합하는 데 사용됩니다.

이 알고리즘은 빠르고 효율적으로 난수를 생성하며, 여러 번 반복하여 난수를 만들어낼 수 있습니다.

 

---

🤔 느낀점

우리가 흔히 사용하는 Hash에서 이렇게 많은 기술이 들어갔다는 것을 처음 알게 되었고, 다시한번 감사하면서 살아야겠다. 그리고 자바가 네이티브 영역으로 가면 cpp언어가 있는게 신기하였다.