HashMap源码之二：put方法
2018-08-02 本文已影响22人
涂豪_OP
上一篇讲了HashMap的概述，这次研究下HashMap的重要方法put；不管什么容器类，添加元素的方法总是重要的，不能忽略的：
/**
* Implements Map.put and related methods
*
* @param hash hash for key key的hash值
* @param key the key 键值对中的键
* @param value the value to put 键值对中的值
* @param onlyIfAbsent if true, don't change existing value 当存入一个元素是，如果此元素
* 已经存在，onlyIfAbsent指的是是否替换已经存在的元素，如果他为true，就不替
* 换，否则替换；默认为true，替换之
* @param evict if false, the table is in creation mode. evict是指当前的hashmap是不是
* 处于创建状态，默认是true，代表hashmap的table创建好了，可以put元素了
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//tab是HashMap的数组；要插入一个元素，首先要计算出这个元素应该放入数组的哪个位置;位置确定
//后，那个位置，可能已经存在一个元素，这时候就需要用待插入元素去更新原来的元素，或者在那个元素
//后面插入；p就是那个原来的元素，当然，他可能为空；n是数组的长度；i是待插入的元素在数组上的索引
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果当前的数组没有创建，，或者数组里面没有元素，那么调用resize()方法
//resize()方法的作用是初始化HashMap的数组或者对HashMap进行扩容。
//resize()是一个非常重要的方法，一会详细分析
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//元素插入桶的位置是由数组长度和key的hash值共同决定的，把这两个值进行与
//操作就能得出桶的索引；如果那个数组索引上没有元素，那么创建一个新的节点
//并放入数组中，这样就完成了插入；newNode()非常简单，不单独分析。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果i那个位置上已经存在元素，说明发生了hash碰撞，需要更新i这
//个位置连接的红黑树/链表上的节点;或者在红黑树/链表上新增新的元素
else {
Node<K,V> e; K k;
//因为两个不同的key可能会hash出同一个hash值，这个时候就产生hash碰撞了；发生碰撞的两个元素
//，他们的key可能一样，也可以不一样；如果一样的话，直接更新好了；如果不一样，那么只能把待插入
//的元素插入的p的后面，(k = p.key) == key || (key != null && key.equals(k))就是
//判断两个元素的key是不是相等。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//key相等的话就把p指向e，后面用得上
e = p;
//如果key不等，说明待插入的元素要插入到p的后面，这个p可能是红黑树中的一个节点，也有可能是链表
//中的一个节点，p后面连接不同的数据结构，插入的方法是不一样的，这里首先判断p后面是不是红黑树
else if (p instanceof TreeNode)
//以红黑树的方式插入待插入元素
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//这个分支代表p后面连接这个一个链表，以链表的方式插入目标元素
else {
//链表的插入就非常简单了，就是遍历该链表，然后一个个比较，必要的时候树化
//当然了，链表中的节点的key可能和待插入元素的key一样，如果一样的话，直
//接更新链表上的这个节点即可；如果没有一样的，那么在链表尾部插入该元素
//插入完成后，e就指向了空
for (int binCount = 0; ; ++binCount) {
//遍历到链表的尾部还没有发现有元素和目标元素的key一样，那么根据传进来的key和value创
//建一个全新节点插入链表尾部；注意，if里面已经对e赋值了，所以第二个if可以直接对e操作
if ((e = p.next) == null) {
//创建全新的节点并插入节点的尾部
p.next = newNode(hash, key, value, null);
//如果链表节点数量达到了阈值(8) - 1，那么调用treeifyBin进行链表的树化
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//这里就是判断目标元素和链表中的节点的key值是否一样，如果一样就直接更新，简单
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果e不为空，说明进入了第一个else分支，第一个else分支是指数组中已经存在一个key的hash和
//目标元素的key的hash相等的节点，如果e不为空，说明整个put其实就是更新老的节点
if (e != null) { // existing mapping for key
//获取老的值
V oldValue = e.value;
//onlyIfAbsent是传进来的，默认是false；所以进入if
if (!onlyIfAbsent || oldValue == null)
//简单的赋值
e.value = value;
//afterNodeAccess在HashMap中是一个空实现，
//在LinkedHashMap里面倒是有实现，暂时不管
afterNodeAccess(e);
return oldValue;
}
}
//修改次数+1，HashMap是线程不安全的，这玩意就是为
//了解决迭代的时候修改HashMap造成的异常，后面分析
++modCount;
//如果HashMap的元素个数超过阈值，就调用resize()进行扩容
if (++size > threshold)
resize();
//同afterNodeAccess，不管
afterNodeInsertion(evict);
return null;
}
纵观put方法，最重要，也是最难理解的是扩容方法resize()和树化方法treeifyBin(//参数略)，在分析这两个方法之前，先研究下红黑树节点是怎么被插入红黑树中的：
/**
* Tree version of putVal.
* 参数解释：
* 1.map : HashMap，简单
* 2.tab : HashMap中的数组，简单
* 3.h : key的hash值
* 4.k : key
* 5.v : value
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
//key的Class对象
Class<?> kc = null;
//searched是一个一次性开关，仅对根节点生效，下面会解释
boolean searched = false;
//putTreeVal()是TreeNode的方法，这个类有个成员变量parent，代表这个节
//点的父节点如果父节点不为空的话，那么先找到红黑树的根节点，root()方法就是
//往死里遍历红黑树，最终找到根节点；如果父节点为空，说明他本身就是根节点。
TreeNode<K,V> root = (parent != null) ? root() : this;
//从根节点开始遍历红黑树
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
//如果遍历到的节点的hash值大于目标key的hash
//值，其实节点的hash值就是key的hash值
if ((ph = p.hash) > h)
//如果遍历到的节点的key的hash目标元素的hash，那么说明
//这个元素应该插入到遍历到的节点的左边，此时将dir置成-1
dir = -1;
//反之置成1
else if (ph < h)
dir = 1;
//如果两个hash相等，key也相等，那么返回这个节点；看起来有点奇怪，怎么就
//直接返回了呢？新的value没有更新啊，其实在putVal的最后面已经进行了更新
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
//流程走到这里，说明待插入的元素的key的hash和当前节点的hash相等但是两个key本身不相等(此时就
//是发生了hash碰撞)。comparableClassFor的作用就是返回key的Class信息；如果key的类型实现了
//Comparable接口，那么返回key的类型信息，没有实现的话就返回null;因为红黑树的左右子节点之间的
//值是有大小之分的，要想有大小之分，就必须具有可比性，实现Comparable接口会让两个相同类型的变量
//之间可比；如果返回null，说明key没有可比性；dir = compareComparables(kc, k, pk)) == 0
//的意思是k和pk之间不可比，也就说待插入元素的key和节点的key之间不具有可比性
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
//在进for循环之前，searched为false；当遍历到根节点时，进入if，if里面通过find
//方法搜索了整棵树，如果能找到目标节点当然更好，找不到就再调用tieBreakOrder找一次
if (!searched) {
TreeNode<K,V> q, ch;
//把searched置为true，在遍历根节点的所有子节点时，都不会进这个分支
searched = true;
//find方法就是在红黑树里面查找key和目标元素key相等的节点
//这里分左右子树分别递归查找，短路操作是为了在左子树中找到
//后无需在右子树中再次查找；如果找到了，就把这个节点直接返回
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
//流程走到这里，说明还没有找到目标节点，也就是说目标元素的key和红黑树的节点的key的hash相等
//但是两个key本身之间无法比较；那就只能使出绝招了：tieBreakOrder；这个方法是调用系统的方
//法identityHashCode来比较，比较的也是hash，但是不是上面的hash了，感兴趣的可以了解下
dir = tieBreakOrder(k, pk);
}
//流程走到这，说明key的比较结果出来了，这就要插入了；只有当
//前节点没有子节点的时候才能插入，否则就要进行下一轮循环比较了
//把遍历到的节点赋值给xp，这里是把xp当做一个父
//节点来使用的，因为后面的流程会把p指向他的子节点
TreeNode<K,V> xp = p;
//如果dir小于0，说明目标元素要放在p的左子树，所以把p指向他的左子节点
//如果dir大于0，说明目标元素要放在p的右子树，所以把p指向他的右子节点
//如果p不为空，说p已经有左/右子节点了，拿到这个节点，开始下一轮循环
//如果p为空，说明已经循环到叶子节点了，这时候就要把目标元素插在叶子节点下面
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//next是Node的属性，TreeNode是Node的子类，继承了这个属性；
//这个属性记录了树化之前链表上节点的顺序，估计是为了反树化准备的
Node<K,V> xpn = xp.next;
//创建一个叶子节点，newTreeNode方法比较简单，不多说，注
//意最后一个参数；也就是说，每个红黑树节点都有一个next属性
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
//决定是插在左子树还是右子树
if (dir <= 0)
xp.left = x;
else
xp.right = x;
//将刚才创建的节点x赋值给他父节点的next属性
xp.next = x;
//将父节点赋值给刚才创建的子节点的parent和prev
x.parent = x.prev = xp;
//xpn是xp的next，xp又是遍历到的节点，所xpn是当前遍历到的节点的next果当前
//遍如历到的节点的next不为空，那么把当前遍历到的节点的prev指向刚才创建的节点
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
//修复红黑树的平衡性，比较复杂，暂时不管
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
可以看到，putTreeVal方法还是有点复杂的；下面研究扩容方法：
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
//扩容的方法，还肩负着初始化HashMap的重任
final Node<K,V>[] resize() {
//扩容前老的数组，当然如果是初始化HashMap的话，这个数组就是空了
Node<K,V>[] oldTab = table;
//老数组的长度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//老的扩容阈值
int oldThr = threshold;
//新数组的长度和扩容阈值
int newCap, newThr = 0;
//如果oldCap大于0，说明调用resize()是为了扩容
if (oldCap > 0) {
//若干老数组的长度超过了最大值，那么扩容失败
//；直接返回老数组，并且把阈值设置成最大值
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果没有超过最大值，那么新数组的长度是老数组长度的两个倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//阈值也翻倍
newThr = oldThr << 1; // double threshold
}
//如果oldCap == 0 ，说明是创建HashMap，oldThr
//大于0的话，说明调用带一个参数的HashMap的构造函数
else if (oldThr > 0) // initial capacity was placed in threshold
//对于带一个参数的构造函数，HashMap的容量就是扩容阈值
newCap = oldThr;
//种子情况就是最常见的了;HashMap map = new HashMap()，啥都没指定
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//对于一个参数的构造函数，只确定了容量，并没有确定新的扩容阈值
if (newThr == 0) {
//计算新的扩容阈值，简单
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//不管是扩容还是调用某个构造函数创建HashMap，走到这，新的扩容阈值算是定下来了，赋值
threshold = newThr;
//创建数组，这个数组对HashMap的重要性无需多言
@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没有后继节点，那么将此节点存入新数组，说明这个桶只有一个元素，没有链表和红黑树
//，e.hash & (newCap - 1)就是计算数组的索引；注意哦，这里是移动节点，所以是拿节
//点的hash与数组长度 - 1进行与运算确定这个节点位于数组中的索引；而上面putVal方法操
//作的是元素，所以是拿元素的key的hash与数组长度 - 1进行与运算确定元素在数组中的索引
//ps：其实这两个hash是一样的
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
//引入了两个链表：low、high；loHead是低位链表low的头结点，loTail是low的尾节点
//hiHead是高位链表high的头结点，hiTail是尾节点；这两个链表是为了拆分老数组某个桶
//后面连接的链表用的
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//循环获取链表中的节点
do {
next = e.next;
//这个操作猛如虎：oldCap是2的n次幂，形如100000......；e.hash & oldCap就是
//取e.hash的高位，相与的结果要么是e.hash的高位，要么是0；如果是0的话，进入if
if ((e.hash & oldCap) == 0) {
//如果链表尾节点都为空，说明这个链表是空的，此时将e置为头结点
if (loTail == null)
loHead = e;
//否则的话，就把e放到链表尾部
else
loTail.next = e;
//同时把链表尾节点指向e
loTail = e;
}
//如果相与结果不为0，那么就是e.hash的高位，进入else
else {
//道理同上
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//如果低位链表的尾节点不为空，那么将尾节点的后继节点置空
if (loTail != null) {
loTail.next = null;
//同时将低位节点放入第j个桶
newTab[j] = loHead;
}
//同上，不过是把高位节点放入低j + oldCap个桶
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
//返回新数组
return newTab;
}
方法本身不算难，他的扩容思想如下：
1.如果桶后面没接红黑树/链表，那么拿到这个节点的hash，与新数组的长度 - 1做与运算，确定桶的位置，然后把这个节点放入那个桶;
2.如果桶后面接着一个链表，那么将此链表一拆为二；拆分的依据是用节点的hash与老数组做与运算，与运算只有两个结果，要么是0，要么是hash的高位；如果结果是0，那么此节点插入低位链表；如果结果不等于0，那么将此插入高位链表；最后把低位链表放入第j个桶，把高位链表放入第j + oldCap个桶；
3.如果桶后面接着的是一棵树，那么调用split方法将红黑树拆分，下面研究下这个方法：
/**
* Splits nodes in a tree bin into lower and upper tree bins,
* or untreeifies if now too small. Called only from resize;
* see above discussion about split bits and indices.
*
* 拆分的思想是先将红黑树转化成两个链表；这两个链表必要的时候进行树化和反树化
*
* @param map the map HashMap，没问题
* @param tab the table for recording bin heads 新数组
* @param index the index of the table being split 桶的位置
* @param bit the bit of hash to split on 老数组的长度
*/
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
//红黑树的根节点
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
//引入四个红黑树节点，类似于链表的拆分，高低位的头尾节点
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
//高低位节点的计数器
int lc = 0, hc = 0;
//通过节点的next往死里遍历红黑树,但是for循环可以这样用的吗
for (TreeNode<K,V> e = b, next; e != null; e = next) {
//重新赋值next节点
next = (TreeNode<K,V>)e.next;
//把e的next置空，因为e要插到两个链表中的一个区，他的后继节点还不确定，所以置空
e.next = null;
//与操作，根链表的拆分是一毛一样的
if ((e.hash & bit) == 0) {
//如果低位尾节点是空，说明链表是空的，那么e就是头结点了
if ((e.prev = loTail) == null)
loHead = e;
//否则的话就插在尾节点后面
else
loTail.next = e;
//同时把尾节点指向e
loTail = e;
//低位节点数量+1
++lc;
}
//同上
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
//经过上面的遍历，红黑树成功被拆成高低位两个链表，但是这另个链表的长度不一定
//符合树化和反树化的要求，所以这里就进行判断；如果小于反树化的阈值，那么把链
//表中的红黑树节点TreeNode转化成普通节点Node；否则的话就把链表树化成红黑树
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
拆分红黑树其实和拆分链表的道理一样，还算是比较简单的，下面介绍最后一个重要方法，树化：treeifyBin(Node<K,V>[] tab, int hash)：
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
* 树化的第一步是将普通节点Node转化成红黑树节点
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果HashMap的容量没有达到MIN_TREEIFY_CAPACITY，那么优先选择扩容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
//下面就为树化做准备
else if ((e = tab[index = (n - 1) & hash]) != null) {
//申明头尾两个红黑树节点
TreeNode<K,V> hd = null, tl = null;
//往死里遍历链表
do {
//将普通节点Node转换成红黑树节点TreeNode，这个转换非常简单，
//就是根据Node创建一个TreeNode对象，注意最后一个参数next为空
TreeNode<K,V> p = replacementTreeNode(e, null);
//如果为节点是空，那么说明链表是空的，刚刚创建的红黑树节点p就是头结点
//注意，这里说的链表是空的，不是指待转换的链表，而是创建了一个新的链表
if (tl == null)
//将头节点指向p
hd = p;
else {
//如果尾节点不为空，那么将新建的红黑树节点插入链表尾部
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
//经过上面那一通折腾，原来的链表都变成一个全新的，连接红黑树节点的链
//表；这里就将新的链表放入桶中；然后调用头结点的treeify进行真正的树化
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
treeifyBin方法只是树化的一个热身步骤，最重要的是treeify方法：
/**
* Forms tree of the nodes linked from this node.
* 这里才是真正的树化过程
* @return root of tree
*/
final void treeify(Node<K,V>[] tab) {
//红黑树的根节点
TreeNode<K,V> root = null;
//遍历此链表，起点是调用treeify方法的节点，也就是链表的头结点
for (TreeNode<K,V> x = this, next; x != null; x = next) {
//给next赋值，代表的是当前遍历到的节点的后继节点
next = (TreeNode<K,V>)x.next;
//首先将当前的节点的左右子节点置空，只有当前节点的next节点才能确定左右子节点
x.left = x.right = null;
//如果根节点是空的话，首先要确定根节点
if (root == null) {
//根节点是没有父节点的，所以将parent置空
x.parent = null;
//根节点必须是黑色的
x.red = false;
//将当前节点赋值给根节点
root = x;
}
//下面就是在根节点的下面插入子节点
else {
//首先拿到链表节点的key
K k = x.key;
//拿到链表节点的hash值
int h = x.hash;
//key的类型信息
Class<?> kc = null;
//以根节点为起点遍历红黑树，确定链表节点应该插到红黑树的哪个地方
for (TreeNode<K,V> p = root;;) {
//dir是链表节点和红黑树中的节点的比较结果；ph是红黑树节点的hash值
int dir, ph;
//拿到红黑树节点的key值
K pk = p.key;
//如果红黑树节点的hash值比链表节点大，说明链表节点应该插在红黑树节点左边，dir == -1
if ((ph = p.hash) > h)
dir = -1;
//如果红黑树节点的hash值比链表节点大，说明链表节点应该插在红黑树节点左边，dir == -1
else if (ph < h)
dir = 1;
//如果链表节点和红黑树节点的hash值一样，但是两者有没有可比性，那么只能出
//绝招了，用tieBreakOrder比较两个对象的内存地址的hash；这个过程之前说过
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
//将红黑树节点赋值给xp，xp就会别当做父节点来使唤
TreeNode<K,V> xp = p;
//根据dir判断链表节点应该插在红黑树的左子节点还是右子节点
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
//插入后修复平衡，比较复杂，还没研究
root = balanceInsertion(root, x);
break;
}
}
}
}
//确保链表头节点是红黑树的根节点
moveRootToFront(tab, root);
}
可以看到，treeify本身不难，难的是修复红黑树平衡的方法balanceInsertion，这个方法没研究过，不敢妄言。
自此，HashMap的put方法研究的差不多了。
