HashMap和ConcurrentHashMap
HashMap? ConcurrentHashMap? 相信看完这篇没人能难住你！
前言
Map这样的Key Value在软件开发中是非常经典的结构，常用于在内存中存放数据。
本篇主要想讨论ConcurrentHashMap这样一个并发容器，在正式开始之前我觉得有必要谈谈HashMap，没有它就不会有后面的ConcurrentHashMap。
HashMap
众所周知HashMap底层是基于数组+链表组成的，不过再jdk1.7和1.8中具体实现稍有不同。
-
Base1.7
1.7中的数据结构图：
image
先来看看1.7中的实现。
image
这是HashMap中比较核心的几个成员变量；看看分别是什么意思？
1、初始化桶大小，因为底层是数组，所以这是数组默认的大小。
2、桶最大值。
3、默认的负载因子（0.75）
4、table真正存放数据的数组
5、Map存放数量的大小。
6、桶大小，可在初始化时显式指定。
7、负载因子，可在初始化时显式指定。
重点解释下负载因子：
由于给定的HashMap的容量大小是固定的，比如默认初始化：
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();
}
给定的默认容量为16，负载因子是0.75。Map在使用过程中不断的往里面存放数据，当数量达到了16*0.75=12就需要将当前16的容量进行扩容，而扩容这个过程涉及到rehash、复制数据等操作，所以非常消耗性能。
因此通常建议能提前预估HashMap的大小最好，尽量的减少扩容带来的性能损耗。
根据代码可以看到其实真正存放数据的是
transient Entry<K,V>[] table =(Entry<K,V>[]) EMPTY_TABLE;
这个数组，那么它又是如何定义的呢？
image
Entry是HashMap中的一个内部类，从他的成员变量很容易看出：
- key 就是写入时的键
- value 自然就是值
- 开始的时候就提到HashMap是由数组和链表组成，所以这个next就是用于实现链表结构。
- hash存放的是当前key的hashcode
知晓了基本结构，那来看看其中重要的写入、获取函数：
put方法
image
- 判断当前数组是否需要初始化。
- 如果key为空，则put一个空值进去。
- 根据key计算出hashcode。
- 根据计算出的hashcode定位所在的桶。
- 如果桶是一个链表则需要遍历判断里面的hashcode、key是否和传入key相等，如果相等则进行覆盖，并返回原来的值
- 如果桶是空的，说明当前位置没有数据存入；新增一个Entry对象写入当前位置。
image
当调用addEntry写入Entry时需要判断是否需要扩容。如果需要就进行两倍扩容，并将当前的key重新hash并定位。而在createEntry中会将当前位置的桶传入到新建的桶中，如果当前桶有值就会在位置形成链表。
get方法
再来看看get函数：
image
- 首先是根据key计算出hashcode，然后定位到具体的桶中。
- 判断该位置是否为链表。
- 不是链表就根据key、key的hashcode是否相等来返回值。
- 为链表则需要遍历直到key及hashcode相等时候就返回值。
- 啥都没取到就直接返回null。
Base1.8
不知道1.7的实现大家看出来需要优化的点没有？
其实一个很明显的地方就是：
当Hash冲突严重时，在桶上形成的链表会变的越来越长，这样在查询时效率就会越来越低，时间复杂度O(N)。
因此1.8中重点优化了这个查询效率。
1.8 HashMap结构图
image
先来看看几个核心的成员变量：
image
和1.7大体上都差不多，还有几个重要的区别：
- TREEIFY_THRESHOLD用于判断是否需要将链表转换为红黑树的阙值。
- HashEntry修改为Node。
Node的核心组成其实也是和1.7中的HashEntry一样，存放的都是key value hashcode next等数据
再来看看核心方法。
put方法
image
看似要比1.7的复杂，我们一步步拆解：
1、判断当前桶是否为空，空的就需要初始化（resize中会判断是否进初始化）。
2、根据当前key的hashcode定位到具体的桶中并判断是否为空，为空表明没有Hash冲突就直接在当前位置创建一个新桶即可。
3、如果当前桶有值（Hash冲突），那么就要比较当前桶中的key、key的hashcode与写入的key是否相等，相等就赋值给e，在第8步的时候会统一进行复制及返回。
4、如果当前桶为红黑树，那就要按照红黑树的方式写入数据。
5、如果是个链表，就需要当前的key、value封装成一个新节点写入到当前桶的后面（形成链表）。
6、接着判断当前链表的大小是否大于预设的阙值，大于时就要转换成红黑树。
7、如果在遍历过程中找到key相同时直接退出遍历。
8、如果e！=null就相当于存在相同的key，那就需要将值覆盖。
9、最后判断是否需要进行扩容。
get方法
image
get方法看起来就简单许多了。
- 首先将key hash之后取得所定位的桶。
- 如果桶为空则直接返回null。
- 否则判断的第一个位置（有可能时链表、红黑树）的key是否为查询的key，是就直接返回value。
- 如果第一个不匹配，则判断的下一个是红黑树还是链表。
- 红黑树就按照树的查找方式返回值
- 不然就按照链表的方式遍历匹配返回值。
从这两个核心方法（get/put）可以看出1.8中对大链表做了优化，修改为红黑树之后查询效率直接提高到了O（logn）。
但是HashMap原有的问题也都存在，比如在并发场景下使用时容易出现死循环。
package com.test;
import java.util.HashMap;
import java.util.UUID;
public class HashMapDemo {
final HashMap<String, String> map = new HashMap<>();
public static void main(String[] args) {
for (int i = 0; i < 1000; i++) {
new Thread(new Runnable() {
@Override
public void run() {
map.put(UUID.randomUUID().toString(), "");
}
}).start();
}
}
}
但是为什么呢？简单分析下。
看过上文的还记得在HashMap扩容的时候会调用resize()方法，就是这里的并发操作容易在一个桶上形成环形链表；这样当获取一个不存在的key时，计算出的index正好时环形链表的下标就会出现死循环。
image
遍历方式
还有一个值得注意的时HashMap的遍历方式，通常有以下几种：
Iterator<Map.Entry<String, String>> entryIterator = map.entrySet().iterator();
while (entryIterator.hasNext()) {
Map.Entry<String, String> next = entryIterator.next();
System.out.println("key=" + next.getKey() + "value=" + next.getValue());
}
Iterator<String> iterator = map.keySet().iterator();
while (iterator.hasNext()) {
String key = iterator.next();
System.out.println("key=" + key + "value=" + map.get(key));
}
强烈建议使用第一种EntrySet进行遍历。
第一种可以把key value同时取出，第二种还得通过key取一次value，效率较低。
简单总结下HashMap：无论是1.7还是1.8其实都能看出JDK没有对它做任何的同步操作，所以并发会出问题，甚至出现死循环导致系统不可用。
因此JDK推出了专项专用的ConcurrentHashMap，该类位于java.util.concurrent包下，专门用于解决并发问题。
坚持看到这里的朋友算是已经把 ConcurrentHashMap 的基础已经打牢了，下面正式开始分析。
ConcurrentHashMap
ConcurrentHashMap 同样也分为 1.7 、1.8 版，两者在实现上略有不同。
-
Base 1.7
先来看看 1.7 的实现，下面是他的结构图：
image
如图所示，是由Segment数组，HashEntry组成，和HashMap一样，仍然是数组加链表。
它的核心成员变量：
image
Segment是ConcurrentHashMap的一个内部类，主要的组成如下：
image
看看其中HashEntry的组成：
image
和HashMap非常类似，唯一的区别就是其中的核心数据如value，以及链表都是用volatitle修饰的，保证了获取时的可见性。
原理上来说：ConcurrentHashMap采用了分段锁技术，其中Segment继承于ReentrantLock。不会像HashTable那样不管是put还是get操作都需要做同步处理，理论上ConcurrentHashMap支持CurrencyLevel（Segment数组数量）的线程并发。每当一个线程占用锁访问一个Segment时，不会影响到其他的Segment。
下面也来看看核心的put get方法。
put方法
image
image
首先时通过key定位到Segment，之后在对应的Segment中进行具体的put。
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();
}
return oldValue;
}
虽然HashEntry中的value是用volatile关键词修饰的，但是并不能保证并发的原子性，所以put操作时仍然需要加锁处理。
首先第一步的时候会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用scanAndLockForPut()自旋获取锁。
image
1、尝试自旋获取锁。
2、如果重试的次数达到了MAX_SCAN_RETRIES则改为阻塞锁获取，保证能获取成功。
image
再结合图看看put的流程。
1、将当前Segment中的table通过key的hashcode定位到HashEntry。
2、遍历该HashEntry，如果不为空则判断传入的key和当前遍历的key是否相等，相等则覆盖旧的value。
3、不为空则需要新建一个HashEntry并加入到Segment中，同时会先判断是否需要扩容。
4、最后会接触在1中所获取当前Segment的锁。
get 方法
image
get逻辑比较简单：
只需要将key通过hash之后定位到具体的Segment，再通过一次Hash定位到具体的元素上。
由于HashEntry中的value属性是用volatitle关键词修饰的，保证了内存可见性，所以每次获取时都是最新值。
ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需要加锁。
-
Base 1.8
1.7 已经解决了并发问题，并且能支持 N 个 Segment 这么多次数的并发，但依然存在 HashMap 在 1.7 版本中的问题。
那就是查询遍历链表效率太低。
因此 1.8 做了一些数据结构上的调整。
首先来看下底层的组成结构：
image
看起来是不是和1.8HashMap结构类似？
其中抛弃了原有的Segment分段所，而采用了CAS+synchronized来保证并发安全性。
image
也是将1.7中存放数据的HashEntry改为Node，但作用都是相同的。其中的val next都用了volatile修饰，保证了可见性。
put方法
重点来看看put函数：
image
- 根据key计算出hashcode。
- 判断是否需要进行初始化。
- f即为当前key定位出的Node，如果为空表示当前位置可以写入数据，利用CAS尝试写入，失败则自旋保证成功。
- 如果当前位置的hashcode==MOVED==-1，则需要进行扩容。
- 如果都不满足，则利用synchronized锁写入数据。
- 如果数量大于TREEIFY_THRESHOLD则要转换为红黑树。
get方法
image
- 根据计算出来的hashcode寻址，如果就在桶上那么直接返回值。
- 如果是红黑树那就按照树的方式获取值。
- 都不满足那就按照链表的方式遍历获取值。
1.8 在 1.7 的数据结构上做了大的改动，采用红黑树之后可以保证查询效率（O(logn)），甚至取消了 ReentrantLock 改为了 synchronized，这样可以看出在新版的 JDK 中对 synchronized 优化是很到位的。
总结
看完了整个 HashMap 和 ConcurrentHashMap 在 1.7 和 1.8 中不同的实现方式相信大家对他们的理解应该会更加到位。
其实这块也是面试的重点内容，通常的套路是：
-
谈谈你理解的 HashMap，讲讲其中的 get put 过程。
-
1.8 做了什么优化？
-
是线程安全的嘛？
-
不安全会导致哪些问题？
-
如何解决？有没有线程安全的并发容器？
-
ConcurrentHashMap 是如何实现的？ 1.7、1.8 实现有何不同？为什么这么做？
这一串问题相信大家仔细看完都能怼回面试官。
除了面试会问到之外平时的应用其实也蛮多，像之前谈到的 Guava 中 Cache 的实现就是利用 ConcurrentHashMap 的思想。同时也能学习 JDK 作者大牛们的优化思路以及并发解决方案。
