推荐一个咕泡学院的视频资源:链接:https://pan.baidu.com/s/1SmSzrmfgbm6XgKZO7utKWg 密码:e54x
先回答一下之前发布的《使用HashMap的时候小心点》同学不补充的问题,说最好说下HashMap在JDK8下是怎么解决死循环的问题的。
链表部分对应上面 transfer 的代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 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; }
由于扩容是按两倍进行扩,即 N 扩为 N + N,因此就会存在低位部分 0 - (N-1),以及高位部分 N - (2N-1), 所以这里分为 loHead (low Head) 和 hiHead (high head)。
通过上面的分析,不难发现循环的产生是因为新链表的顺序跟旧的链表是完全相反的,所以只要保证建新链时还是按照原来的顺序的话就不会产生循环。
JDK8是用 head
和 tail
来保证链表的顺序和之前一样,这样就不会产生循环引用。
传统 HashMap 的缺点 JDK 1.8 以前 HashMap 的实现是 数组+链表,即使哈希函数取得再好,也很难达到元素百分百均匀分布。
当 HashMap 中有大量的元素都存放到同一个桶中时,这个桶下有一条长长的链表,这个时候 HashMap 就相当于一个单链表,假如单链表有 n 个元素,遍历的时间复杂度就是 O(n),完全失去了它的优势。
针对这种情况,JDK 1.8 中引入了 红黑树(查找时间复杂度为 O(logn))来优化这个问题。
新增的数据结构 – 红黑树
JDK 1.8 中 HashMap 中除了链表节点:
1 2 3 4 5 6 7 8 9 10 11 static class Node implements Map .Entry { final int hash; final K key; V value; Node next; }
还有另外一种节点:TreeNode,它是 1.8 新增的,属于数据结构中的 红黑树 (不了解红黑树的同学可以 点击这里了解红黑树 ):
1 2 3 4 5 6 7 static final class TreeNode extends LinkedHashMap .Entry { TreeNode parent; TreeNode left; TreeNode right; TreeNode prev; boolean red; }
可以看到就是个红黑树节点,有父亲、左右孩子、前一个元素的节点,还有个颜色值。
另外由于它继承自 LinkedHashMap.Entry ,而 LinkedHashMap.Entry 继承自 HashMap.Node ,因此还有额外的 6 个属性:
1 2 3 4 5 6 7 8 Entry before, after; final int hash;final K key;V value; Node next;
红黑树的三个关键参数 HashMap 中有三个关于红黑树的关键参数:
TREEIFY_THRESHOLD
UNTREEIFY_THRESHOLD
MIN_TREEIFY_CAPACITY
值及作用如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 static final int TREEIFY_THRESHOLD = 8 ;static final int UNTREEIFY_THRESHOLD = 6 ;static final int MIN_TREEIFY_CAPACITY = 64 ;
新增的操作:桶的树形化 treeifyBin() 在Java 8 中,如果一个桶中的元素个数超过 TREEIFY_THRESHOLD(默认是 8 ),就使用红黑树来替换链表,从而提高速度。
这个替换的方法叫 treeifyBin() 即树形化。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 final void treeifyBin (Node[] tab, int hash) { int n, index; Node e; if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1 ) & hash]) != null ) { TreeNode hd = null , tl = null ; do { TreeNode p = replacementTreeNode(e, null ); if (tl == null ) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null ); if ((tab[index] = hd) != null ) hd.treeify(tab); } } TreeNode replacementTreeNode (Node p, Node next) { return new TreeNode <>(p.hash, p.key, p.value, next); }
上述操作做了这些事:
根据哈希表中元素个数确定是扩容还是树形化
如果是树形化
遍历桶中的元素,创建相同个数的树形节点,复制内容,建立起联系
然后让桶第一个元素指向新建的树头结点,替换桶的链表内容为树形内容
但是我们发现,之前的操作并没有设置红黑树的颜色值,现在得到的只能算是个二叉树。在 最后调用树形节点 hd.treeify(tab) 方法进行塑造红黑树,来看看代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 final void treeify (Node[] tab) { TreeNode root = null ; for (TreeNode x = this , next; x != null ; x = next) { next = (TreeNode)x.next; x.left = x.right = null ; if (root == null ) { x.parent = null ; x.red = false ; root = x; } else { K k = x.key; int h = x.hash; Class kc = null ; for (TreeNode p = root;;) { int dir, ph; K pk = p.key; if ((ph = p.hash) > h) dir = -1 ; else if (ph < h) dir = 1 ; else if ((kc == null && (kc = comparableClassFor(k)) == null ) || (dir = compareComparables(kc, k, pk)) == 0 ) dir = tieBreakOrder(k, pk); TreeNode xp = p; 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); }
可以看到,将二叉树变为红黑树时,需要保证有序。这里有个双重循环,拿树中的所有节点和当前节点的哈希值进行对比(如果哈希值相等,就对比键,这里不用完全有序),然后根据比较结果确定在树种的位置。
新增的操作: 红黑树中添加元素 putTreeVal() 上面介绍了如何把一个桶中的链表结构变成红黑树结构。
在添加时,如果一个桶中已经是红黑树结构,就要调用红黑树的添加元素方法 putTreeVal()。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 final TreeNode putTreeVal (HashMap map, Node[] tab, int h, K k, V v) { Class kc = null ; boolean searched = false ; TreeNode root = (parent != null ) ? root() : this ; for (TreeNode p = root;;) { int dir, ph; K pk; if ((ph = p.hash) > h) dir = -1 ; else if (ph < h) dir = 1 ; else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p; else if ((kc == null && (kc = comparableClassFor(k)) == null ) || (dir = compareComparables(kc, k, pk)) == 0 ) { if (!searched) { TreeNode 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 xp = p; if ((p = (dir <= 0 ) ? p.left : p.right) == null ) { Node xpn = xp.next; TreeNode 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)xpn).prev = x; moveRootToFront(tab, balanceInsertion(root, x)); return null ; } } } static int tieBreakOrder (Object a, Object b) { int d; if (a == null || b == null || (d = a.getClass().getName(). compareTo(b.getClass().getName())) == 0 ) d = (System.identityHashCode(a) <= System.identityHashCode(b) ? -1 : 1 ); return d; }
通过上面的代码可以知道,HashMap 中往红黑树中添加一个新节点 n 时,有以下操作:
从根节点开始遍历当前红黑树中的元素 p,对比 n 和 p 的哈希值;
如果哈希值相等并且键也相等,就判断为已经有这个元素(这里不清楚为什么不对比值);
如果哈希值就通过其他信息,比如引用地址来给个大概比较结果,这里可以看到红黑树的比较并不是很准确,注释里也说了,只是保证个相对平衡即可;
最后得到哈希值比较结果后,如果当前节点 p 还没有左孩子或者右孩子时才能插入,否则就进入下一轮循环;
插入元素后还需要进行红黑树例行的平衡调整,还有确保根节点的领先地位。
新增的操作: 红黑树中查找元素 getTreeNode() HashMap 的查找方法是 get():
1 2 3 4 public V get (Object key) { Node e; return (e = getNode(hash(key), key)) == null ? null : e.value; }
它通过计算指定 key 的哈希值后,调用内部方法 getNode();
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 final Node getNode (int hash, Object key) { Node[] tab; Node first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1 ) & hash]) != null ) { if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null ) { if (first instanceof TreeNode) return ((TreeNode)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 ; }
这个 getNode() 方法就是根据哈希表元素个数与哈希值求模(使用的公式是 (n - 1) &hash
)得到 key 所在的桶的头结点,如果头节点恰好是红黑树节点,就调用红黑树节点的 getTreeNode() 方法,否则就遍历链表节点。
1 2 3 final TreeNode getTreeNode (int h, Object k) { return ((parent != null ) ? root() : this ).find(h, k, null ); }
getTreeNode 方法使通过调用树形节点的 find() 方法进行查找:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 final TreeNode find (int h, Object k, Class kc) { TreeNode p = this ; do { int ph, dir; K pk; TreeNode pl = p.left, pr = p.right, q; if ((ph = p.hash) > h) p = pl; else if (ph < h) p = pr; else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p; else if (pl == null ) p = pr; else if (pr == null ) p = pl; else if ((kc != null || (kc = comparableClassFor(k)) != null ) && (dir = compareComparables(kc, k, pk)) != 0 ) p = (dir < 0 ) ? pl : pr; else if ((q = pr.find(h, k, kc)) != null ) return q; else p = pl; } while (p != null ); return null ; }
由于之前添加时已经保证这个树是有序的,因此查找时基本就是折半查找,效率很高。
这里和插入时一样,如果对比节点的哈希值和要查找的哈希值相等,就会判断 key 是否相等,相等就直接返回(也没有判断值哎);不相等就从子树中递归查找。
新增的操作: 树形结构修剪 split() HashMap 中, resize() 方法的作用就是初始化或者扩容哈希表。当扩容时,如果当前桶中元素结构是红黑树,并且元素个数小于链表还原阈值 UNTREEIFY_THRESHOLD (默认为 6),就会把桶中的树形结构缩小或者直接还原(切分)为链表结构,调用的就是 split():
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 final void split (HashMap map, Node[] tab, int index, int bit) { TreeNode b = this ; TreeNode loHead = null , loTail = null ; TreeNode hiHead = null , hiTail = null ; int lc = 0 , hc = 0 ; for (TreeNode e = b, next; e != null ; e = next) { next = (TreeNode)e.next; e.next = null ; if ((e.hash & bit) == 0 ) { if ((e.prev = loTail) == null ) loHead = e; else loTail.next = e; loTail = e; ++lc; } else { if ((e.prev = hiTail) == null ) hiHead = e; else hiTail.next = e; hiTail = e; ++hc; } } if (loHead != null ) { if (lc <= UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map); else { tab[index] = loHead; if (hiHead != null ) 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); } } }
从上述代码可以看到,HashMap 扩容时对红黑树节点的修剪主要分两部分,先分类、再根据元素个数决定是还原成链表还是精简一下元素仍保留红黑树结构。
1.分类
指定位置、指定范围,让指定位置中的元素 (hash & bit) == 0
的,放到 lXXX 树中,不相等的放到 hXXX 树中。
2.根据元素个数决定处理情况
符合要求的元素(即 lXXX 树),在元素个数小于 6 时还原成链表,最后让哈希表中修剪的痛 tab[index] 指向 lXXX 树;在元素个数大于 6 时,还是用红黑树,只不过是修剪了下枝叶;
不符合要求的元素(即 hXXX 树)也是一样的操作,只不过最后它是放在了修剪范围外 tab[index + bit]。
总结 JDK 1.8 以后哈希表的 添加、删除、查找、扩容方法都增加了一种 节点为 TreeNode 的情况:
添加时,当桶中链表个数超过 8 时会转换成红黑树;
删除、扩容时,如果桶中结构为红黑树,并且树中元素个数太少的话,会进行修剪或者直接还原成链表结构;
查找时即使哈希函数不优,大量元素集中在一个桶中,由于有红黑树结构,性能也不会差。
(图片来自:tech.meituan.com/java-hashma… )
这篇文章根据源码分析了 HashMap 在 JDK 1.8 里新增的 TreeNode 的一些关键方法,可以看到,1.8 以后的 HashMap 结合了哈希表和红黑树的优点,不仅快速,而且在极端情况也能保证性能,设计者苦心孤诣可见一斑,写到这里不禁仰天长叹:什么时候我才能写出这么 NB 的代码啊!!!
参考地址