Java源码解析|HashMap的前世今生 (3)

扩容后拷贝原来的table，像java1.7的transfer函数，java1.8中保持顺序复制，线程仍然不安全

扩容时的高低位链表 不太懂。

resize效率低，需要拷贝，所以初始化时最好指定一定的容量，避免频繁扩容带来的性能问题。

put插入方法

HashMap新增结点步骤如下：

put的部分代码如下

// 入参 hash：通过 hash 算法计算出来的值。 // 入参 onlyIfAbsent：false 表示即使 key 已经存在了，仍然会用新值覆盖原来的值，默认为 false final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { // n 表示数组的长度，i 为数组索引下标，p 为 i 下标位置的 Node 值 Node<K,V>[] tab; Node<K,V> p; int n, i; //如果数组为空，使用 resize 方法初始化 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); // 如果当前索引位置有值的处理方法，即我们常说的如何解决 hash 冲突 else { // e 当前节点的临时变量 Node<K,V> e; K k; // 如果 key 的 hash 和值都相等，直接把当前下标位置的 Node 值赋值给临时变量 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) { // e = p.next 表示从头开始，遍历链表 // p.next == null 表明 p 是链表的尾节点 if ((e = p.next) == null) { // 把新节点放到链表的尾部 p.next = newNode(hash, key, value, null); // 当链表的长度大于等于 8 时，链表转红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash);//树化 break; } // 链表遍历过程中，发现有元素和新增的元素相等，结束循环 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; //更改循环的当前元素，使 p 在遍历过程中，一直往后移动。 p = e; } } // 说明新节点的新增位置已经找到了 if (e != null) { V oldValue = e.value; // 当 onlyIfAbsent 为 false 时，才会覆盖值 if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); // 返回老值 return oldValue; } } // 记录 HashMap 的数据结构发生了变化 ++modCount; //如果 HashMap 的实际大小大于扩容的门槛，开始扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }

如果数组有了key，但不想覆盖 value，可以选择putlfAbsent方法，这个方法有个内置变量onlylfAbsent，内置是true，就不会覆盖，我们平时使用的put方法，内置onlylfAbsent为false，是允许覆盖的。

链表新增结点：把新结点添加到链表尾部就行了。

红黑树新增结点步骤如下

//入参 h：key 的hash值 final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) { Class<?> kc = null; boolean searched = false; //找到根节点 TreeNode<K,V> root = (parent != null) ? root() : this; //自旋 for (TreeNode<K,V> p = root;;) { int dir, ph; K pk; // p hash 值大于 h，说明 p 在 h 的右边 if ((ph = p.hash) > h) dir = -1; // p hash 值小于 h，说明 p 在 h 的左边 else if (ph < h) dir = 1; //要放进去key在当前树中已经存在了(equals来判断) else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p; //自己实现的Comparable的话，不能用hashcode比较了，需要用compareTo else if ((kc == null && //得到key的Class类型，如果key没有实现Comparable就是null (kc = comparableClassFor(k)) == null) || //当前节点pk和入参k不等 (dir = compareComparables(kc, k, pk)) == 0) { if (!searched) { TreeNode<K,V> q, ch; searched = true; 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; } dir = tieBreakOrder(k, pk); } TreeNode<K,V> xp = p; //找到和当前hashcode值相近的节点(当前节点的左右子节点其中一个为空即可) if ((p = (dir <= 0) ? p.left : p.right) == null) { Node<K,V> xpn = xp.next; //生成新的节点 TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); //把新节点放在当前子节点为空的位置上 if (dir <= 0) xp.left = x; else xp.right = x; //当前节点和新节点建立父子，前后关系 xp.next = x; x.parent = x.prev = xp; if (xpn != null) ((TreeNode<K,V>)xpn).prev = x; //balanceInsertion 对红黑树进行着色或旋转，以达到更多的查找效率，着色或旋转的几种场景如下 //着色：新节点总是为红色；如果新节点的父亲是黑色，则不需要重新着色；如果父亲是红色，那么必须通过重新着色或者旋转的方法，再次达到红黑树的5个约束条件 //旋转： 父亲是红色，叔叔是黑色时，进行旋转 //如果当前节点是父亲的右节点，则进行左旋 //如果当前节点是父亲的左节点，则进行右旋 //moveRootToFront 方法是把算出来的root放到根节点上 moveRootToFront(tab, balanceInsertion(root, x)); return null; } } }

有关红黑树还需要补充知识点(占坑)

get查找方法