Java1.8-IdentityHashMap源码解析
2018-01-14 本文已影响856人
骑着乌龟去看海
概述
IdentityHashMap利用Hash表来实现Map接口，比较键（和值）时使用引用相等性代替对象相等性。
- 比如对于要保存的key，k1和k2，当且仅当k1== k2的时候，IdentityHashMap才会相等，而对于HashMap来说，相等的条件则是：(k1==null ? k2==null : k1.equals(k2))。
- IdentityHashMap不是Map的通用实现，它有意违反了Map的常规协定。并且IdentityHashMap允许key和value都为null。
- 同HashMap，IdentityHashMap也是无序的，并且该类不是线程安全的，如果要使之线程安全，可以调用Collections.synchronizedMap(new IdentityHashMap(...))方法来实现。
我们再通过一个例子来帮我们进行分析：
public static void main(String[] args) {
IdentityHashMap<String ,Integer> identityHashMap = new IdentityHashMap<>();
identityHashMap.put(new String("A"), 1);
identityHashMap.put(new String("B"), 2);
identityHashMap.put(new String("A"), 3);
System.out.println(identityHashMap);
}
打印：
{B=2, A=1, A=3}
属性
public class IdentityHashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, java.io.Serializable, Cloneable
{
/**
* 默认容量大小
*/
private static final int DEFAULT_CAPACITY = 32;
/**
* 最小容量
*/
private static final int MINIMUM_CAPACITY = 4;
/**
* 最大容量
* 事实上，该Map最多只能有MAXIMUM_CAPACITY-1个元素，因为它必须有一个key等于null的位置，
* 这是为了避免get,put,remove方法的无限循环
*/
private static final int MAXIMUM_CAPACITY = 1 << 29;
/**
* 用于存储实际元素的数组
*/
transient Object[] table; // non-private to simplify nested class access
/**
* map的大小
*/
int size;
/**
* 结构性修改
*/
transient int modCount;
/**
* key为null的处理
*/
static final Object NULL_KEY = new Object();
}
可以看到，IdentityHashMap底层是使用了一个数组来保存数据。
方法
put方法
- put的时候先通过引用是否相等判断key是不是已经在表中存在，如果存在更新oldValue为新的value，如果元素个数达到阈值，扩容处理，然后再找合适的位置放置key和value。
- put比较有意思的一点就是，在数组的i索引处存key，而紧挨着i的i+1处存value，并且由于hash方法的原因，key所对应的index全是偶数，自然i+1就是奇数了。这也说明了另一点，数组初始化的时候，数组的长度被定义为默认容量的2倍，因为数组元素的每次保存是都占了数组的两个位置。
- put的扩容条件是当存放的数组达到数组长度的1/3的时候，就需要扩容。
public V put(K key, V value) {
// key为null处理
final Object k = maskNull(key);
// 使用了jdk原先的这种标签来进行循环跳转
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)) {
// 如果key与数组原有的key相等，使用新的value代替旧的value，并返回旧的value
if (item == k) {
@SuppressWarnings("unchecked")
V oldValue = (V) tab[i + 1];
tab[i + 1] = value;
return oldValue;
}
}
// size加1
final int s = size + 1;
// Use optimized form of 3 * s.
// Next capacity is len, 2 * current capacity.
// 如果3*size 大于数组的length，则进行扩容，这里计算要注意，+的优先级是高于>号的，所以先算乘以3，再进行比较。
if (s + (s << 1) > len && resize(len))
// 扩容后重新计算元素的值，寻找合适的位置进行存放
continue retryAfterResize;
modCount++;
tab[i] = k;
tab[i + 1] = value;
// 更新size
size = s;
return null;
}
}
get方法
get方法则比较简单，根据key获取数组的索引，然后对象比较引用，基本类型比较数据是否相等即可。如果i处找到对象，说明i+1处就是索引对应的value，这也解释了初始化数组的时候2倍长度的原因了。
public V get(Object key) {
Object k = maskNull(key);
Object[] tab = table;
int len = tab.length;
// 获取元素的index
int i = hash(k, len);
while (true) {
Object item = tab[i];
// 判断是否相等，引用是否相等
if (item == k)
// 获取下一个索引位置的value
return (V) tab[i + 1];
// 获取不到，返回null
if (item == null)
return null;
// 遍历下一个key的索引，这里解决散列冲突的办法是若冲突，则往后寻找空闲区域
i = nextKeyIndex(i, len);
}
}
nextKeyIndex方法
该方法用于解决hash冲突时，取下一个位置进行判断，put的时候也是同样的做法。至于往后移2个单位，也是因为put的时候一个元素的key和value各占一个位置喽。
private static int nextKeyIndex(int i, int len) {
// 往后移两个单位
return (i + 2 < len ? i + 2 : 0);
}
containsValue方法
从循环遍历来看，也能得出数组偶数索引处存的全是元素的key，而奇数位置存的是元素的value。
public boolean containsValue(Object value) {
Object[] tab = table;
for (int i = 1; i < tab.length; i += 2)
if (tab[i] == value && tab[i - 1] != null)
return true;
return false;
}
capacity方法
/**
* 该值计算的是最小的大于expectedMaxSize的二次幂的值，
* 比如expectedMaxSize是5，返回的就是8
*/
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));
}
remove方法
public V remove(Object key) {
Object k = maskNull(key);
Object[] tab = table;
int len = tab.length;
// 计算hash
int i = hash(k, len);
while (true) {
Object item = tab[i];
// 查找引用相等的
if (item == k) {
modCount++;
size--;
@SuppressWarnings("unchecked")
V oldValue = (V) tab[i + 1];
tab[i + 1] = null;
tab[i] = null;
// 删除该元素后，需要把原来有冲突往后移的元素移到前面来
closeDeletion(i);
return oldValue;
}
if (item == null)
return null;
i = nextKeyIndex(i, len);
}
}
resize方法
private boolean resize(int newCapacity) {
// assert (newCapacity & -newCapacity) == newCapacity; // power of 2
int newLength = newCapacity * 2;
// 旧的数组
Object[] oldTable = table;
int oldLength = oldTable.length;
// 旧数组的长度如果是最大值的2倍
if (oldLength == 2 * MAXIMUM_CAPACITY) { // can't expand any further
// 并且如果原先元素的个数是最大容量-1，无法扩容，抛异常
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];
// 旧数组的key不为null，重新获取index后放到新的数组里
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
table = newTable;
return true;
}
equals和hashCode方法
- IdentityHashMap重写了equals和hashcode方法，不过需要注意的是hashCode方法并不是借助Object的hashCode来实现的，而是通过System.identityHashCode方法来实现的。
- 并且，hashCode的生成是与key和value都有关系的，这就间接保证了key和value这对数据具备了唯一的hash值。同时通过重写equals方法，判定只有key值全等情况下才会判断key值相等。这就是IdentityHashMap与普通HashMap不同的关键所在。
public int hashCode() {
int result = 0;
Object[] tab = table;
for (int i = 0; i < tab.length; i +=2) {
Object key = tab[i];
if (key != null) {
Object k = unmaskNull(key);
// 最终hashCode的生成与key和value都有关系
result += System.identityHashCode(k) ^
System.identityHashCode(tab[i + 1]);
}
}
return result;
}
public boolean equals(Object o) {
if (o == this) {
return true;
} else if (o instanceof IdentityHashMap) {
IdentityHashMap<?,?> m = (IdentityHashMap<?,?>) o;
if (m.size() != size)
return false;
Object[] tab = m.table;
for (int i = 0; i < tab.length; i+=2) {
Object k = tab[i];
if (k != null && !containsMapping(k, tab[i + 1]))
return false;
}
return true;
} else if (o instanceof Map) {
Map<?,?> m = (Map<?,?>)o;
return entrySet().equals(m.entrySet());
} else {
return false; // o is not a Map
}
}
总结
- IdentityHashMap的实现不同于HashMap，虽然也是数组，不过IdentityHashMap中没有用到链表，解决冲突的方式是计算下一个有效索引，并且将数据key和value紧挨着存在map中，即table[i]=key，那么table[i+1]=value。
- IdentityHashMap的hash的计算没有使用Object的hashCode方法，而是使用的System.identityHashCode方法。
- 其实有的时候我们常说的IdentityHashMap能保存重复的key是一种不太恰当的说法，因为IdentityHashMap的==操作是比较的内存地址，如果不是指向同一块内存，那这时候才可以保存相同的数据。
// 像这种情况，就不能保存相同的key
IdentityHashMap<String, Integer> map = new IdentityHashMap<>();
map.put("A", 1);
map.put("A", 3);
System.out.println(map);
问题
有一个问题没想清楚，就是计算index的时候，返回的结果一定是偶数么？有时间了再仔细想想。(代码如下)
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);
}
还有一些问题，留着以后思考，比如说Object.hashCode和System.identityHashCode方法同时native方法，底层的实现有什么区别么？等以后慢慢再想。
