在[深入浅出集合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 = 10737418241 << 31 = -21474836481 << 32 = 11 << 33 = 21 << -1 = -2147483648

hashmap的「最大容量「其实是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

推荐阅读:

「深入浅出」集合Map

javaWeb传收参数方式总结

周末了,笑久一点~

如果觉得不错，请给个「好看」

分享给你的朋友！

THANDKS

  • End -

一个立志成大腿而每天努力奋斗的年轻人

伴学习伴成长，成长之路你并不孤单!

推荐阅读：

相关文章