hashMap源码分析1.8

今天药忘吃喽~ 2022-03-29 03:28 189阅读 0赞

# HashMap #

*  JDK1.8的HashMap：底层实现（数组+链表/红黑树）
 *  
 *  1、为什么要从JDK1.8之前的链表设计，修改为链表或红黑树的设计？
 *  当某个链表比较长的时候，查找效率还是会降低。
 *  为了提高查询效率，那么把table\[index\]下面的链表做调整。
 *  如果table\[index\]的链表的节点的个数比较少，（8个或以内），就保持链表。如果超过8个，那么就要考虑把链表转为一棵红黑树。
 *  TREEIFY\_THRESHOLD：树化阈值，从链表转为红黑树的临界值。
 *  
 *  2、什么时候树化？
 *  table\[index\]下的结点数一达到8个就树化吗？
 *  如果table\[index\]的节点数量已经达到8个了，还要判断table.length是否达到64，如果没有达到64，先扩容。
 *  
 *  演示：8个->9个 length从16-》32
 *      9个->10个  length从32->64
 *      10个->11个 length已经达到64，table[index]就从Node类型转为TreeNode类型，说明树化
 *  
 *  MIN\_TREEIFY\_CAPACITY：最小树化容量64
 *  
 *  3、什么时候从树–>链表
 *  当你删除结点时，这棵树的结点个数少于6个，会反树化，变为链表
 *  UNTREEIFY\_THRESHOLD：6个
 *  
 *  树的结构太复杂，当结点少了之后，就用链表更好。
 *  
 *  4、put的过程
 *  （1）\[index\]的计算问题
 *  第一步用key的hashCode值调用hash()函数，干扰hash值，使得(key,value)更加均匀的分布table数组中。
 *  JDK1.8中hash()算法更优化。
 *  
 *  第二步： hash值与table.length-1做&运算，保证index在\[0,length-1\]范围内
 *  
 *  （2）扩容问题
 *  第一种：当某个table\[index\]的链表的个数达到8个，并且table.length<64，那么会扩容
 *  第二种：size >= threshold，并且table\[index\]!=null
 *  threshold = table.length \* loadFator（它的默认值DEFAULT\_LOAD\_FACTOR：0.75）
 *  
 *  （3）当把(key,value)添加到链表中，JDK1.8是在链表的尾部