meta|Java集合面试题看这篇就够了( 六 ) 市值|创投圈|手机行业

0.00000006 。树化阈值选择 8 就是为了让树化几率足够小
???面试官继续追问：那为什么不一开始直接使用红黑树？

当链表数据量少的时候，遍历线性链表比遍历红黑树消耗的资源少 (因为少量数据，红黑树本身自选、变色保持平衡也是需要消耗资源的) ，所以前期使用线性表。
然后TreeNode 占用空间也比普通 Node 的大，如非必要，尽量还是使用链表

19.HashMap扩容（加载）因子为何默认是 0.75f？

在空间占用与查询时间之间取得较好的权衡
大于这个值，空间节省了，但链表就会比较长影响性能
小于这个值，冲突减少了，但扩容就会更频繁，空间占用也更多

20.HashMap怎么计算 key 的 hash 值的？我们先看源码：
static final int hash(Object key) {
int h;
//key==null直接返回0
//1、否则调用key的hashCode()方法计算出key的哈希值然后赋值给h
//2、h >>> 16 。后与h无符号右移16位后的二进制进行按位异或得到最后的hash值
//3、这样做是为了使计算出的hash更分散，让高16位可以参与（低16位具有高16位的特征）
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

可以看出：

首先，计算对象的 hashCode()
然后将 key 的 hashCode 的高 16 位和 hashCode 低 16 位进行异或（XOR）运算，最终得到新的 hash 值。二次 hash() 是为了综合高位数据，让哈希分布更为均匀

关于第二点，这里举个例子就知道了：
我们知道， HashMap 新插入的数据需要经过寻址算法 index = hash & (tab.length - 1) 来确定桶位下标。 tab.length就是数组长度，我们这里设其为 n 。
如果当 n 即数组长度很小，假设是 n = 16 的话，那么 n - 1 是 15，其二进制数为 1111，这样的值和 hashCode 直接做按位与操作，实际上只使用了哈希值的后 4 位。如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了，所以这里把高低位都利用起来，从而解决了这个问题
我们来看一个分析图：

由上图，可以知道如果只使用 key.hashCode()方法计算得到的 hash 值，那么当 hash 值高位变化较大，而低位变化较小时，通过寻址算法 hash & (tab.length - 1) 得到的桶位下标 index 就更容易出现 hash 冲突了！
21.HashMap是怎么解决哈希冲突的？哈希冲突：hashMap在存储元素时会先计算key的hash值来确定存储位置，因为key的hash值计算最后有个对数组长度取余的操作，所以即使不同的key也可能计算出相同的hash值，这样就引起了hash冲突。 hashMap的底层结构中的链表/红黑树就是用来解决这个问题的。
HashMap中的哈希冲突解决方式可以主要从三方面考虑（以JDK1.8为背景)

拉链法
\tHasMap中的数据结构为数组+链表/红黑树，当不同的key计算出的hash值相同时，就用链表的形式将Node结点（冲突的key及key对应的value)挂在数组后面。
hash函数
\tkey的hash值经过两次扰动，key的hashcode值与key的hashcode值的右移16位进行异或，然后对数组的长度取余（实际为了提高性能用的是位运算，但目的和取余一样) ，这样做可以让hashcode取值出的高位也参与运算，进一步降低hash冲突的概率，使得数据分布更平均。
红黑树
- 上一页
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 下一页