ConcurrentHashMap 底层具体实现知道吗？实现原理是什么？
JDK1.7
首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。
在JDK1.7中，ConcurrentHashMap采用Segment + HashEntry的方式进行实现，结构如下：
一个 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和 HashMap类似，是一种数组和链表结构，一个 Segment 包含一个HashEntry 数组，每个 HashEntry 是一个链表结构的元素，每个 Segment 守护着一个 HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment的锁。
Segment的大小默认是16，也就是说 ConcurrentHashMap 有 16 个 Segments，所以理论上，这个时候，最多可以同时支持 16 个线程并发写，只要它们的操作分别分布在不同的 Segment 上。这个值可以在初始化的时候设置为其他值，但是一旦初始化以后，它是不可以扩容的。再具体到每个 Segment 内部，其实每个 Segment 很像之前介绍的 HashMap，不过它要保证线程安全，所以处理起来要麻烦些。
- 该类包含两个静态内部类 HashEntry 和 Segment ；前者用来封装映射表的键值对，后者用来充当锁的角色；
- Segment 是一种可重入的锁 ReentrantLock，每个 Segment 守护一个HashEntry 数组里得元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 锁。
JDK1.8
在JDK1.8中，放弃了Segment臃肿的设计，取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现，synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲突，就不会产生并发，效率又提升N 倍！！！。
看插入元素过程（建议去看看源码）：
如果相应位置的Node还没有初始化，则调用CAS插入相应的数据；
1 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { 2 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) 3 break; // no lock when adding to empty bin 4 }
如果相应位置的Node不为空，且当前该节点不处于移动状态，则对该节点加synchronized锁，如果该节点的hash不小于0，则遍历链表更新节点或插入新节点；
1 if (fh >= 0) { 2 binCount = 1; 3 for (Node<K,V> e = f;; ++binCount) { 4 K ek; 5 if (e.hash == hash && 6 ((ek = e.key) == key || 7 (ek != null && key.equals(ek)))) { 8 oldVal = e.val; 9 if (!onlyIfAbsent) 10 e.val = value; 11 break; 12 } 13 Node<K,V> pred = e; 14 if ((e = e.next) == null) { 15 pred.next = new Node<K,V>(hash, key, value, null); 16 break;
- 如果该节点是TreeBin类型的节点，说明是红黑树结构，则通过 putTreeVal方法往红黑树中插入节
点；如果binCount不为0，说明put操作对数据产生了影响，如果当前链表的个数达到8个，则通过
treeifyBin方法转化为红黑树，如果oldVal不为空，说明是一次更新（覆盖）操作，没有对元素个数产生影响，则直接返回旧值； - 如果插入的是一个新节点，则执行addCount()方法尝试更新元素个数 baseCount；
HashTable，HashMap，TreeMap区别？
- HashTable线程同步，HashMap，TreeMap非线程同步。
- HashTable，TreeMap不允许<键,值>有空值，HashMap允许<键,值>有空值。
- HashTable中hash数组的默认大小是11，增加方式的old*2+1，HashMap中hash数组的默认大小
是16，增长方式一定是2的指数倍。 - TreeMap能够把它保存的记录根据键排序，默认是按升序排序，因此如果你的键需要有序，建议使用TreeMap代替HashMap。
HashMap的扩容因子（HashMap 什么时候进行扩容呢）重点！
扩容因子：尺寸/容量。空表的负载因子是0，半满表的负载因子是0.5，以此类推。负载轻的表产生冲突的可能性小，因此对于插入和查找都是最理想的状态(但是会减慢使用迭代器遍历的过程)。HashMap 与HashSet 都允许指定负载因子的构造器，表示当负载情况达到该负载因子的水平时，容器将会自动扩容(增加桶位数)，实现方式时使容量大致加倍，并重新将现有对象分布到新的桶位集中(这个过程被称为再散列)。
当HashMap中的元素越来越多的时候，碰撞的几率也就越来越高（因为数组的长度是固定的），所以为了提高查询的效率，就要对HashMap的数组进行扩容，数组扩容这个操作也会出现在ArrayList中，所以这是一个通用的操作，很多人对它的性能表示过怀疑，不过想想我们的“均摊”原理，就释然了，而在hashmap数组扩容之后，最消耗性能的点就出现了：原数组中的数据必须重新计算其在新数组中的位置，并放进去，这就是resize。
那么HashMap什么时候进行扩容呢？当hashmap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16 * 0.75=12的时候，就把数组的大小扩展为2 *16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。比如说，我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适，不过上面已经说过，即使是1000，hashmap也自动会将其设置为1024。 但是new HashMap(1024)还不是更合适的，因为0.75 * 1024 < 1000, 那么再次插入数据的时候就可能发生数组扩容了，也就是说为了让0.75 * size > 1000,我们必须这样new HashMap(2048)才最合适，既考虑了&的问题，也避免了resize的问题。
加载因子（扩容因子）为何默认是0.75?
- 在空间占用与查询时间之间取得了较好的权衡
- 大于这个值，空间节省了，但是链表可能过长就会影响性能
- 小于这个值，冲突减少了，但是扩容就会比较频繁，空间占用多并且扩容也会消耗性能
多线程修改HashMap
多线程同时写入，同时执行扩容操作，多线程扩容可能死锁、丢数据；可以对HashMap 加入同步锁Collections.synchronizedMap(hashMap)，但是效率很低，因为该锁是互斥锁，同一时刻只能有一个线程执行读写操作，这时候应该使用ConcurrentHashMap
注意：在使用Iterator遍历的时候，LinkedHashMap会产生java.util.ConcurrentModificationException
扩展HashMap增加双向链表的实现，号称是最占内存的数据结构。支持iterator()时按Entry的插入 顺序来排序(但是更新不算，如果设置accessOrder属性为true，则所有读写访问都算)。实现上是
在Entry上再增加属性before/after指针，插入时把自己加到Header Entry的前面去。如果所有读
写访问都要排序，还要把前后Entry的before/after拼接起来以在链表中删除掉自己。
多线程下使用HashMap会有什么问题？
扩容死链(JDK1.7)
数据错乱(JDK1.7/8)
多线程情况下，可能出现两个线程同时插入的数据要插入到同一个索引处，也就是key不同，但是hashcode相同的情况，然后可能出现两个线程都进入到了为这个为同一个索引添加新节点的情况，那么先来的数据先赋值完毕后，另一个数据再赋值，那么就会出现覆盖问题。
这里我使用IDEA的debug并且设定进入断点的条件，来模拟这种情况的发生
下面是线程1，线程1插入的数据的索引为1
下面是线程2，线程2要插入的数据的索引也为1
我让线程2先完成数据的插入，那么此时线程1中的情况如下
之后我让线程1执行完毕插入操作，那么此时的情况如下，出现了数据的覆盖
可以发现一样的代码，但是只有一个key的数据了，这就是数据错乱
为何要用红黑树？
链表在链表长度过长的时候，遍历的时间复杂度为O(n)，而红黑树的时间复杂度为O（logn），因此在链表长度过长的时候使用红黑树可以加快遍历速度。
为何不一上来就树化？
这是基于时间和空间的综合考虑。
时间上，在Hash冲突比较小的时候，即使转换为了红黑树，也不会有效率上多大的提升，反倒会导致在put的时候由于需要进行红黑树的旋转算法，所以反倒会导致时间效率降低。
红黑树的节点类型为TreeNode，而链表的节点类型为Node，红黑树消耗的空间更多，需要维护更多的指针，对内存的占用更大。
而HashMap之所以选择红黑树而不是普通的二叉搜索树，是因为普通的二叉搜索树在特殊的情况它会变成一个倾斜的情况，最差的情况会变成一个类似于链表的情况，那么查找效率就会退化为和链表差不多。而红黑树他是可以防止这种退化的，并且它又不像其他的完全的平衡二叉树那样有严格的平衡条件，因此红黑树它的插入效率又比那种完全的平衡二叉树要高，因此选择红黑树可以防止极端环境下的退化，又可以兼顾查询和插入的效率。
树化阈值为何是8？
其实，一个链表的长度能超过8的概率非常低。
红黑树用来避免DoS攻击，防止链表超长时性能下降，树化应当是偶然情况，
hash表的查找，更新的时间复杂度是0(1)，而红黑树的查找，更新的时间复杂度是0(log2n)，TreeNode占用空间也比普通Node的大，如非必要，尽量还是使用链表。
hash值如果足够随机，则在 hash表内按泊松分布，在负载因子0.75的情况下，长度超过8的链表出现概率是0.00000006，选择8就是为了让树化几率足够小.
何时会树化？何时会退化为链表？
树化有两个条件：链表长度超过树化阈值并且数组容量大于等于64。
由于树化的开销很大，因此能使用扩容的方式解决链表长度过长的话，是不会树化的。
退化情况1：在扩容的时候如果拆分了树，使得树中元素个数小于等于6，那么红黑树会退化为链表。
退化情况2：remove树中的节点的时候，在remove之前，若root，root.left，root.right，root.left.left中有一个为null，也会退化为链表，然后再移除这个节点。
