搞懂HashTable与ConcurrentHashMap

• 前言
• 一、如何处理HashMap在多线程中的安全问题
• 二、如何实现线程安全
• • 1.HashTable
  • 2.ConcurrentHashMap
  • 3.Collections.synchronizedMap(Map)
• 三、HashTable与ConcurrentHashMap get与put过程
• • 1.HashTable的get：
  • 2.HashTable的put：
  • 3.ConcurrentHashMap的get：
  • 4.ConcurrentHashMap的put：
• 四、1.8进行了什么优化
• 五、ConcurrentHashMap为什么是高并发的
• 六、CAS
• • 1.CAS原理：
  • 2.CAS防止ABA：

前言

HashMap在多线程环境下存在线程安全问题，本文将讲解如何解决线程中安全问题

以下是本篇文章正文内容

一、如何处理HashMap在多线程中的安全问题

1.使用Collections.synchronizedMap(Map)创建线程安全的map集合； 2.Hashtable 3.ConcurrentHashMap 不过出于线程并发度的原因，都会舍弃前两者使用最后的ConcurrentHashMap，他的性能和效率明显 优于前两者。

二、如何实现线程安全

1.HashTable

对数据操作的时候都会上锁，导致效率比较低下

代码如下（示例）：每次读写都会加锁 最多允许一个线程访问并发量较低

2.ConcurrentHashMap

具体原理请看 ConcurrentHashMap的put讲解

1.7之前采用分段锁的方式

1.8之后采用cas+synchronize

3.Collections.synchronizedMap(Map)

在SynchronizedMap内部维护了一个普通对象Map，还有排斥锁mutex

创建出synchronizedMap之后，再操作map的时候，就会对方法上锁

三、HashTable与ConcurrentHashMap get与put过程

1.HashTable的get：

首先计算key的下标,获取hashtable中的数组
		找到对应下标数组,获取对应的链表
		遍历俩表,判断是否有满足条件的entry,如果有,获取value对应的值返回。否则,返回为空.
           

2.HashTable的put：

首先判断value的是是否为空,如果为空,抛出空指针异常
	如果不为空,获取hashtable中的table,获取key的hash值以及对应的下标
	从数组中获取下标对应的链表信息,遍历链表,查询是否有满足条件的entry对象,如果有满足条件的,旧值被新值覆盖,返回旧值
	如果没有,添加一个新的entry
	添加新的entry前先判断当前数组的元素数量是否满足扩容,如果满足,进行扩容后,重新计算hash值和下标
	然后获取当前已经存在的entry链表,然后新建的entry放在原链表的头部,存进数组中.
	*在put方法中，如果需要向table[]中添加Entry元素，会首先进行容量校验，如果容量已经达到了阀值，HashTable就会进行扩容处理rehash()
	*默认数组的长度是11, 扩容公式(oldsize * 2 + 1), key和value不能为null
	hashTable值不能为null的原因：会抛出控制原因   Hashtable使⽤的是安全失败机制（fail-safe），这种机制会使你此次读到的数据不一定是最新
	的数据。
           

hashMap值能为null的原因

3.ConcurrentHashMap的get：

key通过hash定位到具体segment，在通过一次Hash定位到具体的元素上。
           

4.ConcurrentHashMap的put：

1.计算出hashCode值
	2.判断是否需要初始化	 无初始化则调用initTable（）方法来进行初始化过程
	3.检查有无冲突，无冲突则使用cas进行保存，失败则进行自旋
	4.判断是否需要进行扩容
	5.不满足条件进行synchronized写入数据
	6.链表数量大于8进行红黑树转换
	7.调用addCount()统计size判断是否扩容
           

四、1.8进行了什么优化

改进一： 取消segments字段，直接采用transient volatile HashEntry<K,V>[] table保存数据，采用table数组元素作为锁，从而实现了对每一行数据 进行加锁，进			  一步减少并发冲突的概率。
	改进二： 将原先table数组＋单向链表的数据结构，变更为table数组＋单向链表＋红黑树的结构。查询的时间复杂度可以降低到O(logN)。
	JDK1.8的实现已经摒弃了Segment的概念，而是直接用Node数组+链表+红黑树的数据结构来实现，并发控制使用Synchronized和CAS来操作，整个看起来就
	是优化过且线程安全的HashMap，虽然在JDK1.8中还能看到Segment的数据结构，但是已经简化了属性，只是为了兼容旧版本。
	初始化操作并不是在构造函数实现的，而是在put操作中实现，当然ConcurrentHashMap还提供了其他的构造函数，有指定容量大小或者指定负载因子，跟
	HashMap一样
           

五、ConcurrentHashMap为什么是高并发的

1.7之前
ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。
不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap 
支持CurrencyLevel (Segment 数组数量)的线程并发。
每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。
就是说如果容量大小是16他的并发度就是16，可以同时允许16个线程操作16个Segment并且还是线程安全的。
他先定位到Segment，然后再进行put操作
1.8之后
其中抛弃了原有的 Segment 分段锁，采用了 CAS + synchronized 来保证并发安全性。
跟HashMap很像，也把之前的HashEntry改成了Node，但是作用不变，把值和next采用了volatile去修饰，保证了可用性，并且也引用了红黑树，在链表大于阈定值的时候会转换（默认是8）。
           

六、CAS

1.CAS原理：

CAS 是乐观锁的一种实现方式，是一种轻量级锁，JUC 中很多工具类的实现就是基于 CAS 的。

CAS 操作的流程如下图所示，线程在读取数据时不进行加锁，在准备写回数据时，比较原值是否修改，

若未被其他线程修改则写回，若已被修改，则重新执读读取流程。

这是一种乐观策略，认为并发操作并不总会发生。

2.CAS防止ABA：

一个线程把值改回了B，又来了一个线程把值改回了A，对于这个时候判断的线程，就发现

他的值还是A，所以他就不知道这个值到底有没有被⼈改过，其实很多场景如果只追求最后结果正确，

这是没关系的

解决方法

1.加版本号

2.加时间戳