[Java] hashCode() internal : String, Object

질문:  String 간 비교시 헸길리는 부분이있어서 질문 드립니다.

String a = "a";
String b = new String("a");
이와 같은 케이스는 주소가 다르게 생성되던데 이런 케이스 때문에 무조건 equals()메소드로 비교하는것인가요??
답변부탁드립니다.

---

질문에 대한 답부터 하면 "맞다."이다.

 

하지만 이 글을 쓰게 된 이유에는 '주소'라는 말이 있었기 때문이다.

혹시 주소가 hashCode() 돌려주는 값을 의미했는지 물어보니 그렇다고 한다.

String 클래스의 hashCode

(보통) String 클래스의 hashCode() 는 Object의 hashCode()를 사용하지 않고 오버라이딩해서 구현한다.

버전에 따라 구현 방법은 바뀌었지만

자바 8에서는

public final class String
    implements java.io.Serializable, Comparable<String>, CharSequence
{
    private final char value[];
    private int hash; // Default to 0

    public int hashCode() {
        int h = hash;
        if (h == 0 && count > 0) {
            int off = offset;
            char val[] = value;
            int len = count;

            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
        return h;
    }
    // ...
}

자바 11에서는 

public final class String
    implements java.io.Serializable, Comparable<String>, CharSequence {

    private final byte[] value;
    
    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            hash = h = isLatin1() ? StringLatin1.hashCode(value)
                                  : StringUTF16.hashCode(value);
        }
        return h;
    }

    static final boolean COMPACT_STRINGS;

    static {
        COMPACT_STRINGS = true;
    }
    
    private boolean isLatin1() {
        return COMPACT_STRINGS && coder == LATIN1;
    }

    @Native static final byte LATIN1 = 0;
    @Native static final byte UTF16  = 1;
    
    private final byte coder;
    // ...
}

final class StringLatin1 {
    public static int hashCode(byte[] value) {
        int h = 0;
        for (byte v : value) {
            h = 31 * h + (v & 0xff);
        }
        return h;
    }
    //...
}

final class StringUTF16 {
    public static int hashCode(byte[] value) {
        int h = 0;
        int length = value.length >> 1;
        for (int i = 0; i < length; i++) {
            h = 31 * h + getChar(value, i);
        }
        return h;
    }
    
    @HotSpotIntrinsicCandidate
    static char getChar(byte[] val, int index) {
        index <<= 1;
        return (char)(((val[index++] & 0xff) << HI_BYTE_SHIFT) |
                      ((val[index]   & 0xff) << LO_BYTE_SHIFT));
    }
    //...
}

와 같이 구현되었다. JEP 254스펙인 Compact String이 자바9에 추가되면서 해시값을 구하는 로직이 두 가지로 분기가 되었다.

(JDK6때 compressed strings 추가가 되었다 사라진 것의 재현은 아니겠지...)

Object 클래스의 hashCode

Object 클래스의 hashCode()는 String과 달리 늘 일관성이 있었다.

바로 native 메서드였기 때문이다. (물론 JVM 내부 구현은 달라졌으리라 추측해본다.)

public class Object {

    @HotSpotIntrinsicCandidate
    public native int hashCode();
    // ...
}

native 쪽을 살펴보기 위해 C 코드(Object.c)를 살펴보면 아래와 같이 매핑된 함수를 찾을 수 있다. (발췌)

static JNINativeMethod methods[] = {
    {"hashCode",    "()I",                    (void *)&JVM_IHashCode},
    {"wait",        "(J)V",                   (void *)&JVM_MonitorWait},
    {"notify",      "()V",                    (void *)&JVM_MonitorNotify},
    {"notifyAll",   "()V",                    (void *)&JVM_MonitorNotifyAll},
    {"clone",       "()Ljava/lang/Object;",   (void *)&JVM_Clone},
};

hashCode 는 JVM_IHashCode 로 매핑이된다.

JVM_IHashCode 는 jvm.h/cpp 에 정의 및 구현이 되어 있다.

jvm.h

JNIEXPORT jint JNICALL
JVM_IHashCode(JNIEnv *env, jobject obj);

jvm.cpp

JVM_ENTRY(jint, JVM_IHashCode(JNIEnv* env, jobject handle))
  JVMWrapper("JVM_IHashCode");
  return handle == NULL ? 0 : ObjectSynchronizer::FastHashCode (THREAD, JNIHandles::resolve_non_null(handle)) ;
