剑指Offer(类库)——HashMap、HashTable、ConcurrentHashMap底层源码详解

Map是由一对对的Key-Value组成的，key要求唯一，value无所谓。

我们可以针对这点直接看源码;

key自带去重功能，因为是Set类型的。
value则只是Collection接口，可以存放任意集合。
在这里插入图片描述
下面来看看map的一些实现类

在这里插入图片描述
下面，来解决一道非常重要的面试题：

HashMap，HashTable，ConcurrentHashMap有什么区别?

HashMap_15">1.HashMap

首先来介绍一下hashMap，在jdk8之前，hashMap都是由数组+链表组成的。因为数组增删插都慢，而查找快，而链表查询慢，增删插都很快，因此HashMap结合了两者的优势，并且hashMap的操作是非线程安全的，所以效率高，组织键位如下图：

在这里插入图片描述

在我们没有给HashMap初始长度的时候，hashMap默认的初始长度是16，那么在这个初始长度为16的数组中，每一个数组的位置都是存储的链表的头结点，我们可以通过取模运算，得到头结点的存放位置：hash(key.hashCode())%len，而hashCode的运算，又本身是通过位运算得到的。

但是有一种特殊情况是这样的，我们通过取模运算，得到的位置每一次都是同一个，这样就会不断在一条链表中去插入，最坏的性能是让时间复杂度从O1变成On。

于是在jdk8之后hashMap进行了优化，将原先HashMap由数组+链表组成的道理变成了数组+链表+红黑树。

添加了红黑树之后，当我们再遇见之前那种特殊情况的时候，我们就可以去用TREEIFY_THRESHOLD判断是否要将链表转换成一颗红黑树了，在这种情况下，我们的最坏情况的时间复杂度就从On变成了Ologn。

接下来我们来看看源码：

首先是hashMap的节点结构

在这里插入图片描述

首先可以看出是一个数组，其次，这个数组的元素，还是一个一个的头结点，我们点进去Node，可以看见内部的构造。

在这里插入图片描述

hash是用来寻址的，next是用来连接下一个链表或者树的结点的。

然后再来看看我们之前提到的从链表变成红黑树的那个界

在这里插入图片描述

也就是当超过了8，就会从链表变成红黑树。并且既然有TREEIFY_THRESHOLD，让链表转换成红黑树来提高性能，那么如果我们删除结点，让结点节点，也必然也是有策略让红黑树变成链表的界的。

也就是UNTREEIFY_THRESHOLD=6的时候，从红黑树转变成链表。
在这里插入图片描述

阅读了HashMap的成员变量之后，我们再来看看hashMap的构造函数，一共是如下的几个：

在这里插入图片描述

我们可以从这个loadFactor判断出来，hashMap也是懒加载的，也就是说，当我们new 出来的时候不会去加载分配空间，只有真正去使用的时候，才会去初始化，和Hibernate的延迟加载原理是一样的。

也就是说，当我们去put的时候，才是初始化的开始，所以我们再来看看put的方法：
在这里插入图片描述
可以发现，put实际上是使用的putVal方法，那我们再来看putVal方法的逻辑

我们可以从这两段代码看出来，当我们第一次使用的时候，和超过16个大小的时候，hashmap就会去分配合适的空间去使用。

并且可以发现，在里面也有添加之后判断是否树化，分配寻址空间，等等的细节逻辑。

最后对HashMap的put操作进行一个思路上的总结：

如果HashMap没有被初始化，则初始化
对Key求Hash值，然后再计算下标
如果没有碰撞，直接放入桶中
如果碰撞了，以链表的方式链接到后面
如果链表长度超过阈值，就把链表转成红黑树
如果链表长度低于6，就把红黑树转回链表
如果节点已经存在，就替换旧值
如果桶满了（容量16*0.75），就需要resize扩容2倍后重排。

然后再来看一下HashMap的get 方法的逻辑：

在这里插入图片描述

主要的get逻辑是这样的：使用hash算法，找到对应的bucket桶，然后用key.equals找到地址空间，最后找到值返回。

除了树化这种方式被动的提升性能以外，hash运算也是可以提升性能的，但是hash运算是存在哈希碰撞的，下面是几种减少哈希碰撞概率的方法：

扰动函数：促使元素位置分布均匀，减少碰撞几率。
使用final对象，并且采用合适的equals()和hashCode()方法。

最后再稍微提一下hashMap的扩容问题：

在多线程的情况下，调整大小存在条件竞争，容易死锁。
rehashing是一个比较耗时的过程。

HashTable_91">2.HashTable

我们都知道，HashTable是线程安全的，那么，hashTable究竟做到了什么，才做到了HashMap没做到的线程安全呢？

