江苏龙网

  1. 首页 > 人文 > >

详解HashMap集合( 五 )

TreeNodes占用空间是普通Nodes的两倍 ， 所以只有当bin包含足够多的节点时才会转成TreeNodes ， 而是否足够多就是由TREEIFY_THRESHOLD的值决定的 。 当bin中节点数变少时 ， 又会转成普通的bin 。 并且我们查看源码的时候发现 ， 链表长度达到8就转成红黑树 ， 当长度降到6就转成普通bin 。
这样就解释了为什么不是一开始就将其转换为TreeNodes ， 而是需要一定节点数才转为TreeNodes ， 说白了就是权衡 ， 空间和时间的权衡 。
这段内容还说到：当hashCode离散性很好的时候 ， 树型bin用到的概率非常小 ， 因为数据均匀分布在每个bin中 ， 几乎不会有bin中链表长度会达到阈值 。 但是在随机hashCode下 ， 离散性可能会变差 ， 然而JDK又不能阻止用户实现这种不好的hash算法 ， 因此就可能导致不均匀的数据分布 。 不过理想情况下随机hashCode算法下所有bin中节点的分布频率会遵循泊松分布 ， 我们可以看到 ， 一个bin中链表长度达到8个元素的概率为0.00000006 ， 几乎是不可能事件 。 所以 ， 之所以选择8 ， 不是随便决定的 ， 而是根据概率统计决定的 。 由此可见 ， 发展将近30年的Java每一项改动和优化都是非常严谨和科学的 。
也就是说：选择8因为符合泊松分布 ， 超过8的时候 ， 概率已经非常小了 ， 所以我们选择8这个数字 。
补充：
1）.
Poisson分布(泊松分布) ， 是一种统计与概率学里常见到的离散[概率分布] 。 泊松分布的概率函数为： 泊松分布的参数λ是单位时间(或单位面积)内随机事件的平均发生次数 。泊松分布适合于描述单位时间内随机事件发生的次数 。 2）.以下是我在研究这个问题时 ， 在一些资料上面翻看的解释：供大家参考：
红黑树的平均查找长度是log(n) ， 如果长度为8 ， 平均查找长度为log(8)=3 ， 链表的平均查找长度为n/2 ， 当长度为8时 ， 平均查找长度为8/2=4 ， 这才有转换成树的必要；链表长度如果是小于等于6 ， 6/2=3 ， 而log(6)=2.6 ， 虽然速度也很快的 ， 但是转化为树结构和生成树的时间并不会太短 。 6.当链表的值小于6则会从红黑树转回链表
//当桶(bucket)上的结点数小于这个值时树转链表 static final int UNTREEIFY_THRESHOLD = 6;7.当Map里面的数量超过这个值时 ， 表中的桶才能进行树形化， 否则桶内元素太多时会扩容 ， 而不是树形化 为了避免进行扩容、树形化选择的冲突 ， 这个值不能小于 4 * TREEIFY_THRESHOLD (8)
//桶中结构转化为红黑树对应的数组长度最小的值 static final int MIN_TREEIFY_CAPACITY = 64;8、table用来初始化(必须是二的n次幂)(重点)
//存储元素的数组 transient Node[] table;table在JDK1.8中我们了解到HashMap是由数组加链表加红黑树来组成的结构其中table就是HashMap中的数组 ， jdk8之前数组类型是Entry类型 。 从jdk1.8之后是Node类型 。 只是换了个名字 ， 都实现了一样的接口：Map.Entry 。 负责存储键值对数据的 。
9、用来存放缓存
//存放具体元素的集合transient Set> entrySet;10、 HashMap中存放元素的个数(重点)
//存放元素的个数 ， 注意这个不等于数组的长度 。transient int size;size为HashMap中K-V的实时数量 ， 不是数组table的长度 。
11、 用来记录HashMap的修改次数
// 每次扩容和更改map结构的计数器 transient int modCount;12、 用来调整大小下一个容量的值计算方式为(容量*负载因子)
// 临界值 当实际大小(容量*负载因子)超过临界值时 ， 会进行扩容int threshold;


推荐阅读


上一篇：正确使用#include语句的双引号形式和角括号形式

下一篇：带你揭开BFC的神秘面纱