JDK1.8HashMap源码分析

上一篇 <<<Jdk1.7HashMap如何扩容及解决死循环问题
下一篇 >>>

---

JDK1.8的HashMap的底层结构：是由数组+链表+红黑树构成的。

核心参数常量

###HashMap默认初始容量16(扩容速度：原始容量的2倍速度)
1.static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
###HashMap限制最大容量1073741824
2.static final int MAXIMUM_CAPACITY = 1 << 30;
###加载因子0.75f 16*0.75=12 提前扩容
3. static final float DEFAULT_LOAD_FACTOR = 0.75f;
##链表长度如果大于8的情况下，将链表转换成红黑树
4.static final int TREEIFY_THRESHOLD = 8;
##红黑树个数如果小于6的情况下将红黑树转换链表
5.static final int UNTREEIFY_THRESHOLD = 6;
###（数组容量>=64&链表长度大于8）
6.static final int MIN_TREEIFY_CAPACITY = 64;
// 实际存放大小个数
transient int size;
//hashMap迭代fastclass机制
transient int modCount;
// 扩容临界值16*0.75
int threshold;
// 加载因子
final float loadFactor;

put()方法

get()方法

remove()方法

HashMap8与7实现有那些区别

a、数据结构不一致，jdk7用的是数组+链表，jdk8用的是数组+链表+红黑树
b、扩容的改进，jdk7在多线程情况下，采用头插入法，容易造成死循环，jdk8在多线程情况下，使用尾插入法，解决了死锁问题。
c、查询效率，jdk7如果index冲突情况多的情况下，会导致链表过长，时间复杂度为o(n)，查询效率低下。Jdk8在链表长度达到8的时候，就转为了红黑树，时间复杂度立马降低为log n，速度有了大幅度的提升。

HashMap8中为什么需要引入红黑树

可解决死锁问题，并极大的提高查询速度。

HashMap是如何将链表转换红黑树

先将单向链表转为双向链表，然后把双向链表转为红黑树，容易前后遍历，目的是方便后续逆向的转换为链表。
当链表的长度>8且总长度>64的时候就会转为红黑树，如果红黑树的长度<6就转为链表。

HashMap为啥要链表长度达到8，且总数组长度达到64才转为红黑树？

因为8是偶数，也是2的倍数，转为红黑树正好满足O(logn)的复杂度。

数组达到64也是为了性能考虑，减少转换的次数。