ConcurrentHashMap
写在前HashMap、ConcurrentHashMap，我在还没学java的时候就有耳闻。记得大三那会，去西二旗那面试，被问到HashMap，我也不会啊，只学了基本的面向对象、继承、基本类型啊，一问三不知…当然，面试不到10分钟，被叫回去等通知了… 时隔一年,哦不,是2年,我又回来了,这次谁再问我HashMap, 直接360度无死角的怼死他…
在这里, 我查阅不下20篇博客, 看了好几个老师讲源码, 自己也看了源码, 也来聊聊我脑子里存的干货。不过，码字这玩意太费神了，我就拿一些大佬们的过来记一笔，省的以后又要找，显得陌生。 我把ConcurrentHashMap & HashTable的知识点都整理了一下
16是2的幂，8也是，32也是，为啥偏偏选了16？关于HashMap的数组初始化大小的问题，源码上是：
/*** The default initial capacity - MUST be a power of two.*/static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16如何保证数组上的链表节点个数均匀分布，经过了几代的更新，第一代，利用key的hashCode值去与16做取模运算，范围不就落在0-15（数组下标）范围内了吗。后来觉得这个取模运算有点复杂，不好，换一个。于是第二代，用key的hashCode值和数组的长度n减一的结果进行与运算，即 key.hashCode & (n-1) 这样获得的结果,也在0-15(数组下标)范围内。后来觉得还是不靠谱，又让key的hashCode值的二进制结果 的高16位和低16位进行异或运算，得到异或的结果后再与n-1进行与运算，避免了hashCode值尾部的重复问题。
Hashmap中的链表大小超过八个时会自动转化为红黑树，当删除小于六时重新变为链表，为啥呢？根据泊松分布，在负载因子默认为0.75的时候，单个hash槽内元素个数为8的概率小于百万分之一，所以将7作为一个分水岭，等于7的时候不转换，大于等于8的时候才进行转换，小于等于6的时候就化为链表。
一般在多线程的场景，我都会使用好几种不同的方式去代替HashMap：使用Collections.synchronizedMap(Map)创建线程安全的map集合； Hashtable ConcurrentHashMap 不过出于线程并发度的原因，我都会舍弃前两者使用最后的ConcurrentHashMap，他的性能和效率明显高于前两者.
补充:
ArrayList, HashSet, HashMap,等Collections是非线程安全的,非常重要一、线程不安全类与写法1. 字符串拼接类StringBuilder和StringBuffer：经验证，使用线程池开启多线程对字符串进行5000次字符串拼接，可知，StringBuilder是非线程安全的，StringBuffer是线程安全的类。StringBuffer类的方法上，基本都添加了synchronized关键字，影响效率。一般拼接我都使用StringBuilder在方法里面定义局部变量，因为堆栈封闭，不涉及线程安全问题，性能提升。2.SimpleDateFormat类与DateTimeFormatter(是joda-time包中的类)SimpleDateFormat的对象时非线程安全的, 若多线程方法下使用它为全局变量时会报异常.所以要写在局部变量的方法里,避免线程安全带来的异常.DateTimeFormatter线程安全, DateTime.parse(“20200611”,dateTimeFormatter).todate().3.ArrayList, HashSet, HashMap,等Collections是非线程安全的,非常重要先检查再执行: 这种写法是不安全的, 因为判断的时候,值是相等,但是执行过程中是不安全的. 要确保是否涉及多线程的线程安全问题, 是否上锁,保证原子性.线程安全-同步容器ArrayList-> Vector, StackHashMap-> HashTable(key,value不能为null)Collections.synchronizedXXX(List Set Map)说明：同步容器不一定能真正做到线程安全.Vector在某些情况下会出现线程不安全的问题:Vector是线程同步的容器, 虽然所有方法都使用synchronized修饰,但可能会因为两个同步方法在调用顺序上出现线程安全问题(比如下图中,线程1和线程2同时判断了vector的大小,但是线程1先执行删除, 导致线程2无法获取删除掉的数据,造成数组越界的异常). 故,即便是线程安全的方法,在使用顺序上存在的问题,仍然可能会造成线程安全问题. 如下图单线程操作Vector对象, 增强for循环和Iterator循环中, 如果做删除操作,会出现异常的. 使用正常的for循环删除是ok的.
完了，还没开始讲正题。。。
哈希表 1. 哈希表介绍 哈希表就是一种以 键-值(key-indexed) 存储数据的结构，我们只要输入待查 找的值即 key，即可查找到其对应的值。哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数 组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。 这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。 2. 链式哈希表链式哈希表从根本上说是由一组链表构成。每个链表都可以看做是一个“桶”， 我们将所有的元素通过散列的方式放到具体的不同的桶中。插入元素时，首先将 其键传入一个哈希函数（该过程称为哈希键），函数通过散列的方式告知元素属 于哪个“桶”，然后在相应的链表头插入元素。查找或删除元素时，用同们的方 式先找到元素的“桶”，然后遍历相应的链表，直到发现我们想要的元素。因为 每个“桶”都是一个链表，所以链式哈希表并不限制包含元素的个数。然而，如 果表变得太大，它的性能将会降低。
3.应用场景我们熟知的缓存技术（比如 redis、memcached）的核心其实就是在内存中维 护一张巨大的哈希表，还有大家熟知的 HashMap、CurrentHashMap 等的应 用。
ConcurrentHashMap 与 HashMap 等的区别 1.HashMap我们知道 HashMap 是线程不安全的，在多线程环境下，使用 Hashmap 进行 put 操作会引起死循环，导致 CPU 利用率接近 100%，所以在并发情况下不能 使用 HashMap。
2.HashTableHashTable 和 HashMap 的实现原理几乎一样，差别无非是
HashTable 不允许 key 和 value 为 nullHashTable 是线程安全的 但是 HashTable 线程安全的策略实现代价却太大了，简单粗暴，get/put 所有 相关操作都是 synchronized 的，这相当于给整个哈希表加了一把大锁。 多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相 当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。 3.ConcurrentHashMap主要就是为了应对 hashmap 在并发环境下不安全而诞生的， ConcurrentHashMap 的设计与实现非常精巧，大量的利用了 volatile，final， CAS 等 lock-free 技术来减少锁竞争对于性能的影响。 我们都知道 Map 一般都是数组+链表结构（JDK1.8 该为数组+红黑树）。 ConcurrentHashMap 避免了对全局加锁改成了局部加锁操作，这样就极大地 提高了并发环境下的操作速度，由于 ConcurrentHashMap 在 JDK1.7 和 1.8 中的实现非常不同，接下来我们谈谈 JDK 在 1.7 和 1.8 中的区别。
JDK1.7 版本的 CurrentHashMap 的实现原理在 JDK1.7 中 ConcurrentHashMap 采用了数组+Segment+分段锁的方式实 现
1.Segment(分段锁)ConcurrentHashMap 中的分段锁称为 Segment，它即类似于 HashMap 的结 构，即内部拥有一个 Entry 数组，数组中的每个元素又是一个链表,同时又是一 个 ReentrantLock（Segment 继承了 ReentrantLock）。
2.内部结构ConcurrentHashMap 使用分段锁技术，将数据分成一段一段的存储，然后给 每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的 数据也能被其他线程访问，能够实现真正的并发访问。 如下图是 ConcurrentHashMap 的内部结构图： 从上面的结构我们可以了解到，ConcurrentHashMap 定位一个元素的过程需 要进行两次 Hash 操作。 第一次 Hash 定位到 Segment，第二次 Hash 定位到元素所在的链表的头部。
3.该结构的优劣势 坏处： 这一种结构的带来的副作用是 Hash 的过程要比普通的 HashMap 要长好处： 写操作的时候可以只对元素所在的 Segment 进行加锁即可，不会影响到其他的 Segment，这样，在最理想的情况下，ConcurrentHashMap 可以最高同时支 持 Segment 数量大小的写操作（刚好这些写操作都非常平均地分布在所有的 Segment 上）。所以，通过这一种结构，ConcurrentHashMap 的并发能力可以大大的提高。
JDK1.8 版本的 CurrentHashMap 的实现原理JDK8 中 ConcurrentHashMap 参考了 JDK8 HashMap 的实现，采用了数组+ 链表+红黑树的实现方式来设计，内部大量采用 CAS 操作，这里我简要介绍下 CAS。
CAS 是 pare and swap 的缩写，即我们所说的比较交换。cas 是一种基于 锁的操作，而且是乐观锁。在 java 中锁分为乐观锁和悲观锁。悲观锁是将资源锁住，等一个之前获得锁的线程释放锁之后，下一个线程才可以访问。而乐观锁 采取了一种宽泛的态度，通过某种方式不加锁来处理资源，比如通过给记录加 version 来获取数据，性能较悲观锁有很大的提高。
CAS 操作包含三个操作数 —— 内存位置（V）、预期原值（A）和新值(B)。 如果内存地址里面的值和 A 的值是一样的，那么就将内存里面的值更新成 B。 CAS 是通过无限循环来获取数据的，若果在第一轮循环中，a 线程获取地址里面 的值被 b 线程修改了，那么 a 线程需要自旋，到下次循环才有可能机会执行。
JDK8 中彻底放弃了 Segment 转而采用的是 Node，其设计思想也不再是 JDK1.7 中的分段锁思想。
Node：保存 key，value 及 key 的 hash 值的数据结构。其中 value 和 next 都用 volatile 修饰，保证并发的可见性。 Java8 ConcurrentHashMap 结构基本上和 Java8 的 HashMap 一样，不过 保证线程安全性。
在 JDK8 中 ConcurrentHashMap 的结构，由于引入了红黑树，使得ConcurrentHashMap 的实现非常复杂，我们都知道，红黑树是一种性能非常 好的二叉查找树，其查找性能为 O（logN），但是其实现过程也非常复杂，而 且可读性也非常差，Doug Lea 的思维能力确实不是一般人能比的，早期完全采 用链表结构时 Map 的查找时间复杂度为 O（N），JDK8 中 ConcurrentHashMap 在链表的长度大于某个阈值的时候会将链表转换成红黑树进一步提高其查找性 能。
总结其实可以看出 JDK1.8 版本的 ConcurrentHashMap 的数据结构已经接近 HashMap，相对而言，ConcurrentHashMap 只是增加了同步的操作来控制并 发，从 JDK1.7 版本的 ReentrantLock+Segment+HashEntry，到 JDK1.8 版 本中 synchronized+CAS+HashEntry+红黑树。
1.数据结构： 取消了 Segment 分段锁的数据结构，取而代之的是数组+链表+ 红黑树的结构。 2.保证线程安全机制： JDK1.7 采用 segment 的分段锁机制实现线程安全，其中 segment 继承自 ReentrantLock。JDK1.8 采用 CAS+Synchronized 保证线程 安全。 3.锁的粒度： 原来是对需要进行数据操作的 Segment 加锁，现调整为对每个数 组元素加锁（Node）。 4.链表转化为红黑树: 定位结点的 hash 算法简化会带来弊端,Hash 冲突加剧,因 此在链表节点数量大于 8 时，会将链表转化为红黑树进行存储。 5.查询时间复杂度： 从原来的遍历链表 O(n)，变成遍历红黑树 O(logN)。
ConcurrentHashMap