IdentityHashMap

最近使用 ANTLR4 时看到其 ParseTreeProperty 类用到了 IdentityHashMap，本文简要记录。

根据 IdentityHashMap 的 Java Doc 可知：

This class implements the Map interface with a hash table, using reference-equality in place of object-equality when comparing keys (and values). In other words, in an IdentityHashMap, two keys k1 and k2 are considered equal if and only if (k1==k2). (In normal Map implementations (like HashMap) two keys k1 and k2 are considered equal if and only if (k1==null ? k2==null : k1.equals(k2)).)

其与 HashMap 的最大不同为比较 key 时，IdentityHashMap 仅比较引用，而 HashMap 则是调用的 key 的 equals 方法进行比较，同时，文档中还提到：

A typical use of this class is topology-preserving object graph transformations, such as serialization or deep-copying.

IdentityHashMap 最典型的使用场景为图的处理，比如我们存在多个值相同的顶点，如果使用 HashMap 的话，后添加至 HashMap 的顶点就会覆盖掉之前添加到 HashMap 的值相同的顶点。但是在图中，我们知道这两个顶点其实不应该相同，即使此时他们的值恰好相同，此时就需要使用 IdentityHashMap 来处理此类问题，ANTLR4 也是使用此特性来存储每个节点对应的属性值。其 ParseTreeProperty 类的源码如下：

package org.antlr.v4.runtime.tree;

import java.util.IdentityHashMap;
import java.util.Map;

/**
 * Associate a property with a parse tree node. Useful with parse tree listeners
 * that need to associate values with particular tree nodes, kind of like
 * specifying a return value for the listener event method that visited a
 * particular node. Example:
 *
 * <pre>
 * ParseTreeProperty&lt;Integer&gt; values = new ParseTreeProperty&lt;Integer&gt;();
 * values.put(tree, 36);
 * int x = values.get(tree);
 * values.removeFrom(tree);
 * </pre>
 *
 * You would make one decl (values here) in the listener and use lots of times
 * in your event methods.
 */
public class ParseTreeProperty<V> {
 protected Map<ParseTree, V> annotations = new IdentityHashMap<ParseTree, V>();

 public V get(ParseTree node) { return annotations.get(node); }
 public void put(ParseTree node, V value) { annotations.put(node, value); }
 public V removeFrom(ParseTree node) { return annotations.remove(node); }
}

类似地，Ehcache2 在遍历对象图的过程中也用到了 IdentityHashMap，源码位于：ObjectGraphWalker.java at v2.11.0.0.75。

我们可以写一个简短的测试代码来展示 IdentityHashMap 与 HashMap 的区别：

package me.tianshuang;

import java.util.HashMap;
import java.util.IdentityHashMap;
import java.util.Map;

public class IdentityHashMapTest {

    public static void main(String[] args) {
        Map<Integer, String> identityHashMap = new IdentityHashMap<>();
        identityHashMap.put(new Integer(1), "first");
        identityHashMap.put(new Integer(1), "second");
        System.out.println("identityHashMap: " + identityHashMap);

        Map<Integer, String> hashMap = new HashMap<>();
        hashMap.put(new Integer(1), "first");
        hashMap.put(new Integer(1), "second");
        System.out.println("hashMap: " + hashMap);
    }

}

输出如下：

identityHashMap: {1=second, 1=first}
hashMap: {1=second}

可以看出，与我们上面提到的原理一致，除了这一主要的区别外，IdentityHashMap 内部实现与 HashMap 也有一些差异，如使用的负载因子为 2/3。在此实现中为何采用了 2/3 作为负载因子而不是像 HashMap 一样使用 0.75 呢？可以参考：Open Addressing。

计算哈希是使用的默认的 System.identityHashCode() 方法而不会使用 key 对应的类覆写的 hashCode() 方法，冲突时采用步长为 2 进行线性探测空闲空间进行存储，为何采用的步长为 2 呢？在文档中有如下描述：

This is a simple linear-probe hash table, as described for example in texts by Sedgewick and Knuth. The array alternates holding keys and values. (This has better locality for large tables than does using separate arrays.) For many JRE implementations and operation mixes, this class will yield better performance than HashMap (which uses chaining rather than linear-probing).

即底层的数据结构为 Object[] table 而不是 HashMap 中使用的 Node<K,V>[] table，在 IdentityHashMap 中，key 和 value 都存储在该数组中，相比使用两个数组来分别存储 key 和 value 的技术方案，单个数组对于大的哈希表能够提供更好的本地性。对于大多数的 JRE 实现，IdentityHashMap 能够提供比 HashMap 更好的性能。可以用以下示例来描述数组中的元素分布：

[key1, value1, null, null, key2, value2, null, null]

这就解释了在 hashCode 冲突进行线性探测时的步长为何为 2。同理，我们知道 key 全部位于偶数索引上，所以这也解释了 hash 函数中的移位操作的原因，源码位于 IdentityHashMap.java at jdk8-b120:

/**
 * Returns index for Object x.
 */
private static int hash(Object x, int length) {
    int h = System.identityHashCode(x);
    // Multiply by -127, and left-shift to use least bit as part of hash
    return ((h << 1) - (h << 8)) & (length - 1);
}

我们将移位部分转换为乘法即为 h × 2¹ - h × 2⁸ = h × 2 - h × 256 = h × (-254)，该注释表示乘以 -127 然后再左移一位，即等同于乘以 -254，有人认为该段注释不够清晰，可以参考：JDK-8046362 IdentityHashMap.hash comments should be clarified - Java Bug System。在 JDK 15 中，该段注释已经被优化为如下代码 IdentityHashMap.java at jdk-15+36:

/**
 * Returns index for Object x.
 */
private static int hash(Object x, int length) {
    int h = System.identityHashCode(x);
    // Multiply by -254 to use the hash LSB and to ensure index is even
    return ((h << 1) - (h << 8)) & (length - 1);
}

其中 h << 1 可以保证最低位为 0，即最后计算的数字为偶数，而为何还需要减去 h << 8 呢？主要是考虑 System.identityHashCode() 的底层实现，在部分 JVM 实现中，采用的为内存地址或单调递增的值，那么在此种场景下，连续创建的对象仅有低位不同，此时使用减去 h << 8 可以将低位的变化反映在高位中，以使计算出的 int 值映射到哈希表中时尽可能均匀分布。相关细节可以参考文末引用。

关于该类的其他部分实现与 ThreadLocalMap 有相似之处，此处不再赘述。

Reference

What is the purpose of this code in IdentityHashMap.hash()? - Stack Overflow
System.identityHashCode()