JVM_END

ObjectSynchronizer 클래스의 FastHashCode 메서드를 호출하는 것을 알 수 있다.

FastHashCode 는 내부적으로 get_next_hash 메서드를 호출한다.

ObjectSynchronizer.cpp - assert와 주석은 가독성을 떨어뜨려 제거하였다.

intptr_t ObjectSynchronizer::FastHashCode(Thread * Self, oop obj) {
  if (UseBiasedLocking) {
    if (obj->mark()->has_bias_pattern()) {
      Handle hobj(Self, obj);
      BiasedLocking::revoke_and_rebias(hobj, false, JavaThread::current());
      obj = hobj();
    }
  }

  ObjectMonitor* monitor = NULL;
  markOop temp, test;
  intptr_t hash;
  markOop mark = ReadStableMark(obj);

  if (mark->is_neutral()) {
    hash = mark->hash();
    if (hash) {
      return hash;
    }
    hash = get_next_hash(Self, obj);
    temp = mark->copy_set_hash(hash);
    test = obj->cas_set_mark(temp, mark);
    if (test == mark) {
      return hash;
    }
  } else if (mark->has_monitor()) {
    monitor = mark->monitor();
    temp = monitor->header();
    hash = temp->hash();
    if (hash) {
      return hash;
    }
  } else if (Self->is_lock_owned((address)mark->locker())) {
    temp = mark->displaced_mark_helper();
    hash = temp->hash();
    if (hash) {
      return hash;
    }
  }

  monitor = ObjectSynchronizer::inflate(Self, obj, inflate_cause_hash_code);
  mark = monitor->header();
  hash = mark->hash();
  if (hash == 0) {
    hash = get_next_hash(Self, obj);
    temp = mark->copy_set_hash(hash);
    test = Atomic::cmpxchg(temp, monitor->header_addr(), mark);
    if (test != mark) {
      hash = test->hash();
    }
  }
  return hash;
}

// hashCode() generation :
//
// Possibilities:
// * MD5Digest of {obj,stwRandom}
// * CRC32 of {obj,stwRandom} 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.stwRandom ;
// * A variation of Marsaglia's shift-xor RNG scheme.
// * (obj ^ stwRandom) 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 * Self, 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 addrBits = cast_from_oop<intptr_t>(obj) >> 3;
    value = addrBits ^ (addrBits >> 5) ^ GVars.stwRandom;
  } else if (hashCode == 2) {
    value = 1;            // for sensitivity testing
  } else if (hashCode == 3) {
    value = ++GVars.hcSequence;
  } 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 = Self->_hashStateX;
    t ^= (t << 11);
    Self->_hashStateX = Self->_hashStateY;
    Self->_hashStateY = Self->_hashStateZ;
    Self->_hashStateZ = Self->_hashStateW;
    unsigned v = Self->_hashStateW;
    v = (v ^ (v >> 19)) ^ (t ^ (t >> 8));
    Self->_hashStateW = v;
    value = v;
  }

  value &= markOopDesc::hash_mask;
  if (value == 0) value = 0xBAD;
  TEVENT(hashCode: GENERATE);
  return value;
}

get_next_hash라는 메서드의 알고리즘은 주어진 전역변수 hashCode가 설정된 값에 따라 여러가지 알고리즘으로 분기한다.

0. 운영체제에 구현된 random(Park-Miller RNG)을 사용
1. 객체의 메모리 주소 int로 캐스팅 한 값을 우로 3 쉬프트 한 값을 사용
2. 고정된 값 1을 반환 (테스팅 목적)
3. 연속된 시퀀스를 반환
4. 객체의 메모리 주소를 그냥 int로 캐스팅함
5. XOR 쉬프트를 통한 스레드 상태를 기반으로 생성

그러면 hashCode는 어떤 값에 의해 선택될까?

globals.hpp에 따르면 OpenJDK 8의 경우 5번이 선정된다.

#define RUNTIME_FLAGS(develop, develop_pd, product, product_pd, diagnostic, experimental, notproduct, manageable, product_rw, lp64_product) \
// ..
  develop(bool, InlineObjectHash, true,                                     \
          "Inline Object::hashCode() native that is known to be part "      \
          "of base library DLL")                                            \
  product(intx, hashCode, 5,                                                \
          "(Unstable) select hashCode generation algorithm")                \

