HashMap
- HashMap集合底层的数据结构
- 在JDK1.7，HashMap由数组+链表数据结构组成。
- 在JDK1.8，HashMap由数组+链表+红黑树数据结构组成。
- HasMap<String, String> map = new HashMap<>();
在创建HashMap集合对象的时候，在Jdk8之前， 构造方法中创建一个长度为16的Entry[] table用来存储键值对数据。在jdk8之后不是在HashMap的构造方法底层创建数组，是在第一次调用put方法时创建的数组，Node[] table 本质依然是Map.Entry类型。 - 哈希表底层采用何种算法计算hash值？还有哪些算法可以计算出hash值？
底层采用的key的hashCode()方法的值结合数组长度进行无符号右移(>>>)、按位异或（^）、按位与（&）计算出索引。
还可以采用：取余法、伪随机数法、平方取中法。 - 如果节点长度即链表长度大于阈值8并且数组长度大于等于64则链表变为红黑树。
- 当两个对象的hashCode相等时会怎么样？
会产生哈希碰撞，若key值内容相同，则替换旧的value，不然连接到链表后面，链表长度超过阈值8就转换为红黑树存储。 - 在不断添加数据的过程中，会涉及到扩容的问题。当超出临界值（且要存放的位置非空）时，扩容，默认的扩容方式：扩容为原来容量的2倍，并将原有的数据复制过来。
- 默认负载因子为0.75（兼顾数组利用率又考虑链表不要太多）。集合最大容量的上限是：2的30次幂。
- 为什么阈值设定为8
因为树节点的大小大约是普通节点的两倍，所以桶中包含足够的节点时才使用树节点。当他们变得太小（由于删除或调整大小）时，就会被转换为普通的桶，在使用分布良好的用户hashcode时，很少使用树。理想情况下，节点的频率服从泊松分布。
 - 当链表值小于6则会从红黑树转回链表
- 上面代码是HashMap::put的核心实现, HashMap会在两个地方进行resize(扩容):
1 HashMap实行了懒加载, 新建HashMap时不会对table进行赋值, 而是到第一次插入时, 进行resize时构建table;
2 当HashMap.size 大于 threshold时, 会进行resize;threshold的值我们在上一次分享中提到过: 当第一次构建时, 如果没有指定HashMap.table的初始长度, 就用默认值16, 否则就是指定的值; 然后不管是第一次构建还是后续扩容, threshold = table.length * loadFactor; - 第一次添加元素的时候，默认初期长度为16，当往map中继续添加元素的时候，通过hash值跟数组长度取“与”来决定放在数组的哪个位置，如果出现放在同一个位置的时候，优先以链表的形式存放，在同一个位置的个数又达到了8个（代码是>=7,从0开始，及第8个开始判断是否转化成红黑树），如果数组的长度还小于64的时候，则会扩容数组。如果数组的长度大于等于64的话，才会将该节点的链表转换成树。在扩容完成之后，如果某个节点的是树，同时现在该节点的个数又小于等于6个了，则会将该树转为链表。
- 扩容条件： if ((size = threshold) && (null != table[bucketIndex])) {resize(2 * table.length);//数组长度变为原来两倍}
- 为什么HashMap以2的幂次方扩容？
- h%n == h & (n-1) 增加运算速度 （位与(&)运算符比%运算速度快很多， 还有因为扩容是2的倍数，根据位与（&）运算，元素hash值不变，而通过%运算，因为n的变化，计算出来的hash桶的位置不断变化，数据一致在漂移，影响性能。）
- 使hash分布更均匀，减少冲突。（假设数组的长度n可能为偶数也可能为奇数，当n为偶数是，n-1为奇数，奇数的二进制最后一位是1，和hash位与运算后，既可能为奇数1，也可能为偶数0， 保证了散列的均匀性。而如果为n为奇数，浪费了近一半的空间）
- 扩容时仅需要多比较1个bit（ if ((e.hash & oldCap) == 0) { 重点
newTab[j + oldCap] = hiHead;重点） - 扩容迁移时，仅有一半的数据要迁移，减少迁移成本。
拼多多集团-PDD公司氛围 515人发布