您现在的位置是:主页 > 数据库技术 > 数据库技术

Map桶中超过8个才转为红黑树的原因是什么

IDCBT2021-12-31服务器技术人已围观

简介本篇内容主要讲解“Map桶中超过8个才转为红黑树的原因是什么”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“Map桶中超过8个才转

本篇内容主要讲解“Map桶中超过8个才转为红黑树的原因是什么”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“Map桶中超过8个才转为红黑树的原因是什么”吧!

JDK 1.8 的 HashMap 和 ConcurrentHashMap 都有这样一个特点:最开始的 Map 是空的,因为里面没有任何元素,往里放元素时会计算 hash 值,计算之后,第 1 个 value 会首先占用一个桶(也称为槽点)位置,后续如果经过计算发现需要落到同一个桶中,那么便会使用链表的形式往后延长,俗称“拉链法”,如图所示:

当链表长度大于或等于阈值(默认为 8)的时候,如果同时还满足容量大于或等于 MIN_TREEIFY_CAPACITY(默认为 64)的要求,就会把链表转换为红黑树。同样,后续如果由于删除或者其他原因调整了大小,当红黑树的节点小于或等于 6 个以后,又会恢复为链表形态。如下图:

在图中我们可以看到,有一些槽点是空的,有一些是拉链,有一些是红黑树。

那么为什么转化的这个阈值要默认设置为 8 呢?

    那首先我们就要知道为什么要转换,因为转换是第一步。

    每次遍历一个链表,平均查找的时间复杂度是 O(n),n 是链表的长度。红黑树有和链表不一样的查找性能,由于红黑树有自平衡的特点,可以防止不平衡情况的发生,所以可以始终将查找的时间复杂度控制在 O(log(n))。最初链表还不是很长,所以可能 O(n) 和 O(log(n)) 的区别不大,但是如果链表越来越长,那么这种区别便会有所体现。所以为了提升查找性能,需要把链表转化为红黑树的形式。

      那为什么不一开始就用红黑树,反而要经历一个转换的过程呢?

      在 JDK 的源码注释中已经对这个问题作了解释:

      Because TreeNodes are about twice the size of regular nodes,
      use them only when bins contain enough nodes to warrant use
      (see TREEIFY_THRESHOLD). And when they become too small (due 
      removal or resizing) they are converted back to plain bins.

      这段话的意思是:单个 TreeNode 需要占用的空间大约是普通 Node 的两倍,所以只有当包含足够多的 Nodes 时才会转成 TreeNodes,而是否足够多就是由 TREEIFY_THRESHOLD 的值决定的。而当桶中节点数由于移除或者 resize 变少后,又会变回普通的链表的形式,以便节省空间。

      通过查看源码可以发现,默认是链表长度达到 8 就转成红黑树,而当长度降到 6 就转换回去,这体现了时间和空间平衡的思想,最开始使用链表的时候,空间占用是比较少的,而且由于链表短,所以查询时间也没有太大的问题。可是当链表越来越长,需要用红黑树的形式来保证查询的效率。对于何时应该从链表转化为红黑树,需要确定一个阈值,这个阈值默认为 8,并且在源码中也对选择 8 这个数字做了说明,原文如下:

      标签:

      很赞哦! ()

本栏推荐