HashMap 源码分析
1. 成员变量
// 未指定容量时的初始化容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量 2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默认的加载因子 用于扩容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 链表转为红黑树时链表的最小长度
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转换为链表的临界值,链表长度超过则不转换
static final int UNTREEIFY_THRESHOLD = 6;
// 转化为红黑树时数组的最小容量
static final int MIN_TREEIFY_CAPACITY = 64;
// HashMap的底层实现 一个Node数组
transient Node<K,V>[] table;
// 存储的数量
transient int size;
// 扩容的阈值
int threshold;
// 加载因子
final float loadFactor;
Node源码:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}TreeNode源码:
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* Returns root of tree containing this node.
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}2. 构造方法
a. 无参构造
将负载因子赋值为默认的加载因子,0.75
b. 有参构造
赋值初始容量,但是这个初始容量只是一个给定值,并不是数组实际值,如下构造方法:
实际的容量通过tableSizeFor方法得出.如下:
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}实际上得到的容量值就是大于等于cap并且最接近cap的一个2的n次幂的值
上面的移位操作,实际上就是在将最高位1后面的0全部变为1,return返回时再加1就等到了一个2的n次幂.
3. 扩容
HashMap的扩容是通过resize方法实现的,我们先看前一部分
首先我们拿到原table,并且拿到原来的table的大小,如果原table为null,则表示还没有添加任何元素进来,此时oldCap为0,否则为实际容量.
如果拿到的oldCap大于0,并且它大于允许的最大容量,那么我们将threshold改为Integer的最大值,然后直接返回,因为此时无法再扩大table的大小了,在扩大可能会抛出OOM异常.
否则的话,将newCap置为原容量的两倍,如果此时满足小于允许的最大容量,并且老的容量大于等于默认的初始化容量,则将新的newThr置为原oldThr的两倍.
而如果 oldThr大于0,表示此时table的容量为0,但是threshold已经被初始化过了.表示在执行构造方法时,指定了initialCapacity.此时直接将新的newThr置为原来的阈值(已经经过计算的)就可以了.
最后一个情况,就是使用的默认的无参构造方法启动的.此时直接将新的容量指定为16,新的扩容阈值指定为16*0.75
下面这一部分,判断newThr为0,也是上面的,如果在构造方法指定了initialCapacity,那么此时newThr仍然没被赋值,还是为0.此时我们直接将它赋值为newCap * loadFactor即可.
最后赋值threshold为newThr
下面就是使用新tab替换旧tab的过程.较长就不贴图直接贴代码了:
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;首先直接new了一个新的容量为newCap的newTab,然后将table直接指向newTab.接下来用oldTab进行下面的操作.
第一层循环,将tab数组进行循环.
首先拿到tab数组的索引为j的元素.将其赋值为e,然后帮助GC,原tab指向null.
如果e后面没有元素了,那么通过hash值直接将其填入新tab
如果e是一个红黑树的节点,那么根据红黑树的规则进行插入
如果e后面还有节点,且不是树节点,再通过一个do-while循环将这条链表的值插入新tab
先拿到下一个节点,赋值给next
然后通过(e.hash & oldCap)判断当前这个元素,是因在原来的位置,还是应该插入到新的位置(j+oldCap)
loxx代表了低位的节点,也就是在新数组中索引位置没有发生变化
hixx代表了高位的节点,也就是在新数组中索引位置发生变化了,多了个高位的长度,也就对应原数组的长度
while循环后,得到的两个链表,将他们连入新数组即完成了扩容操作,最后返回.
4. put方法
put方法将指定的值与key`对应.
首先通过hash(Object)方法获取key的hash值.
将对象的hashCode经过一次扰动后,得到hash值
随后通过putVal方法进行插入操作.
onlyIfAbsent表示如果键存在则不插入.
evict此参数在afterNodeInsertion方法中有用到,可能用于删除最老元素.
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}putValue方法首先把table赋值给tab,然后将table的长度赋值给n,如果table为null或者长度为0都会给table来一次默认的初始化操作.
随后判断(n - 1) & hash的位置上是不是为空,为空则直接插入,否则表示需要解决冲突.
这里很关键,这个地方判断了对应位置的hash值与传入hash值是否相等,如果不等直接结束.这里也就是为什么我们说的,重写了equals就要重写hashCode方法,否则这里无法判断相等.
如果插入的key值与对应位置的key值相等,或者key值equals相等,那么我们直接将这个首位置的元素替换为我们的元素(赋值为e,后面统一替换).
如果这个位置是一个红黑树的节点,那么通过红黑树的的操作将值进行插入.
否则就需要解决hash冲突,通过一个循环,binCount表示当前链表节点的数量.循环到最后一个空节点,new一个新的节点,将当前需要插入的Value通过尾插法进行插入.并且判断当前节点数量,如果达到了TREEIFY_THRESHOLD,那么就将这条链表进行一个treeifyBin,把它变成一个红黑树.
如果在循环的过程中,找到了key相等的节点,直接结束循环.
此时判断e是否为空,如果e不为空直接将e的值进行替换.
而如果是在一个没有任何元素的新位置中进行了插入,那么最终会将size++,并且将这个,如果大于了threshold,将进行一个resize扩容操作.
JDK1.8中采用的是尾插法,1.7及之前采用的是头插法.头插法在并发条件下可能造成死循环.但是并发条件下推荐使用ConcurrentHashMap而不是HashMap
5. remove方法
remove方法与put方法类似,找到指定元素,删除即可.
关于(e.hash & oldCap)
由于capacity的值永远都是2的n次幂(tableSizeFor决定),用二进制来表示就永远是最高位为1,其他的都是0
(e.hash & oldCap-1)表示e在原数组中的具体位置
(e.hash & 2*oldCap-1)表示e在新数组中的具体位置
2*oldCap-1(高位变0,其余全部为1)的二进制位数与oldCap相同
而我们通过e.hash & oldCap只是判断hash值对应的那个最高位是否为1,如果为1,那么它与2*oldCap-1的最高位相与也一定为1.
(e.hash & oldCap)为0表示,oldCap的最高位与e.hash值相应的那一位相与为0,因此e在新的数组中,仍然在原来的位置.
而(e.hash & oldCap)为1表示,oldCap的最高位与e.hash值相应的那一位相与为0,因此e在新数组中的位置,就要加上多的这一位,为2的n(对应的那一位同时为1的位次)次幂,即原来的长度加上当前的相对位置j.
