24

Object.hashCode()の Javadoc には、次のように記載されています

合理的に実用的である限り、クラスで定義された hashCode メソッドはObject、個別のオブジェクトに対して個別の整数を返します。(これは通常、オブジェクトの内部アドレスを整数に変換することによって実装されますが、この実装手法は Java™ プログラミング言語では必要ありません。)

これはメモリアドレスと関係があるという一般的な誤解ですが、通知なしに変更される可能性があり、オブジェクトの hashCode() は変更されず、変更されてはならないため、そうではありません。

@Neet は良い答えへのリンクを提供しましたhttps://stackoverflow.com/a/565416/57695が、詳細を探しています。

これが私の懸念を説明する例です

Field theUnsafe = Unsafe.class.getDeclaredField("theUnsafe");
theUnsafe.setAccessible(true);
Unsafe unsafe = (Unsafe) theUnsafe.get(null);

for (int t = 0; t < 10; t++) {
    System.gc();
    Object[] objects = new Object[10];
    for (int i = 0; i < objects.length; i++)
        objects[i] = new Object();

    for (int i = 0; i < objects.length; i++) {
        if (i > 0) System.out.print(", ");
        int location = unsafe.getInt(objects, Unsafe.ARRAY_OBJECT_BASE_OFFSET + Unsafe.ARRAY_OBJECT_INDEX_SCALE * i);
        System.out.printf("%08x: hc= %08x", location, objects[i].hashCode());
    }
    System.out.println();
}

版画

eac00038: hc= 4f47e0ba, eac00048: hc= 2342d884, eac00058: hc= 7994d431, eac00068: hc= 19f71b53, eac00078: hc= 2e22f376, eac00088: hc= 789ddfa3, eac00098: hc= 44c58432, eac000a8: hc= 036a11e4, eac000b8: hc= 28bc917c, eac000c8: hc= 73f378c8
eac00038: hc= 30813486, eac00048: hc= 729f624a, eac00058: hc= 3dee2310, eac00068: hc= 5d400f33, eac00078: hc= 18a60d19, eac00088: hc= 3da5f0f3, eac00098: hc= 596e0123, eac000a8: hc= 450cceb3, eac000b8: hc= 4bd66d2f, eac000c8: hc= 6a9a4f8e
eac00038: hc= 711dc088, eac00048: hc= 584b5abc, eac00058: hc= 3b3219ed, eac00068: hc= 564434f7, eac00078: hc= 17f17060, eac00088: hc= 6c08bae7, eac00098: hc= 3126cb1a, eac000a8: hc= 69e0312b, eac000b8: hc= 7dbc345a, eac000c8: hc= 4f114133
eac00038: hc= 50c8c3b8, eac00048: hc= 2ca98e77, eac00058: hc= 2fc83d89, eac00068: hc= 034005e1, eac00078: hc= 6041f871, eac00088: hc= 0b1df416, eac00098: hc= 5b83d60d, eac000a8: hc= 2c5a1e6b, eac000b8: hc= 5083198c, eac000c8: hc= 4f025f9f
eac00038: hc= 00c5eb8a, eac00048: hc= 41eab16b, eac00058: hc= 1726099c, eac00068: hc= 4240eca3, eac00078: hc= 346fe350, eac00088: hc= 1db4b415, eac00098: hc= 429addef, eac000a8: hc= 45609812, eac000b8: hc= 489fe953, eac000c8: hc= 7a8f6d64
eac00038: hc= 7e628e42, eac00048: hc= 7869cfe0, eac00058: hc= 6aceb8e2, eac00068: hc= 29cc3436, eac00078: hc= 1d77daaa, eac00088: hc= 27b4de03, eac00098: hc= 535bab52, eac000a8: hc= 274cbf3f, eac000b8: hc= 1f9fd541, eac000c8: hc= 3669ae9f
eac00038: hc= 772a3766, eac00048: hc= 749b46a8, eac00058: hc= 7e3bfb66, eac00068: hc= 13f62649, eac00078: hc= 054b8cdc, eac00088: hc= 230cc23b, eac00098: hc= 1aa3c177, eac000a8: hc= 74f2794a, eac000b8: hc= 5af92541, eac000c8: hc= 1afcfd10
eac00038: hc= 396e1dd8, eac00048: hc= 6c696d5c, eac00058: hc= 7d8aea9e, eac00068: hc= 2b316b76, eac00078: hc= 39862621, eac00088: hc= 16315e08, eac00098: hc= 03146a9a, eac000a8: hc= 3162a60a, eac000b8: hc= 4382f3da, eac000c8: hc= 4a578fd6
eac00038: hc= 225765b0, eac00048: hc= 17d5176d, eac00058: hc= 26f50154, eac00068: hc= 1f2a45c7, eac00078: hc= 104b1bcd, eac00088: hc= 330e3816, eac00098: hc= 6a844689, eac000a8: hc= 12330301, eac000b8: hc= 530a3ffc, eac000c8: hc= 45eee3fb
eac00038: hc= 3f9432e0, eac00048: hc= 1a9830bc, eac00058: hc= 7da79447, eac00068: hc= 04f801c4, eac00078: hc= 363bed68, eac00088: hc= 185f62a9, eac00098: hc= 1e4651bf, eac000a8: hc= 1aa0e220, eac000b8: hc= 385db088, eac000c8: hc= 0ef0cda1

