详解HashMap集合( 四 )
注意 ， 这个n已经经过了n |= n >>> 1; 操作 。 假设此时n为00000000 00000000 00000000 00001101， 则n无符号右移两位 ， 会将最高位两个连续的1右移两位 ， 然后再与原来的n做或操作 ， 这样n的二进制表示的高位中会有4个连续的1 。 如：
00000000 00000000 00000000 00001111 //按位异或之后是15第三次右移 :
n |= n >>> 4;//n通过第一、二次右移变为了：n=1500000000 00000000 00000000 00001111// 15|00000000 00000000 00000000 00000000//15右移之后变为0-------------------------------------------------00000000 00000000 00000000 00001111 //按位异或之后是15这次把已经有的高位中的连续的4个1 ， 右移4位 ， 再做或操作 ， 这样n的二进制表示的高位中正常会有8个连续的1 。 如00001111 1111xxxxxx。以此类推 注意 ， 容量最大也就是32bit的正数 ， 因此最后n |= n >>> 16;， 最多也就32个1（但是这已经是负数了 。 在执行tableSizeFor之前 ， 对initialCapacity做了判断 ， 如果大于MAXIMUM_CAPACITY(2 ^ 30) ， 则取MAXIMUM_CAPACITY 。 如果等于MAXIMUM_CAPACITY(2 ^ 30) ， 会执行移位操作 。 所以这里面的移位操作之后 ， 最大30个1 ， 不会大于等于MAXIMUM_CAPACITY 。 30个1 ， 加1之后得2 ^ 30）。请看下面的一个完整例子：
注意 ， 得到的这个capacity却被赋值给了threshold 。
this.threshold = tableSizeFor(initialCapacity);//initialCapacity=103.默认的负载因子 ， 默认值是0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;4.集合最大容量
//集合最大容量的上限是：2的30次幂static final int MAXIMUM_CAPACITY = 1 << 30;5.当链表的值超过8则会转红黑树(1.8新增)
//当桶(bucket)上的结点数大于这个值时会转成红黑树 static final int TREEIFY_THRESHOLD = 8;问题：为什么Map桶中节点个数超过8才转为红黑树？
【详解HashMap集合】8这个阈值定义在HashMap中 ， 针对这个成员变量 ， 在源码的注释中只说明了8是bin（bin就是bucket(桶)）从链表转成树的阈值 ， 但是并没有说明为什么是8：
在HashMap中有一段注释说明： 我们继续往下看 :
Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins.In usages with well-distributed user hashCodes, tree bins are rarely used.Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution() with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5)*pow(0.5, k)/factorial(k)).The first values are:因为树节点的大小大约是普通节点的两倍 ， 所以我们只在箱子包含足够的节点时才使用树节点(参见TREEIFY_THRESHOLD) 。 当它们变得太小(由于删除或调整大小)时 ， 就会被转换回普通的桶 。 在使用分布良好的用户hashcode时 ， 很少使用树箱 。 理想情况下 ， 在随机哈希码下 ， 箱子中节点的频率服从泊松分布() ， 默认调整阈值为0.75 ， 平均参数约为0.5 ， 尽管由于调整粒度的差异很大 。 忽略方差 ， 列表大小k的预期出现次数是(exp(-0.5)*pow(0.5, k)/factorial(k)) 。 第一个值是:0:0.606530661:0.303265332:0.075816333:0.012636064:0.001579525:0.000157956:0.000013167:0.000000948:0.00000006more: less than 1 in ten million
推荐阅读
- 极速鲨课堂85：显卡怎么测试 3DMARK详解
- 性能翻倍！飞腾首款8核桌面处理器腾锐D2000详解
- 详解工程师不可不会的LRU缓存淘汰算法
- 网速再翻倍，官方详解小米 11 搭载的 WiFi 6 增强版技术
- leetcode之错误的集合
- 苹果指南详解如果隐私受到威胁，如何锁定iPhone
- 小米多看电纸书Pro详解：1099元值不值得买？
- 电动汽车「换电问题」详解：更换电池是否为新电池呢？
- 安卓面试必备的JVM虚拟机制详解，看完之后简历上多一个技能
- 新能源出租车驶入包头，运管部门详解换新热点问题