JVM常用概念之身份哈希码

问题

当我们调用Object.hashCode时，如果没有用户没有提供哈希码，会发生什么？ System.identityHashCode如何工作？它是否获取对象地址？

基础知识

在 Java 中，每个对象都有equals和hashCode ，即使用户不提供。如果用户不提供equals的覆盖，则使用== (identity) 比较。如果用户不提供hashCode的覆盖，则使用System.identityHashCode执行哈希码计算。

Object.hashCode的Javadoc说明，hashCode 的一般约定是：

• 在 Java 应用程序执行期间，如果对同一对象多次调用 hashCode 方法，则该方法必须始终返回相同的整数，前提是对象上用于 equals 比较的信息未发生修改。此整数不必在应用程序的一次执行和同一应用程序的另一次执行之间保持一致。
• 如果根据 equals(Object) 方法两个对象相等，则对两个对象中的每一个调用 hashCode 方法必须产生相同的整数结果。
• 如果两个对象根据 equals(java.lang.Object) 方法不相等，则不要求对这两个对象分别调用 hashCode 方法必须产生不同的整数结果。但是，程序员应该意识到，对不相等的对象产生不同的整数结果可能会提高哈希表的性能。

在合理实用的情况下，Object 类定义的 hashCode 方法会为不同的对象返回不同的整数。（这通常是通过将对象的内部地址转换为整数来实现的，但 Java™ 编程语言并不要求采用这种实现技术。）

哈希码应该具有两个属性：a)分布性好，即不同对象的哈希码尽可能不同；b)幂等性，即具有相同关键对象组件的对象具有相同的哈希码。请注意，后者意味着如果对象没有更改这些关键对象组件，则其哈希码也不应该更改。

更改对象的方式经常会导致错误，即其hashCode在使用后发生变化。例如，将对象作为键添加到HashMap ，然后更改其字段，使 hashCode 也发生变化，这会导致令人惊讶的行为：可能根本无法在映射中找到该对象，因为内部实现会在“错误”的存储桶中查找。同样，哈希码分布不均（例如返回常量值）也经常会导致性能异常。

对于用户指定的哈希码，这两个属性都是通过对用户选择的字段集进行计算来实现的。如果字段和字段值足够多样化，它将分布良好，并且通过在未更改的（例如 final）字段上进行计算，我们可以获得幂等性。在这种情况下，我们不需要将哈希码存储在任何地方。一些哈希码实现可能会选择将其缓存在另一个字段中，但这不是必需的。

对于身份哈希码，不能保证有字段可用于计算哈希码，即使有，我们也不知道这些字段实际上有多稳定。考虑没有字段的java.lang.Object ：它的哈希码是什么？两个分配的Object几乎是彼此的镜像：它们具有相同的元数据，具有相同的（即空的）内容。它们唯一不同之处在于它们分配的地址，但即便如此也存在两个问题。首先，地址的熵非常低，特别是来自大多数 Java GC 所采用的 bump-ptr 分配器时，因此分布不太好。其次，GC 会移动对象，因此地址不是幂等的。 从性能角度来看，返回常量值是行不通的。

因此，当前的实现从内部 PRNG（“良好分布”）计算身份哈希码，并将其存储为每个对象（“幂等性”）。

为了实现这一点，Hotspot JVM 有几种不同风格的身份哈希码生成器，它将计算出的身份哈希码存储在对象头中以保证稳定性。身份哈希码生成器的选择直接影响hashCode本身和hashCode用户的性能，尤其是java.util.HashMap 。将计算出的身份哈希码存储在对象头中的实现选择直接影响哈希码的准确性（我们可以存储多少位）以及与对象头其他用户的复杂交互。

Hotspot 代码库中有一个地方生成了哈希码，代码如下：

