JDK源码解析之HashMap

前言：

    关于HashMap的源码解析网上已经有很多大神级别的文章，看的笔者心生敬佩，真心不敢写了。

    但是每次聊到HashMap的时候，总会有知识点是模糊的，应该还是眼高手低的缘故，所以还是决心写一下（很多参考大神的文章）

    注意：笔者的JDK是1.8.3版本的，所以包括之前写的JDK源码解析系列都是这个版本的

 

1.有关于哈希表

    哈希表这种数据结构，本质上也是数组，但是它与传统数组不同的是，它的下标是通过对数据进行一个函数处理之后，然后得到一个下标值，再在相应的位置存放该数据即可。

    所以针对数据的添加和查询操作都是基于函数处理之后获取下标，这样（在没有哈希冲突的情况下）它的操作时间复杂度都在O(1)

 

    笔者之前写过一篇关于哈希表实现的文章，读者可参考下：https://blog.csdn.net/qq_26323323/article/details/79497114 

    网上发现一篇写的比较好的哈希表博客：https://www.cnblogs.com/s-b-b/p/6208565.html 

 

2.HashMap的存储解决方案

    我们都知道HashMap是基于数组+链表的方式实现的，当然这是在JDK6的时候的实现方式。

    在JDK8中，HashMap做了一些变化，变成了数组+（链表|红黑树）的实现方式

 

    我们来简单想一下为什么会有这种变化？

    HashMap在解决哈希冲突的时候默认是采用链地址法，当出现哈希冲突时，以链表的方式来存储冲突的数据。

    我们再来思考一下使用链表来存储数据有什么不好的地方？

    如果使用链表来存储，链表的查询时间复杂度为O(N)，当链表过长时，就会发生查询效率过低的问题，那么如何解决呢？

 

    如果使用红黑树来存储的话，那查询时间复杂度直接降为O(log(n))，这样就解决了刚才链表查询效率过低的问题，所以HashMap8发生了这个优化

    借用网友的一个图片来总结一下（实在不会画图）来自https://www.cnblogs.com/yangming1996/p/7997468.html  ：

3.HashMap的结构分析

public class HashMap extends AbstractMap
    implements Map, Cloneable, Serializable {
    /** 常量 */
    // 初始化容量，默认为16
    static final int DEFAULT_INITIAL_CAPACITY = 1