그런데 JDK 6, 7에서는 0번의 전략을 선택했다. (src/share/vm/runtime/globals.hpp)

  develop(bool, InlineObjectHash, true,                                     \
          "inline Object::hashCode() native that is known to be part "      \
          "of base library DLL")                                            \
  product(intx, hashCode, 0,                                                \
         "(Unstable) select hashCode generation algorithm" )                \

VMOption 값의 확인방법

macOS, Linux

java -XX:+PrintFlagsFinal -version 2>&1 | grep 'hash'

Windows

java -XX:+PrintFlagsFinal -version 2>&1 | findstr "hash"

 

os:random은 정적 멤버함수로 선언 및 구현이 되어 있다.

os.hpp L.814

class os: AllStatic {
  friend class VMStructs;
  // ..
  // random number generation
  static long random();                    // return 32bit pseudorandom number
  static void init_random(long initval);   // initialize random sequence

os.cpp on JDK 11

static int random_helper(unsigned int rand_seed) {
  /* standard, well-known linear congruential random generator with
   * next_rand = (16807*seed) mod (2**31-1)
   * see
   * (1) "Random Number Generators: Good Ones Are Hard to Find",
   *      S.K. Park and K.W. Miller, Communications of the ACM 31:10 (Oct 1988),
   * (2) "Two Fast Implementations of the 'Minimal Standard' Random
   *     Number Generator", David G. Carta, Comm. ACM 33, 1 (Jan 1990), pp. 87-88.
  */
  const unsigned int a = 16807;
  const unsigned int m = 2147483647;
  const int q = m / a;        assert(q == 127773, "weird math");
  const int r = m % a;        assert(r == 2836, "weird math");

  // compute az=2^31p+q
  unsigned int lo = a * (rand_seed & 0xFFFF);
  unsigned int hi = a * (rand_seed >> 16);
  lo += (hi & 0x7FFF) << 16;

  // if q overflowed, ignore the overflow and increment q
  if (lo > m) {
    lo &= m;
    ++lo;
  }
  lo += hi >> 15;

  // if (p+q) overflowed, ignore the overflow and increment (p+q)
  if (lo > m) {
    lo &= m;
    ++lo;
  }
  return lo;
}

int os::random() {
  // Make updating the random seed thread safe.
  while (true) {
    unsigned int seed = _rand_seed;
    unsigned int rand = random_helper(seed);
    if (Atomic::cmpxchg(rand, &_rand_seed, seed) == seed) {
      return static_cast<int>(rand);
    }
  }
}

JDK 8.0 (알고리즘은 동일하다)

long os::random() {
  /* standard, well-known linear congruential random generator with
   * next_rand = (16807*seed) mod (2**31-1)
   * see
   * (1) "Random Number Generators: Good Ones Are Hard to Find",
   *      S.K. Park and K.W. Miller, Communications of the ACM 31:10 (Oct 1988),
   * (2) "Two Fast Implementations of the 'Minimal Standard' Random
   *     Number Generator", David G. Carta, Comm. ACM 33, 1 (Jan 1990), pp. 87-88.
  */
  const long a = 16807;
  const unsigned long m = 2147483647;
  const long q = m / a;        assert(q == 127773, "weird math");
  const long r = m % a;        assert(r == 2836, "weird math");

  // compute az=2^31p+q
  unsigned long lo = a * (long)(_rand_seed & 0xFFFF);
  unsigned long hi = a * (long)((unsigned long)_rand_seed >> 16);
  lo += (hi & 0x7FFF) << 16;

  // if q overflowed, ignore the overflow and increment q
  if (lo > m) {
    lo &= m;
    ++lo;
  }
  lo += hi >> 15;

  // if (p+q) overflowed, ignore the overflow and increment (p+q)
  if (lo > m) {
    lo &= m;
    ++lo;
  }
  return (_rand_seed = lo);
}

 

참고로 이 값은 JVM 시작할 때 옵션으로 조정이 가능하다.

1값으로만 반환하는 2번 전략을 사용하고 싶으면 아래와 같은 옵션을 붙이면 된다.

-XX:hashCode=2

IntelliJ IDEA에서는 VM options에 넣어주면 된다.

-XX:hashCode=2

더 자세한 내용은 Galo Navarro 의 How does the default hashCode() work? 에 더 잘 설명되어 있으니 관심있는 사람은 방문해보는 것이 좋을 것 같다.