補足として; このコードを見ると

if (value == 0) value = 0xBAD ;

0xBAD は、0 がこの値にマップされるため、通常の hashCode の 2 倍の可能性があるようです。これを十分に実行すると、

long count = 0, countBAD = 0;
while (true) {
    for (int i = 0; i < 200000000; i++) {
        int hc = new Object().hashCode();
        if (hc == 0xBAD)
            countBAD++;
        count++;
    }
    System.out.println("0xBAD ratio is " + (double) (countBAD << 32) / count + " times expected.");
}

版画

0xBAD ratio is 2.0183116992481205 times expected.
4

4 に答える 4

23

これは明らかに実装固有です。

以下にObject.hashCode()、OpenJDK 7 で使用される実装を含めます。

oopこの関数は 6 つの異なる計算方法をサポートしますが、そのうち 2 つだけがオブジェクトのアドレス (「アドレス」は への C++キャスト)を通知しますintptr_t。2 つの方法の 1 つはアドレスをそのまま使用するのに対し、もう 1 つはビットをいじってから、あまり更新されない乱数で結果をマッシュアップします。

残りのメソッドのうち、1 つは定数 (おそらくテスト用) を返し、1 つは連番を返し、残りは疑似乱数シーケンスに基づいています。

メソッドは実行時に選択できるようで、デフォルトはメソッド 0 のようですos::random()。後者は線形合同ジェネレーターであり、競合状態がスローされたとされています。:-) 最悪の場合、2 つのオブジェクトが同じハッシュ コードを共有することになるため、競合状態は許容されます。これは不変条件を壊しません。

計算は、ハッシュ コードが初めて必要なときに実行されます。一貫性を維持するために、結果はオブジェクトのヘッダーに格納され、その後の への呼び出しで返されますhashCode()。キャッシュはこの関数の外で行われます。

要約するとObject.hashCode()、オブジェクトのアドレスに基づく概念は、大部分が歴史的な人工物であり、現代のガベージ コレクターの特性によって時代遅れになっています。

// hotspot/src/share/vm/runtime/synchronizer.hpp

// 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 an unguarded global Park-Miller RNG,
     // so it's possible for two threads to race and generate the same 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 = 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 = 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 ;
  assert (value != markOopDesc::no_hash, "invariant") ;
  TEVENT (hashCode: GENERATE) ;
  return value;
}
于 2012-12-13T13:05:59.213 に答える
5

通常は、オブジェクトのメモリ アドレスです。ただし、メソッドがオブジェクトで初めてhashcode呼び出されると、整数がそのオブジェクトのヘッダーに格納されるため、次の呼び出しで同じ値が返されます (おっしゃるように、ガベージ コレクションを圧縮するとアドレスが変更される可能性があります)。私の知る限り、それが Oracle JVM での実装方法です。

EDIT：JVMソースコードを掘り下げると、これが表示されます（synchronizer.cpp）：

// 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 an unguarded global Park-Miller RNG,
     // so it's possible for two threads to race and generate the same 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 = 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 = 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 ;
  assert (value != markOopDesc::no_hash, "invariant") ;
  TEVENT (hashCode: GENERATE) ;
  return value;
}

したがって、Oracle JVMでそれを行う6つの異なる方法のうちの1つは、私が言ったことと同等です...値は、メソッド呼び出しによってオブジェクトのヘッダーに格納されますget_next_hash(その方法FastHashCodeが呼び出され、ネイティブバージョンから呼び出されます)のObject.hashCode()。

于 2012-12-13T12:52:35.383 に答える
2

私見ですが、実装に依存しますが、JVM のオブジェクト参照は実際のメモリ アドレスではなく、実際のアドレスを指す内部 JVM 参照です。これらの内部参照は、最初はメモリ アドレスに基づいて生成されますが、破棄されるまでオブジェクトに関連付けられたままになります。

私がこれを言うのは、Java HotSpot GC が何らかの形式のコレクターをコピーしており、コレクターをlive objects1 つのヒープから別のヒープにトラバースしてコピーし、old heapその後破棄することによって機能するためです。したがって、GC が発生すると、JVM はすべてのオブジェクトの参照を更新する必要はなく、内部参照にマップされた実際のメモリ アドレスを変更するだけです。

于 2012-12-13T13:16:25.667 に答える
0

メモリアドレスからハッシュコードを導出することによって実装されるという Object.hashCode() に対する Javadoc の提案は、単に時代遅れです。

おそらく、ガベージ コレクターのコピーではこの実装パスが使用できなくなったことに誰も気にしていませんでした (または気づいていませんでした) (オブジェクトが別のメモリ ロケーションにコピーされるとハッシュコードが変更されるため)。

ヒープスペースを節約できるため、コピーガベージコレクターが登場する前にハッシュコードをそのように実装することは非常に理にかなっています。非コピー GC (CMS) は、今日でもハッシュコードをそのように実装している可能性があります。

于 2012-12-13T15:44:12.597 に答える