HashMap 与 ConcurrentHashMap

一、背景：

线程不安全的HashMap：因为多线程环境下，使用Hashmap进行put操作会引起死循环，导致CPU利用率接近100%，所以在并发情况下不能使用HashMap。

效率低下的HashTable容器：HashTable容器使用synchronized来保证线程安全，但在线程竞争激烈的情况下HashTable的效率非常低下。

因为当一个线程访问HashTable的同步方法时，其他线程访问HashTable的同步方法时，可能会进入阻塞或轮询状态。如线程1使用put进行添加元素，线程2不但不能使用put方法添加元素，并且也不能使用get方法来获取元素，所以竞争越激烈效率越低。

二、锁分段技术：

既然不能全锁（HashTable）又不能不锁（HashMap），所以就搞个部分锁（ConcurrentHashMap），只锁部分（Segment），用到哪部分就锁哪部分。

一个大仓库（ConcurrentHashMap），里面有若干个隔间（Segment数组），每个隔间里面放置货架（HashEntry数组），每个货架上摆放货物（HashEntry则用于存储键值对数据），

每个隔间都有锁（Segment 是一种可重入锁 ReentrantLock ），同时只允许一个人进隔间存取东西。

但是，在存取东西之前，获取到隔间的锁（UnderLock），通过有一个全局索引（key.hashCode()），告诉你要操作的资源在哪个隔间里（根据key.hashCode()来决定操作的key在哪个Segment中），然后当你看到隔间空闲时，就可以进去存取，如果隔间正在占用，那你就得等着.

三、其他：

1，是否需要扩容。

在插入元素前会先判断Segment里的HashEntry数组是否超过容量（threshold），如果超过阀值，数组进行扩容。值得一提的是，Segment的扩容判断比HashMap更恰当，因为HashMap是在插入元素后判断元素是否已经到达容量的，如果到达了就进行扩容，但是很有可能扩容之后没有新元素插入，这时HashMap就进行了一次无效的扩容。

2，如何扩容。

扩容的时候首先会创建一个两倍于原容量的数组，然后将原数组里的元素进行再hash后插入到新的数组里。为了高效ConcurrentHashMap不会对整个容器进行扩容，而只对某个segment进行扩容。

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

四、JDK1.8之前和JDK1.8之后的ConcurrentHashMap工作原理：

JDK1.8之前：

ConcurrentHashMap结构:

ConcurrentHashMap结构分为两部分：segment数组，不可扩容；segment中的内部数组和链表，内部数组可扩容

concurrencyLevel： 并行级别、并发数、Segment 数，默认值是16，也就是说 ConcurrentHashMap 有 16 个 Segments，所以理论上，这个时候，最多可以同时支持 16 个线程并发写，只要它们的操作分别分布在不同的 Segment 上。这个值可以在初始化的时候设置为其他值，但是一旦初始化以后，它是不可以扩容的。

JDK1.8之后：

ConcurrentHashMap结构:

JDK1.8之后ConcurrentHashMap结构和JDK1.8之后的HashMap基本上一样，也是保持着数组+链表+红黑树的结构，不同的是，ConcurrentHashMap需要保证线程安全性。

ConcurrentHashMap总结和思考

可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近JDK1.8版本的HashMap，相对而言，ConcurrentHashMap只是增加了同步的操作来控制并发，从JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红黑树,相对而言，总结如下思考：

1,JDK1.8的实现降低锁的粒度，JDK1.7版本锁的粒度是基于Segment的，包含多个HashEntry，而JDK1.8锁的粒度就是HashEntry（首节点）。

2.JDK1.8版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使用synchronized来进行同步，所以不需要分段锁的概念，也就不需要Segment这种数据结构了，由于粒度的降低，实现的复杂度也降低了。

3,JDK1.8使用红黑树来优化链表，基于长度很长的链表的遍历是一个很漫长的过程，而红黑树的遍历效率是很快的，代替一定阈值的链表，这样形成一个最佳拍档。

4,JDK1.8为什么使用内置锁synchronized来代替重入锁ReentrantLock，有以下几点：

