IdentityHashMap
简介
IdentityHashMap 类利用哈希表实现 Map 接口，比较键（和值）时使用引用相等性代替对象相等性。
换句话说，在 IdentityHashMap 中，当且仅当 (k1==k2) 时，才认为两个键 k1 和 k2 相等（在正常 Map 实现（如 HashMap）中，
当且仅当满足下列条件时才认为两个键 k1 和 k2 相等：(k1==null ? k2==null : e1.equals(e2))）。
注意
此类不是 通用 Map 实现！此类实现 Map 接口时，它有意违反 Map 的常规协定，该协定在比较对象时强制使用 equals 方法。此类设计仅用于其中需要引用相等性语义的罕见情况。 此类的典型用法是拓扑保留对象图形转换，如序列化或深层复制。
要执行这样的转换，程序必须维护用于跟踪所有已处理对象引用的“节点表”。
节点表一定不等于不同对象，即使它们偶然相等也如此。此类的另一种典型用法是维护代理对象。
例如，调试设施可能希望为正在调试程序中的每个对象维护代理对象。
此类提供所有的可选映射操作，并且允许 null 值和 null 键。此类对映射的顺序不提供任何保证；特别是不保证顺序随时间的推移保持不变。 此类提供基本操作（get 和 put）的稳定性能，假定系统标识了将桶间元素正确分开的哈希函数 (System.identityHashCode(Object))。 此类具有一个调整参数（影响性能但不影响语义）：expected maximum size。此参数是希望映射保持的键值映射关系最大数。 在内部，此参数用于确定最初组成哈希表的桶数。未指定所期望的最大数量和桶数之间的确切关系。 默认的价值加载因子为2/3,在重新哈希后，加载因子变为1/3.当哈希表中的条目数超出了加载因子与当前容量的乘积时，通过调用 reszie 方法将容量翻倍,重新进行哈希。增加桶数，重新哈希，可能相当昂贵。
因此创建具有足够大的期望最大数量的标识哈希映射更合算。另一方面，对 collection 视图进行迭代所需的时间与哈希表中的桶数成正比， 所以如果特别注重迭代性能或内存使用，则不宜将期望的最大数量设置得过高。
注意，此实现不是同步的。如果多个线程同时访问此映射，并且其中至少一个线程从结构上修改了该映射， 则其必须保持外部同步（结构上的修改是指添加或删除一个或多个映射关系的操作；仅改变与实例已经包含的键关联的值不是结构上的修改。）
这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。
最好在创建时完成这一操作，以防止对映射进行意外的不同步访问，如下所示：
Map m = Collections.synchronizedMap(new HashMap(...));
由所有此类的“collection 视图方法”所返回的迭代器都是快速失败的：在迭代器创建之后， 如果从结构上对映射进行修改，除非通过迭代器自身的 remove 或 add 方法，其他任何时间任何方式的修改， 迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败， 而不冒在将来不确定的时间任意发生不确定行为的风险。
注意，迭代器的快速失败行为不能得到保证，一般来说，存在不同步的并发修改时，不可能作出任何强有力的保证。 快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的方式是错误的，正确做法是： 迭代器的快速失败行为应该仅用于检测程序错误。
实现注意事项：此为简单的线性探头哈希表，如 Sedgewick 和 Knuth 原文示例中所述。 该数组交替保持键和值（对于大型表来说，它比使用独立组保持键和值更具优势）。对于多数 JRE 实现和混合操作， 此类比 HashMap（它使用链 而不使用线性探头）能产生更好的性能。
注意1：允许 null 值和 null 键。 注意2：此类对映射的顺序不提供任何保证；特别是不保证顺序随时间的推移保持不变。 注意3：此实现不是同步的。 注意4：迭代器的快速失败行为不能得到保证。 注意5：此为简单的线性探头哈希表。对于多数 JRE 实现和混合操作， 此类比 HashMap（它使用链 而不使用线性探头）能产生更好的性能。
使用场景
需要根据地址去判断的实现。
简单例子
- IdentityHashMapTest.java
import java.util.IdentityHashMap;
import java.util.Map;
/**
* @author binbin.hou
* date 2019/2/19
*/
public class IdentityHashMapTest {
public static void main(String[] args) {
Map<String, String> map = new IdentityHashMap<>();
map.put("A", "A-value-1");
map.put("A", "A-value-2");
map.put(new String("B"), "B-value-2");
map.put(new String("B"), "B-value-2");
System.out.println(map);
}
}
- 输出日志
{B=B-value-2, A=A-value-2, B=B-value-2}
源码分析
jdk 版本
java version "1.8.0_191"
接口定义
public class IdentityHashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, java.io.Serializable, Cloneable
{}
基础属性
底层依然使用的数组进行数据的存储。
/**
* The initial capacity used by the no-args constructor.
* MUST be a power of two. The value 32 corresponds to the
* (specified) expected maximum size of 21, given a load factor
* of 2/3.
*/
private static final int DEFAULT_CAPACITY = 32;
/**
* The minimum capacity, used if a lower value is implicitly specified
* by either of the constructors with arguments. The value 4 corresponds
* to an expected maximum size of 2, given a load factor of 2/3.
* MUST be a power of two.
*/
private static final int MINIMUM_CAPACITY = 4;
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<29.
*
* In fact, the map can hold no more than MAXIMUM_CAPACITY-1 items
* because it has to have at least one slot with the key == null
* in order to avoid infinite loops in get(), put(), remove()
*/
private static final int MAXIMUM_CAPACITY = 1 << 29;
/**
* The table, resized as necessary. Length MUST always be a power of two.
*/
transient Object[] table; // non-private to simplify nested class access
/**
* The number of key-value mappings contained in this identity hash map.
*
* @serial
*/
int size;
/**
* The number of modifications, to support fast-fail iterators
*/
transient int modCount;
/**
* Value representing null keys inside tables.
*/
static final Object NULL_KEY = new Object();
基础工具方法
感觉是为了避免 NPE，对 null 值进行了转换处理。
null 的处理
/**
* Use NULL_KEY for key if it is null.
*/
private static Object maskNull(Object key) {
return (key == null ? NULL_KEY : key);
}
/**
* Returns internal representation of null key back to caller as null.
*/
static final Object unmaskNull(Object key) {
return (key == NULL_KEY ? null : key);
}
hash 的处理
主要是在 put() 的时候使用。
/**
* 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);
}
/**
* Circularly traverses table of size len.
*/
private static int nextKeyIndex(int i, int len) {
return (i + 2 < len ? i + 2 : 0);
}
构造器
/**
* Constructs a new, empty identity hash map with a default expected
* maximum size (21).
*/
public IdentityHashMap() {
init(DEFAULT_CAPACITY);
}
/**
* Constructs a new, empty map with the specified expected maximum size.
* Putting more than the expected number of key-value mappings into
* the map may cause the internal data structure to grow, which may be
* somewhat time-consuming.
*
* @param expectedMaxSize the expected maximum size of the map
* @throws IllegalArgumentException if <tt>expectedMaxSize</tt> is negative
*/
public IdentityHashMap(int expectedMaxSize) {
if (expectedMaxSize < 0)
throw new IllegalArgumentException("expectedMaxSize is negative: "
+ expectedMaxSize);
init(capacity(expectedMaxSize));
}
/**
* Constructs a new identity hash map containing the keys-value mappings
* in the specified map.
*
* @param m the map whose mappings are to be placed into this map
* @throws NullPointerException if the specified map is null
*/
public IdentityHashMap(Map<? extends K, ? extends V> m) {
// Allow for a bit of growth
this((int) ((1 + m.size()) * 1.1));
putAll(m);
}
init()
其中 init() 源码如下:
/**
* Initializes object to be an empty map with the specified initial
* capacity, which is assumed to be a power of two between
* MINIMUM_CAPACITY and MAXIMUM_CAPACITY inclusive.
*/
private void init(int initCapacity) {
// assert (initCapacity & -initCapacity) == initCapacity; // power of 2
// assert initCapacity >= MINIMUM_CAPACITY;
// assert initCapacity <= MAXIMUM_CAPACITY;
table = new Object[2 * initCapacity];
}
默认初始化为 DEFAULT_CAPACITY*2，所以为什么不把 DEFAULT_CAPACITY 设置为 64？
capacity
对传入的大小进行校验。
并选择 2 的幂作为大小。
/**
* Returns the appropriate capacity for the given expected maximum size.
* Returns the smallest power of two between MINIMUM_CAPACITY and
* MAXIMUM_CAPACITY, inclusive, that is greater than (3 *
* expectedMaxSize)/2, if such a number exists. Otherwise returns
* MAXIMUM_CAPACITY.
*/
private static int capacity(int expectedMaxSize) {
// assert expectedMaxSize >= 0;
return
(expectedMaxSize > MAXIMUM_CAPACITY / 3) ? MAXIMUM_CAPACITY :
(expectedMaxSize <= 2 * MINIMUM_CAPACITY / 3) ? MINIMUM_CAPACITY :
Integer.highestOneBit(expectedMaxSize + (expectedMaxSize << 1));
}
putAll()
根据已有的 map 生成新的 map 中用到。
/**
* Copies all of the mappings from the specified map to this map.
* These mappings will replace any mappings that this map had for
* any of the keys currently in the specified map.
*
* @param m mappings to be stored in this map
* @throws NullPointerException if the specified map is null
*/
public void putAll(Map<? extends K, ? extends V> m) {
int n = m.size();
if (n == 0)
return;
if (n > size)
resize(capacity(n)); // conservatively pre-expand
for (Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
- resize() 扩容
/**
* Resizes the table if necessary to hold given capacity.
*
* @param newCapacity the new capacity, must be a power of two.
* @return whether a resize did in fact take place
*/
private boolean resize(int newCapacity) {
// assert (newCapacity & -newCapacity) == newCapacity; // power of 2
int newLength = newCapacity * 2;
Object[] oldTable = table;
int oldLength = oldTable.length;
if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
if (size == MAXIMUM_CAPACITY - 1)
throw new IllegalStateException("Capacity exhausted.");
return false;
}
if (oldLength >= newLength)
return false;
Object[] newTable = new Object[newLength];
for (int j = 0; j < oldLength; j += 2) {
Object key = oldTable[j];
if (key != null) {
Object value = oldTable[j+1];
oldTable[j] = null;
oldTable[j+1] = null;
int i = hash(key, newLength);
while (newTable[i] != null)
i = nextKeyIndex(i, newLength);
newTable[i] = key;
newTable[i + 1] = value;
}
}
table = newTable;
return true;
}
put() 核心方法
元素的放入
/**
* Associates the specified value with the specified key in this identity
* hash map. If the map previously contained a mapping for the key, the
* old value is replaced.
*
* @param key the key with which the specified value is to be associated
* @param value the value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
* @see Object#equals(Object)
* @see #get(Object)
* @see #containsKey(Object)
*/
public V put(K key, V value) {
final Object k = maskNull(key);
retryAfterResize: for (;;) {
final Object[] tab = table;
final int len = tab.length;
int i = hash(k, len);
for (Object item; (item = tab[i]) != null;
i = nextKeyIndex(i, len)) {
if (item == k) {
@SuppressWarnings("unchecked")
V oldValue = (V) tab[i + 1];
tab[i + 1] = value;
return oldValue;
}
}
final int s = size + 1;
// Use optimized form of 3 * s.
// Next capacity is len, 2 * current capacity.
if (s + (s << 1) > len && resize(len))
continue retryAfterResize;
modCount++;
tab[i] = k;
tab[i + 1] = value;
size = s;
return null;
}
}
get() 属性的获取
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key == k)},
* then this method returns {@code v}; otherwise it returns
* {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
@SuppressWarnings("unchecked")
public V get(Object key) {
Object k = maskNull(key);
Object[] tab = table;
int len = tab.length;
int i = hash(k, len);
while (true) {
Object item = tab[i];
if (item == k)
return (V) tab[i + 1];
if (item == null)
return null;
i = nextKeyIndex(i, len);
}
}
