HashMap在JDK7和JDK8中的区别
HashMap在JDK7和JDK8中的区别
在[深入浅出集合Map]中,已讲述了HashMap在jdk7中实现,在此就不再细说了
JDK7中的HashMap
基于链表+数组实现,底层维护一个Entry数组
Entry<K,V>[] table;根据计算的hashCode将对应的KV键值对存储到该table中，一旦发生hashCode冲突，那么就会将该KV键值对放到对应的已有元素的后面， 此时，形成了一个链表式的存储结构,如下图
JDK8中的HashMap
基于位桶+链表/红黑树的方式实现,底层维护一个Node数组
Node<K,V>[] table;在JDK7中HashMap,当成百上千个节点在hash时发生碰撞，存储一个链表中，那么如果要查找其中一个节点，那就不可避免的花费O(N)的查找时间，这将是多么大的性能损失,这个问题终于在JDK8中得到了解决。
JDK8中,HashMap采用的是位桶+链表/红黑树的方式,当链表的存储的数据个数大于等于8的时候，不再采用链表存储，而采用了红黑树存储结构。这是JDK7与JDK8中HashMap实现的最大区别。 如下图所示：
这么做主要是再查询的时间复杂度上进行优化，链表为O(n)，而红黑树一直是O(logn)，冲突（即为相同的hash值存储的元素个数） 超过8个，可以大大的提高查找性能。
其他异同
共同点
1.容量(capacity):容量为底层数组的长度,JDK7中为Entry数组,JDK8中为Node数组
a. 容量一定为2的次幂
static int indexFor(int h, int length) {
return h & (length-1);
} 这段代码是用来计算出键值对存放在一个数组的索引,h是int hash = hash(key.hashCode())计算出来的,SUN大师们发现, “当容量一定是2^n时，h & (length - 1) == h % length” ,按位运算特别快 。
源码中大量使用运算，对于计算机,位运算计算效率特别快，毕竟二进制才是亲儿子呀
b. 默认初始容量16(容量为低层数组的长度,JDK7中为Entry数组,JDK8中为Node数组)
c.最大容量1<<30,即2的30次方
1 << 30 = 1073741824
1 << 31 = -2147483648
1 << 32 = 1
1 << 33 = 2
1 << -1 = -2147483648hashmap的“最大容量“其实是Integer.MAX_VALUE
2.加载因子(Load factor)：HashMap在其容量自动增加前可达到多满的一种尺度 a. 默认加载因子 = 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f - 加载因子越大、填满的元素越多 = 空间利用率高、但冲突的机会加大、查找效率变低（因为链表变长了）
- 加载因子越小、填满的元素越少 = 空间利用率小、冲突的机会减小、查找效率高（链表不长） 0.75是一个"冲突的机会"与"空间利用率"之间寻找一种平衡与折衷的选择
3.扩容机制：扩容时resize(2 * table.length)，扩容到原数组长度的2倍。
4.key为null:若key == null，则hash(key) = 0，则将该键-值 存放到数组table 中的第1个位置，即table [0]
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}不同点
1.发生hash冲突时 JDK7:发生hash冲突时，新元素插入到链表头中，即新元素总是添加到数组中，就元素移动到链表中。 JDK8：发生hash冲突后，会优先判断该节点的数据结构式是红黑树还是链表，如果是红黑树，则在红黑树中插入数据；如果是链表，则将数据插入到链表的尾部并判断链表长度是否大于8，如果大于8要转成红黑树。
2.扩容时 JDK7:在扩容resize（）过程中，采用单链表的头插入方式，在将旧数组上的数据 转移到 新数组上时，转移操作 = 按旧链表的正序遍历链表、在新链表的头部依次插入，即在转移数据、扩容后，容易出现链表逆序的情况 。 多线程下resize()容易出现死循环。此时若（多线程）并发执行 put（）操作，一旦出现扩容情况，则 容易出现 环形链表，从而在获取数据、遍历链表时 形成死循环（Infinite Loop），即 死锁的状态 。
JDK8:由于 JDK 1.8 转移数据操作 = 按旧链表的正序遍历链表、在新链表的尾部依次插入，所以不会出现链表 逆序、倒置的情况，故不容易出现环形链表的情况 ，但jdk1.8仍是线程不安全的，因为没有加同步锁保护。
建议: 1.使用时设置初始值,避免多次扩容的性能消耗 2.使用自定义对象作为key时,需要重写hashCode和equals方法 3.多线程下,使用CurrentHashMap代替HashMap
推荐阅读:
如果觉得不错，请给个「好看」
分享给你的朋友！
THANDKS
- End -