static inline intptr_t get_next_hash(Thread* current, oop obj) {...if (hashCode == 0) {// Use os::random();} else if (hashCode == 1) {// Use address with some mangling} else if (hashCode == 2) {// Use constant 1} else if (hashCode == 3) {// Use global counter} else if (hashCode == 4) {// Use raw address} else {// Use thread-local PRNG}...
}

该设置可作为-XX:hashCode VM 选项访问。生成的哈希码稍后将被安装到 ObjectSynchronizer::FastHashCode 中的对象头中，并在下一次哈希码请求中重用。

哈希码存储

我们可以使用JOL查看身份哈希码存储。实际上，有一个特定的示例已经捕获了我们想要的内容：

import org.openjdk.jol.info.ClassLayout;
import org.openjdk.jol.vm.VM;import static java.lang.System.out;/*** @author Aleksey Shipilev*/
public class JOLSample_15_IdentityHashCode {/** The example for identity hash code.** The identity hash code, once computed, should stay the same.* HotSpot opts to store the hash code in the mark word as well.* You can clearly see the hash code bytes in the header once* it was computed.*/public static void main(String[] args) {out.println(VM.current().details());final A a = new A();ClassLayout layout = ClassLayout.parseInstance(a);out.println("**** Fresh object");out.println(layout.toPrintable());out.println("hashCode: " + Integer.toHexString(a.hashCode()));out.println();out.println("**** After identityHashCode()");out.println(layout.toPrintable());}public static class A {// no fields}}

$ java -cp jol-samples/target/jol-samples.jar org.openjdk.jol.samples.JOLSample_15_IdentityHashCode
...**** Fresh object
org.openjdk.jol.samples.JOLSample_15_IdentityHashCode$A object internals:
OFF  SZ  DESCRIPTION             VALUE0   8  (object header: mark)   0x0000000000000001 (non-biasable; age: 0)8   4  (object header: class)  0x00cc400012   4  (object alignment gap)
Instance size: 16 bytes
Space losses: 0 bytes internal + 4 bytes external = 4 bytes totalhashCode: 4e9ba398**** After identityHashCode()
org.openjdk.jol.samples.JOLSample_15_IdentityHashCode$A object internals:
OFF  SZ  DESCRIPTION             VALUE0   8  (object header: mark)   0x0000004e9ba39801 (hash: 0x4e9ba398; age: 0)8   4  (object header: class)  0x00cc400012   4  (object alignment gap)
Instance size: 16 bytes
Space losses: 0 bytes internal + 4 bytes external = 4 bytes total

在这里，内部生成器算出此对象的哈希码是4e9ba398 ，并将其记录在对象头中。 每次后续调用身份哈希码时，现在都会重用此值。

哈希码生成器随机性

为了估计身份哈希码生成器的随机性，我们可以使用如下测试：

public class HashCodeValues {static long sink;public static void main(String... args) {for (int t = 0; t < 100000; t++) {for (int c = 0; c < 1000; c++) {sink = new Object().hashCode();}System.out.println(new Object().hashCode());}}
}

此测试的目标是打印连续对象的标识哈希码。它伴随着演示问题：一些生成器的分布非常糟糕，因此在大型图形规模上它们彼此难以区分。因此，测试跳过打印大多数中间对象的哈希码，同时仍然（尴尬地）确保计算哈希码。

哈希码值的热图将是这样的：

请注意以下几点：

• 这两个 PRNG 的表观值域几乎占所有可能哈希码值的一半。值中只有“上”半部分存在，因为在 64 位 JVM 中，只有身份哈希码的前 31 位存储在标头中。
• 对象地址的熵非常低。这是由于(T)LAB 分配的线性特性：时间相邻的对象将具有非常相似的地址。事实上，这就是为什么从对象地址生成哈希码是一个坏主意！
• 全局计数器的分布很不方便。全局计数器的值域仅仅是我们曾经计算过哈希码的对象的数量。
• 常量哈希码表现出极其糟糕的分布。

对于基于地址和全局计数器的哈希码，经常被忽视的一点是——虽然它们可能比 PRNG 更独特（PRNG 还会遭受生日悖论）——但它们的位相关性非常好，一旦您从哈希码中选择非低位子运行，就会面临发生子哈希冲突的风险。此外，当我们以常规模式处理元素时，常规哈希码（如全局计数器哈希码）的性能会很奇怪，例如，在哈希表中保留每隔一个对象会很快导致元素只有奇数/偶数哈希码，这会未充分利用哈希表，例如执行hashcode % size存储桶放置。

哈希码生成器性能

看看这些生成器的性能可能会很有趣。在像这样的简单 JMH 基准测试中，您或多或少会得到可预测的结果：

@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Fork(3)
@Threads(Threads.MAX)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@State(Scope.Benchmark)
public class IdentityHashCode {Object o = new Object();@Benchmarkpublic void cold(Blackhole bh) {Object lo = new Object();bh.consume(lo);bh.consume(lo.hashCode());}@Benchmarkpublic void warm(Blackhole bh) {Object lo = o;bh.consume(lo); // for symmetrybh.consume(lo.hashCode());}
}

在搭载最新 JDK 17 EA 的运行环境上，其运行效果如下：

Benchmark              Mode  Cnt    Score   Error  Units# Style 0: os::random() PRNG
IdentityHashCode.cold  avgt   15  400.703 ± 12.470  ns/op
IdentityHashCode.warm  avgt   15    5.051 ±  0.064  ns/op# Style 1: STW Address
IdentityHashCode.cold  avgt   15   86.180 ±  1.854  ns/op
IdentityHashCode.warm  avgt   15    5.109 ±  0.074  ns/op# Style 2: Constant 1
IdentityHashCode.cold  avgt   15   83.195 ±  2.034  ns/op
IdentityHashCode.warm  avgt   15    5.045 ±  0.060  ns/op# Style 3: Global Counter
IdentityHashCode.cold  avgt   15  124.748 ±  0.946  ns/op
IdentityHashCode.warm  avgt   15    5.069 ±  0.079  ns/op# Style 4: Address
IdentityHashCode.cold  avgt   15   86.232 ±  2.984  ns/op
IdentityHashCode.warm  avgt   15    5.066 ±  0.058  ns/op# Style 5: MT PRNG
IdentityHashCode.cold  avgt   15   90.809 ±  0.792  ns/op
IdentityHashCode.warm  avgt   15    5.087 ±  0.077  ns/op

请注意以下几点：

• 无论使用哪种生成器， warm变体的表现都相同。这是有道理的，因为该路径仅拾取已存储的身份哈希码。
• 大部分cold成本都花在了 VM 的哈希码计算上。即便是最基本的生成器（返回常数 1）的成本也相当高。
• 其他生成器的效果会滚雪球般增长。值得注意的是，os::random() PRNG 会将原子更新为 PRNG 状态，因此存在严重的可扩展性问题。

总结

身份哈希码生成器的选择在很大程度上取决于具体实现。生成器应具有良好的分布性和高度可扩展性。这就是为什么现代 Hotspot VM 默认使用hashCode=5 （多线程 PRNG）。

身份哈希码计算根本不涉及地址计算。这也是为什么最终从 Javadoc 中删除了令人困惑的地址计算提及的原因之一。