Poison

IdentityHashMap

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

根据 IdentityHashMapJava 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 则是调用的 keyequals 方法进行比较,同时,文档中还提到:

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 类的源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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); }
}

同理,我们可以写一个简短的测试代码来展示 IdentityHashMapHashMap 的区别:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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);
}

}

输出如下:

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

可以看出,与我们上面提到的原理一致,除了这一主要的区别外,IdentityHashMap 内部实现与 HashMap 也有一些差异,如使用的负载因子为 2/3,计算哈希是使用的默认的 System.identityHashCode() 方法而不会使用 key 对应的类覆写的 hashCode() 方法,冲突时采用步长为 2 进行线性探测空闲空间进行存储,为何采用的步长为 2 呢?在文档中有如下描述:

Implementation note: 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 中,keyvalue 都存储在该数组中,相比使用两个数组来分别存储 keyvalue 的技术方案,单个数组对于大的哈希表能够提供更好的本地性。对于大多数的 JRE 实现,IdentityHashMap 能够提供比 HashMap 更好的性能。可以用以下图示来描述数组中的元素分布:

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

这就解释了在 hashCode 冲突进行线性探测时的步长为何为 2。关于该类的其他部分实现与 ThreadLocalMap 有相似之处,此处不再赘述。