因为粒度降低了，在相对而言的低粒度加锁方式，synchronized并不比ReentrantLock差，在粗粒度加锁中ReentrantLock可能通过Condition来控制各个低粒度的边界，更加的灵活，而在低粒度中，Condition的优势就没有了。

JVM的开发团队从来都没有放弃synchronized，而且基于JVM的synchronized优化空间更大，使用内嵌的关键字比使用API更加自然。

在大量的数据操作下，对于JVM的内存压力，基于API的ReentrantLock会开销更多的内存，虽然不是瓶颈，但是也是一个选择依据。

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

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

3，JDK1.7 和  JDK1.8 对 ConcurrentHashMap的优化：

    JDK1.7 ConcurrentHashMap 的  get和put方法

3.1: put 方法：

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

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

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

最后会解除在 1 中所获取当前 Segment 的锁

3.2: get 方法：

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

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

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

  JDK1.8 ConcurrentHashMap 的  get和put方法：

3.2: put 方法：

根据 key 计算出 hashcode 。

判断是否需要进行初始化。

f 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。

如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。

如果都不满足，则利用 synchronized 锁写入数据。

如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。

3.4: get 方法

根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。

如果是红黑树那就按照树的方式获取值。

就不满足那就按照链表的方式遍历获取值。

4，hashMap 1.7 扩容死循环 和 1.8 修复（并发的情况，发生扩容时，可能会产生循环链表，在执行get的时候，会触发死循环，引起CPU的100%问题）：

4.1 ： JDK 1.7 HashMap扩容导致死循环的主要原因 ：

HashMap扩容导致死循环的主要原因在于扩容后链表中的节点在新的hash桶使用头插法插入。

新的hash桶会倒置原hash桶中的单链表，那么在多个线程同时扩容的情况下就可能导致产生一个存在闭环的单链表，从而导致死循环。

4.1 ： JDK 1.8 HashMap扩容不会造成死循环的原因：

在JDK 1.8中执行上面的扩容死循环代码示例就不会发生死循环，我们可以理解为在JDK 1.8 HashMap扩容不会造成死循环，但还是需要理论依据才有信服力。

首先通过上面的分析我们知道JDK 1.7中HashMap扩容发生死循环的主要原因在于扩容后链表倒置以及链表过长。

那么在JDK 1.8中HashMap扩容不会造成死循环的主要原因就从这两个角度去分析一下。

由于扩容是按两倍进行扩，即 N 扩为 N + N，因此就会存在低位部分 0 - (N-1)，以及高位部分 N - (2N-1)， 所以在扩容时分为 loHead (low Head) 和 hiHead (high head)。

然后将原hash桶中单链表上的节点按照尾插法插入到loHead和hiHead所引用的单链表中。

由于使用的是尾插法，不会导致单链表的倒置，所以扩容的时候不会导致死循环。

通过上面的分析，不难发现循环的产生是因为新链表的顺序跟旧的链表是完全相反的，所以只要保证建新链时还是按照原来的顺序的话就不会产生循环。

如果单链表的长度达到 8 ，就会自动转成红黑树，而转成红黑树之前产生的单链表的逻辑也是借助loHead (low Head) 和 hiHead (high head)，采用尾插法。然后再根据单链表生成红黑树，也不会导致发生死循环。

这里虽然JDK 1.8 中HashMap扩容的时候不会造成死循环，但是如果多个线程同时执行put操作，可能会导致同时向一个单链表中插入数据，从而导致数据丢失的。

所以不论是JDK 1.7 还是 1.8，HashMap线程都是不安全的，要使用线程安全的Map可以考虑ConcurrentHashMap。

JDK1.7的时候使用的是数组+ 单链表的数据结构。但是在JDK1.8及之后时，使用的是数组+链表+红黑树的数据结构（当链表的深度达到8的时候，也就是默认阈值，就会自动扩容把链表转成红黑树的数据结构来把时间复杂度从O（n）变成O（logN）提高了效率）

相关知识点

1,哈希表如何解决Hash冲突

2,为什么HashMap具备下述特点：键-值（key-value）都允许为空、线程不安全、不保证有序、存储位置随时间变化

3,为什么 HashMap 中 String、Integer 这样的包装类适合作为 key 键

4,HashMap 中的 key若是Object类型， 则需实现哪些方法？