# IdentityHashMap

## 简介

IdentityHashMap 类利用哈希表实现 Map 接口，比较键（和值）时使用引用相等性代替对象相等性。

## 注意

Map m = Collections.synchronizedMap(new 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();


## 基础工具方法

### 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 的处理

/**
* 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()

    /**
* 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];
}


### capacity

    /**
* 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()

    /**
* 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) {

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[] 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);
}
}


# 参考资料

IdentityHashMap

Java1.8-IdentityHashMap源码解析