HashMap和ConcurrentHashMap

HashMap? ConcurrentHashMap? 相信看完这篇没人能难住你！

前言

Map这样的Key Value在软件开发中是非常经典的结构，常用于在内存中存放数据。

本篇主要想讨论ConcurrentHashMap这样一个并发容器，在正式开始之前我觉得有必要谈谈HashMap，没有它就不会有后面的ConcurrentHashMap。

HashMap

众所周知HashMap底层是基于数组+链表组成的，不过再jdk1.7和1.8中具体实现稍有不同。

Base1.7

　　1.7中的数据结构图：

先来看看1.7中的实现。

这是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;

这个数组，那么它又是如何定义的呢？

Entry是HashMap中的一个内部类，从他的成员变量很容易看出：

key 就是写入时的键
value 自然就是值
开始的时候就提到HashMap是由数组和链表组成，所以这个next就是用于实现链表结构。
hash存放的是当前key的hashcode

知晓了基本结构，那来看看其中重要的写入、获取函数：

put方法

判断当前数组是否需要初始化。
如果key为空，则put一个空值进去。
根据key计算出hashcode。
根据计算出的hashcode定位所在的桶。
如果桶是一个链表则需要遍历判断里面的hashcode、key是否和传入key相等，如果相等则进行覆盖，并返回原来的值
如果桶是空的，说明当前位置没有数据存入；新增一个Entry对象写入当前位置。

当调用addEntry写入Entry时需要判断是否需要扩容。如果需要就进行两倍扩容，并将当前的key重新hash并定位。而在createEntry中会将当前位置的桶传入到新建的桶中，如果当前桶有值就会在位置形成链表。

get方法

再来看看get函数：

首先是根据key计算出hashcode，然后定位到具体的桶中。
判断该位置是否为链表。
不是链表就根据key、key的hashcode是否相等来返回值。
为链表则需要遍历直到key及hashcode相等时候就返回值。
啥都没取到就直接返回null。

Base1.8

不知道1.7的实现大家看出来需要优化的点没有？

其实一个很明显的地方就是：

当Hash冲突严重时，在桶上形成的链表会变的越来越长，这样在查询时效率就会越来越低，时间复杂度O(N)。

因此1.8中重点优化了这个查询效率。

1.8 HashMap结构图

先来看看几个核心的成员变量：

和1.7大体上都差不多，还有几个重要的区别：

TREEIFY_THRESHOLD用于判断是否需要将链表转换为红黑树的阙值。
HashEntry修改为Node。

Node的核心组成其实也是和1.7中的HashEntry一样，存放的都是key value hashcode next等数据

再来看看核心方法。

put方法

看似要比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方法

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正好时环形链表的下标就会出现死循环。

遍历方式

还有一个值得注意的时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 的实现，下面是他的结构图：

如图所示，是由Segment数组，HashEntry组成，和HashMap一样，仍然是数组加链表。

它的核心成员变量：

Segment是ConcurrentHashMap的一个内部类，主要的组成如下：

看看其中HashEntry的组成：

和HashMap非常类似，唯一的区别就是其中的核心数据如value，以及链表都是用volatitle修饰的，保证了获取时的可见性。

原理上来说：ConcurrentHashMap采用了分段锁技术，其中Segment继承于ReentrantLock。不会像HashTable那样不管是put还是get操作都需要做同步处理，理论上ConcurrentHashMap支持CurrencyLevel（Segment数组数量）的线程并发。每当一个线程占用锁访问一个Segment时，不会影响到其他的Segment。

下面也来看看核心的put get方法。

put方法

首先时通过key定位到Segment，之后在对应的Segment中进行具体的put。

 1        final V put(K key, int hash, V value, boolean onlyIfAbsent) {
 2            HashEntry<K,V> node = tryLock() ? null :
 3                scanAndLockForPut(key, hash, value);
 4            V oldValue;
 5            try {
 6                HashEntry<K,V>[] tab = table;
 7                int index = (tab.length - 1) & hash;
 8                HashEntry<K,V> first = entryAt(tab, index);
 9                for (HashEntry<K,V> e = first;;) {
10                    if (e != null) {
11                        K k;
12                        if ((k = e.key) == key ||
13                            (e.hash == hash && key.equals(k))) {
14                            oldValue = e.value;
15                            if (!onlyIfAbsent) {
16                                e.value = value;
17                                ++modCount;
18                            }
19                            break;
20                        }
21                        e = e.next;
22                    }
23                    else {
24                        if (node != null)
25                            node.setNext(first);
26                        else
27                            node = new HashEntry<K,V>(hash, key, value, first);
28                        int c = count + 1;
29                        if (c > threshold && tab.length < MAXIMUM_CAPACITY)
30                            rehash(node);
31                        else
32                            setEntryAt(tab, index, node);
33                        ++modCount;
34                        count = c;
35                        oldValue = null;
36                        break;
37                    }
38                }
39            } finally {
40                unlock();
41            }
42            return oldValue;
43        }

虽然HashEntry中的value是用volatile关键词修饰的，但是并不能保证并发的原子性，所以put操作时仍然需要加锁处理。

首先第一步的时候会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用scanAndLockForPut()自旋获取锁。

1、尝试自旋获取锁。

2、如果重试的次数达到了MAX_SCAN_RETRIES则改为阻塞锁获取，保证能获取成功。

再结合图看看put的流程。

1、将当前Segment中的table通过key的hashcode定位到HashEntry。

2、遍历该HashEntry，如果不为空则判断传入的key和当前遍历的key是否相等，相等则覆盖旧的value。

3、不为空则需要新建一个HashEntry并加入到Segment中，同时会先判断是否需要扩容。

4、最后会接触在1中所获取当前Segment的锁。

get 方法

get逻辑比较简单：

只需要将key通过hash之后定位到具体的Segment，再通过一次Hash定位到具体的元素上。

由于HashEntry中的value属性是用volatitle关键词修饰的，保证了内存可见性，所以每次获取时都是最新值。

ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需要加锁。

Base 1.8

1.7 已经解决了并发问题，并且能支持 N 个 Segment 这么多次数的并发，但依然存在 HashMap 在 1.7 版本中的问题。

那就是查询遍历链表效率太低。

因此 1.8 做了一些数据结构上的调整。

首先来看下底层的组成结构：

看起来是不是和1.8HashMap结构类似？

其中抛弃了原有的Segment分段所，而采用了CAS+synchronized来保证并发安全性。

也是将1.7中存放数据的HashEntry改为Node，但作用都是相同的。其中的val next都用了volatile修饰，保证了可见性。

put方法

重点来看看put函数：

根据key计算出hashcode。
判断是否需要进行初始化。
f即为当前key定位出的Node，如果为空表示当前位置可以写入数据，利用CAS尝试写入，失败则自旋保证成功。
如果当前位置的hashcode==MOVED==-1，则需要进行扩容。
如果都不满足，则利用synchronized锁写入数据。
如果数量大于TREEIFY_THRESHOLD则要转换为红黑树。

get方法

根据计算出来的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 作者大牛们的优化思路以及并发解决方案。