JDK1.8源码逐字逐句带你理解HashMap底层（2）

引言：

很开心，大家继续来看HashMap底层的第二段。昨天（上一篇博文）我们主要是介绍了HashMap类的一些重要的成员变量并简述了他们的名称作用，附带图文解释了他们之间存在的关系，又深入学习了HashMap存储的发展和结构，以一个简单的demo描述了HashMap的初始化和各个变量的变化情况。今天主要是从HashMap的源码入手，我会逐字逐句的解释每一种情况中HashMap干了些什么。为了大家更好的理解，我会适当拓展一下和HashMap底层相关的一些技术话题，所以，在博文中“技术点”这个模块将会让你对整个博文理解更深刻哦。如果是新来的朋友，可以查看我的博文目录寻找上半篇，同时目前的博文都是面试高频出现的哦，大家可以点击链接：http://blog.csdn.net/u012403290

技术点：

1、算法复杂度（时间复杂度和空间复杂度）

①空间复杂度是指运行一个程序所需要的内存大小，主要用于估计程序运行所需内存大小。主要分为固定部分和可变部分，固定部分是指代码、常量、简单变量等所占的空间，可变部分主要算法输入、程序执行所需要的额外空间。一般来说降低空间复杂度可以考虑压缩存储技术。

②时间复杂度用O(f(n))表示，主要是用于描述算法执行效率高低。它是面试当中经常会遇到的笔试题，比如说给你一段程序，要求你求得该段程序的时间复杂度。笔者不想去解释它的定义了，因为会让大家反而变得看不懂，我先从小到大列出常见的时间复杂度，然后给几个代码片段来一起求复杂度。
常见时间复杂度：常数阶O(1)，对数阶O(log2n)，线性阶O(n)，线性对数阶O(nlog2n)，平方阶O(n^2)，立方阶O(n^3)，K次方阶O(n^k)，指数阶O(2^n)。这些复杂度的算法执行效率是依次递减的，所以在上述当中指数阶是最差的时间复杂度，也就是指数阶的算法执行效率最低。这里可能有的小伙伴就要问了，O(1)当中的1不见得比O(log2n)的log2n小吧。其实不是这么理解，应该理解的模式是当n无穷大的时候，他们所对应的值。下面我引入一张百度的图片：

其实在我们一般编程中写算法的时候会以O(n)为界限，如上图坡度越小，效率越好，我们越喜欢。但是那些爆炸式的时间复杂度肯定也存在意义，比如说天文计算等等。接下来，我们用几个例子说明如何计算时间复杂度：

        for (int i = 0; i < n; i++) { //2j++;   //3}

其中语句2执行n+1次，语句3执行n次(之所以语句2会多执行一次是因为语句不符合的时候还会进行一次运行判断)
那么时间复杂度就是O(n+1+n)= O(2n+1)=O(n)。为什么直接就等于O(n)了呢？因为我们只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。所以如果熟练之后只需要看最里面的语句的执行频度就可以确定阶级了。在比如：

        for (int i = 0; i < n; i++) {    //1for(int j = 0; j//2k++;                      //3}}

上面代码段中有两个for循环。语句1执行n+1次，语句2执行n*(n+1)次，语句3执行n*n次。所以他们的时间复杂度就是O(n+1+n*(n+1)+n^2) = O(2n^2+2n+1)=O(n^2).
时间复杂度就写到这里了，篇幅太长不好，有兴趣可以自己去找资料研究哒。

在HashMap中组数里面添加了链表，就是一种时间复杂度换空间复杂度的一种方式。合理配置时间复杂度和空间复杂度会使得程序更加的健壮。

2、红黑树

红黑树是自平衡的二叉查找树(有序二叉树)，一般的二叉查找树的时间复杂度为O(lgn)，当一般的二叉查找树退化之后会变成一个线性的列表，这个时候它的时间复杂度就变为了O(n)(这个O(n)其实就是for循环/遍历一次)，但是红黑树它所独有的着色和自平衡的一些性质使得时间复杂度最坏为O(logn)，而不是更低的O(n)，这就是等下我们要说的为什么HashMap在JDK1.8的时候引入冲突解决方案要用红黑树。对于红黑树，笔者在简单的说一下大致性质：

从图中就可以看到：①对于任意一个节点，它的左子节点比它小，右子节点比它大， 其实它还有更多的性质。我们就不一一研究了。我们只需要知道这一条性质和红黑树的优势就是可以自平衡。注意，本博客中提到的树性质就是①。

节点插入:遍历树，根据上面描述的性质，只要根据key值的大小可以很快定位到新要插入的节点位置。如果插入破坏了红黑树本身的平衡，红黑树会进行旋转，重新着色进行调整。

节点删除：分为3种情况。①第一要删除的节点处于最外层，那么就可以直接删除。②如果它存在一个子节点，这个子节点直接顶替要删除的节点后并不会破坏整棵树的性质，③如果

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！