HashMap 源码探究
这两天一直在研究HashMap的源码,也算研究个大概了。怕以后忘记,也为了能给其他同学做参考交流,就理一下思路给贴出来吧。
本文是以加注释的方式来解读put、resize、get等主要方法,有不对的地方欢迎评论讨论
put:
public V put(K key, V value) {
//这里调用了putVal()
return putVal(hash(key), key, value, false, true);
}
hash:
static final int hash(Object key) {
int h;
//这里用key的hashcode与自身右移16位做异位运算
//为了&(length-1)获得数组下标时,让下标不止受hashcode的的后几位影响,减小hash冲突
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
putVal:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判断table(hashmap的数组)是否为空,为空则初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//判断对应的数组位置是否为null,为null则直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//如果数组相应的位置节点的key和插入的key相同,则用e暂存(之后会直接修改节点的value值)
//这里用了==判断的同时还用了equals判断,这里是因为用户可能重写equals,要让用户重写的equals也生效
//先用hash判断再用equals判断是为了避免用户重写的equals太复杂而执行过多的计算
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果数组相应位置的节点是TreeNode的实现类的话,说明是红黑树不是链表,就做红黑树的插入操作
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//否则,相应位置上是链表
else {
//从链表头部开始往下一个个判断,bigCount是链表长度-1
for (int binCount = 0; ; ++binCount) {
//如果遍历到链表尾部,则在尾部插入新的节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果链表长度大于TREEIFY_THRESHOLD (8),则执行treeifyBin方法,此方法先判断数组容量有没有大于64,小于64则扩容,否则转化为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果在链表中存在key相同的节点,则返回,此时e是key值和插入的key值相同的节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//前面的e=p.next和此行的p=e 是利用e在链表中遍历
p = e;
}
}
//如果e存在(e是key值和插入key值相同的Node)
if (e != null) { // existing mapping for key
//将e的旧value暂存
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//将value更新,因为e是key等于新传入key的Node指针,直接修改value即可
e.value = value;
//这个方法体是空的,在这里调用没什么用,但是在LinkedHashMap中被重写了
afterNodeAccess(e);
//返回key对应的旧value,因为put方法是有返回值的,返回值就是key对应的旧value
return oldValue;
}
}
++modCount;
//threshold是capacity * load factor,capacity是数组长度,factor是加载引子,如果size大于数组长度*加载因子,则扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
//不存在旧value则返回null
return null;
}
get:
public V get(Object key) {
Node<K,V> e;
//key对应的有值时调用getNode
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//如果table数组不为空再接着判断
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//判断数组对应的位置节点的key是否等于传入的key,等于则直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果不等于则判断是否!=null
if ((e = first.next) != null) {
//如果数组对应的节点时TreeNode的实现则从红黑树中寻找并直接返回
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//在链表中挨个查询,找到则返回
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
resize:(初始化和扩容)
final Node<K,V>[] resize() {
//原数组赋值给临时变量oldTab
Node<K,V>[] oldTab = table;
//旧数组容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//旧的扩容阈值(加载因子*容量)
int oldThr = threshold;
//新的容量,新的扩容阈值
int newCap, newThr = 0;
//如果旧数组容量>0
if (oldCap > 0) {
//如果旧数组容量>最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果新数组容量<<1(也就是扩大二倍)之后<=最大容量,并且旧容量>默认容量(16)。
//在判断中已经将newCap扩大为oldCap的二倍了
//这一步是核心判断
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//新的扩容阈值扩大为原来的二倍
newThr = oldThr << 1; // double threshold
}
//这一步不太理解,什么时候旧的容量=0并且加载因子>0?
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//如果oldCap==0,oldThr==0,即还没被初始化过
else { // zero initial threshold signifies using defaults
//初始化新数组容量为默认初始化容量(16)
newCap = DEFAULT_INITIAL_CAPACITY;
//初始化扩容阈值为 加载因子*默认容量
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果新扩容阈值==0(这一步不太理解什么时候会==0?)
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
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;
//把遍历到的数组对应位置的元素赋给e
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果e.next==null,说明不是链表和数组
if (e.next == null)
//把e放到新数组的对应位置
newTab[e.hash & (newCap - 1)] = e;
//如果e时TreeNode的实现类,说明对应位置是红黑树
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//否则就是链表了
else { // preserve order
//扩容之后链表上的每个元素可能放在原下标处,可能放在原下标+新容量/2。
//这点不清楚的可以计算比较一下旧下标:hash&(旧容量-1))和新下标:hash&(新容量-1),会发现新的下标只可能在原下标或原下标+新容量/2处
//这里的几个Node类型的局部变量就是为了实现链表上元素位置改变用的
//应该放在原下标的链表的头节点和尾节点
Node<K,V> loHead = null, loTail = null;
//应该放在新下标的链表的头节点和尾节点
Node<K,V> hiHead = null, hiTail = null;
//用来遍历链表
Node<K,V> next;
//这个循环的作用是遍历链表,计算链表的每个元素应该放在新下标的链表上还是旧下标的链表上
do {
next = e.next;
//这里很巧妙,看次是遍历的元素应该放在哪个链表上只用计算一下hash & oldCap
//因为旧下标hash & (oldCap-1)和新下标 hash & (newCap-1)的二进制位上只有一位不同,这一位用hash & oldCap正好可以计算出来
//这里不详细展开了,想理解的可以自己计算一下,记得oldCap和newCap都是2的n次方,或者可以在文章下面评论,我再补充
//说明在原下标处
if ((e.hash & oldCap) == 0) {
//第一次插入让loHead指向当前元素,loHead是头指针
if (loTail == null)
loHead = e;
//第二次插入,让loTail指向当前元素,loTail是尾指针
else
loTail.next = e;
//loTail始终指向新插入的,也就是该链表最后一个元素
loTail = e;
}
//说明在新下标处
else {
//这里和原下标处的逻辑一样,就是把计算出在新下标出的链表都挂在hiHead上
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//如果原下标的链表存在,则挂在对应数组位置上
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//如果新下表的链表存在,则挂在新位置上,新位置下标为什么是j + oldCap这个在前面说过了,这里就不赘述了
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
remove:
public V remove(Object key) {
Node<K,V> e;
//调用了removeNode方法
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
removeNode:
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//对数组判空,并根据hash算出下标,将下标对应的元素赋给p
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
//如果p的key等于传入的key
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
//判断p所在的节点是否有next的同时将e指向p.next
else if ((e = p.next) != null) {
//如果p是TreeNode的实现类,说明删除的节点在红黑树中
if (p instanceof TreeNode)
//从红黑树中找到对应的节点
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
//从链表中寻找删除的节点
else {
do {
//判断e是否是要删除的节点,如果是,将node指向e
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
//p指向遍历结束前的e的前一个元素
p = e;
//通过e=e.next循环遍历链表
} while ((e = e.next) != null);
}
}
//如果node不为空并且(matchValue(匹配value)不开启或value等于node.value)
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//如果node是TreeNode的实现类,则从红黑树中删除node节点
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//node==p说明符合前面判断:删除的节点在数组上
else if (node == p)
//删除数组上对应的元素
tab[index] = node.next;
//否则待删除的元素在链表上
else
//p指向链表中待删除的前一个元素,node是待删除元素,这样就把node指向的元素从链表中删除了
p.next = node.next;
//modCount是操作次数,自然要加一
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}