← 返回目录

JDK1.8 之后

第 4 / 16 卷日期:

转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树)时,将链表转化为红黑树,以减少搜索时间。

图 5-1
图 5-1

TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底层都用到了红黑树。红黑树就是为了解决二叉查找树的缺陷,因为二叉查找树在某些情况下会退化成一个线性结构。

我们来结合源码分析一下 HashMap 链表到红黑树的转换。

  1. putVal 方法中执行链表转红黑树的判断逻辑。

链表的长度大于 8 的时候,就执行 treeifyBin(转换红黑树)的逻辑。

// 遍历链表

for (int binCount = 0; ; ++binCount) {

// 遍历到链表最后一个节点

if ((e = p.next) == null) {

p.next = newNode(hash, key, value, null);

// 如果链表元素个数大于等于TREEIFY_THRESHOLD(8)

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st

// 红黑树转换(并不会直接转换成红黑树)

if (e.hash == hash &&

((k = e.key) == key || (key != null && key.equals(k))))

break;

p = e;

}

  1. treeifyBin 方法中判断是否真的转换为红黑树。

final void treeifyBin(Node<K,V>[] tab, int hash) {

int n, index; Node<K,V> e;

// 判断当前数组的长度是否小于 64

if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)

// 如果当前数组的长度小于 64,那么会选择先进行数组扩容

resize();

else if ((e = tab[index = (n - 1) & hash]) != null) {

// 否则才将列表转换为红黑树

TreeNode<K,V> hd = null, tl = null;

do {

TreeNode<K,V> 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);

}

}

将链表转换成红黑树前会判断,如果当前数组的长度小于 64,那么会选择先进行数组扩容,而不是转换为红黑树。

全站分卷索引 · 16 卷
  1. 1Java 基础篇
  2. 2反射的应用场景
  3. 3HashMap 源码实现,链表转红黑树条件,红黑树是否会退化为链表
  4. 4JDK1.8 之后
  5. 5ConcurrentHashMap 的底层实现
  6. 6JDK1.8 之后
  7. 7简述 CAS
  8. 8乐观锁和悲观锁
  9. 9什么是乐观锁?
  10. 10Java 线程池的几个参数以及其具体意义
  11. 11线程池的拒绝策略
  12. 12描述线程池的执行过程
  13. 13JVM 篇
  14. 14复制算法
  15. 15标记-整理算法
  16. 16简述类加载过程