写段代码来说一下:

在这里插入图片描述

接着来解释一下为什么是线程安全的

我们进入synchronizedMap这个方法内部看一下

在这里插入图片描述

我们可以发现，这里声明了一个mutex修饰对象成员，用互斥锁包起来，就保证了内容互斥，串行化访问，以保证线程安全。

而hashTable同理，也是一样的，和hashMap的实现逻辑本质没什么差别，就是同样的去加锁了而已，我接一个随便的方法看一下就知道了：

在这里插入图片描述

但是我们知道了，串行化访问，肯定效率就降低了，所以为了改变当时的那种情况，既保证安全，又保证效率，并行化的ConcurrentHashMap就出来了。

HashMap_112">3. ConcurrentHashMap

经过了上面对于HashTable 的介绍之后，先不去介绍ConcurrentHashMap，先说说，我们要如何去优化HashTable

通过锁细粒度化，化整锁拆解成多个锁进行优化。

早期的在jdk5的ConcurrentHashMap确实是这么做的，它是通过分段锁Segment来实现的，结构也是数组加链表，而Segment也可以对应着头结点去存放默认16把锁，区别就是，比起HashMap，给每一个头结点配一把锁，从串行化的HashTable简单对比一下，效率提升了16倍。

在这里插入图片描述
也就是说，如果我们7号锁的下城去访问数组的话，其他节点所占有的线程也可以去访问这些资源，是不会被阻塞的，只有相同的Segment才会被阻塞。

但是每一个bucket都用不同的锁去管理，说实话还是有点过多的使用了性能，所以我们就有了一定的改进，在jdk8，ConcurrentHashMap使用了CAS+synchronized使得锁变得更加细化，同时又做了进一步的优化。

下面是ConcurrentHashMap最新的图解：

可以看出，jdk8的ConcurrentHashMap也随着最新的HashMap，使用了数组+链表+红黑树这种结构在效率上进行一定的提升。

在这里插入图片描述
紧接着我们来看看ConcurrentHashMap的源码：

从内置的成员变量来看，确实和之前介绍的hashmap是有相似的地方的

在这里插入图片描述

其中最重要的是一个叫做sizeCtl的成员变量，是JUC下ConcurrentHashMap十分关键的一个成员变量了。

它是一个做大小控制的标识符，是哈希表初始化或者扩容和时候的一个控制位标示量，负数代表正在进行初始化或者扩容操作，-1代表正在初始化，其他的负数代表有n-1个线程正在等待扩容，整数和0代表还没被初始化。

因为被volatile修饰，所以是多线程可见的。

在这里插入图片描述

我们知道ConcurrentHashMap是使用CAS+Synchronized来做到高效的保证线程安全的，也同样来看看它的put方法：

由于代码比较多，先来看看预备方面的操作

我们这里使用for循环，是因为有个cas操作，要保证不断的去请求操作，之后进行判空，如果是空的就进行初始化；
如果不是空的，就进行哈希寻址找到头结点的存储位置。
如果这个位置不存在，就用cas操作创造出来，添加失败就break进入下一次循环。
如果发现这个key已经存在了，说明ConcurrenthashMap正在进行remove，remove就是说明正在进行扩容，我们就协助他们扩容，执行helpTransfer操作。

最后一种情况也就是最恶劣的哈希碰撞：

这时候就会锁住链表或者红黑二叉树的头结点，也就是我们的数组元素，操作如下：

首先判断这个出现哈希碰撞的结点是不是头结点，如果是，就触发计数器为1，遍历链表，如果发现结点存在，就更新value，如果不存在，就更新结点，逻辑和hashMap相同。
在这里插入图片描述

此外，ConcurrenthashMap还可以构建本地缓存，来降低程序的计算量，复杂度。

在这里插入图片描述
总结一下ConcurrentHashmap的put方法逻辑：

判断Node[]数组是否进行了初始化，没有就进行初始化操作。
通过hash定位数组的索引坐标，是否有Node节点，如果没有就使用CAS进行添加，添加失败就进入下一次循环。
检查到内部正在扩容，就帮助一起扩容。
如果链表头结点是空的，就是用synchronized锁住头结点。之后：
4.1 如果是Node就进行链表的添加操作。
4.2 如果是TreeNode就进行树添加操作。
5.判断链表长度，6 和8 的链表和树的转换。

然后再总结一下ConcurrentHashMap的jdk1.8版本和1.5版本的差异：

说白了我们总体还是使用的锁分离的思想，比Segment更加细致，首先使用无锁操作CAS插入头结点，失败就循环重试，如果头结点已经存在，就尝试获取头结点的同步锁，再进行操作

最后最后再总结一句话，三者的区别：