一、ConcurrentHashMap数据结构

ConcurrentHashMap 底层是基于 数组 + 链表 组成的，不过在 jdk1.7 和 1.8 中具体实现稍有不同。
在1.7中数据结构
在这里插入图片描述
是由 Segment 数组、HashEntry 链表组成。它和HashMap 一样，仍然是数组加链表。
Segment 是 ConcurrentHashMap 的一个内部类，主要的组成如下：

static final class Segment<K,V> extends ReentrantLock implements
Serializable { 
private static final long serialVersionUID = 2249069246763182397L;
// 和 HashMap 中的 HashEntry 作用一样，真正存放数据的桶
transient volatile HashEntry<K,V>[] table;
transient int count;
// 记得快速失败（fail—fast）么？
transient int modCount;
// 大小
transient int threshold;
// 负载因子
final float loadFactor;
}

HashEntry跟HashMap差不多的，但是不同点是，他使用volatile去修饰了他的数据Value还有下一个节点next。
volatile的特性：
(1)保证了不同线程对这个变量进行操作时的可见性，即一个线程修改了某个变量的值，这新值对其它线程来说是立即可见的。（实现可见性）
(2)禁止进行指令重排序。（实现有序性）
(3)volatile 只能保证对单次读/写的原子性。i++ 这种操作不能保证原子性。

二、那你能说说他并发度高的原因么？

原理上来说，ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。

分段锁：首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

不会像 HashTable 那样不管是 put 还是 get 操作都需要做同步处理，理论上 ConcurrentHashMap支持CurrencyLevel (Segment 数组数量)的线程并发。
每当每个线程占用锁访问一个 Segment 时，不会影响到其他Segment。
就是说如果容量大小是16他的并发度就是16，可以同时允许16个线程操作16个Segment而且还是线程安全的。

public V put(K key, V value) { 
    Segment<K,V> s;
    if (value == null)
    throw new NullPointerException();//这就是为啥他不可以put null值的原因
    int hash = hash(key);
    int j = (hash >>> segmentShift) & segmentMask;
    if ((s = (Segment<K,V>)UNSAFE.getObject
        (segments, (j << SSHIFT) + SBASE)) == null)
        s = ensureSegment(j);
    return s.put(key, hash, value, false);
}

他先定位到Segment，然后再进行put操作。
我们看看他的put源代码，你就知道他是怎么做到线程安全的了，关键句子我注释了。

final V put(K key, int hash, V value, boolean onlyIfAbsent) { 
        //将当前Segment中的table通过key的hashcode定位到HashEntry
            HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
            V oldValue;
            try { 
                HashEntry<K,V>[] tab = table;
                int index = (tab.length - 1) & hash;
                HashEntry<K,V> first = entryAt(tab, index);
                for (HashEntry<K,V> e = first;;) { 
                    if (e != null) { 
                        K k;
 //遍历该HashEntry，如果不为空则判断传入的key和当前遍历的key是否相等，相等则覆盖旧的value。
                        if ((k = e.key) == key ||
                            (e.hash == hash && key.equals(k))) { 
                            oldValue = e.value;
                            if (!onlyIfAbsent) { 
                                e.value = value;
                                ++modCount;
                            }
                            break;
                        }
                        e = e.next;
                    }
                    else { 
                 // 不为空则需要新建一个HashEntry并加入到Segment中，同时会先判断是否需要扩容。
                        if (node != null)
                            node.setNext(first);
                        else
                            node = new HashEntry<K,V>(hash, key, value, first);
                        int c = count + 1;
                        if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                            rehash(node);
                        else
                            setEntryAt(tab, index, node);
                        ++modCount;
                        count = c;
                        oldValue = null;
                        break;
                    }
                }
            } finally { 
               //释放锁
                unlock();
            }
            return oldValue;
        }

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

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

三、ConcurrentHashMap 的get的逻辑呢？

get 逻辑比较简单，只需要将 Key 通过 Hash 之后定位到具体的 Segment ，再通过一次 Hash 定位到具体的元素上。

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

四、你有没有发现1.7虽然可以支持每个Segment并发访问，但是还是存在一些问题？

ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需要加锁。
因为基本上还是数组加链表的方式，我们去查询的时候，还得遍历链表，会导致效率很低，这个跟jdk1.7的HashMap是存在的一样问题，所以他在jdk1.8完全优化了。

五、那你再跟我聊聊jdk1.8他的数据结构是怎么样子的呢？

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

跟HashMap很像，也把之前的HashEntry改成了Node，但是作用不变，把值和next采用了volatile去修饰，保证了可见性，并且也引入了红黑树，在链表大于一定值的时候会转换（默认是8）。

六、同样的，你能跟我聊一下他值的存取操作么？以及是怎么保证线程安全的？

ConcurrentHashMap在进行put操作的还是比较复杂的，大致可以分为以下步骤：
(1)根据 key 计算出 hashcode 。
(2)判断是否需要进行初始化。为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
(3)如果当前位置的 hashcode == MOVED == -1，则需要进行扩容。
(4)如果都不满足，则利用 synchronized 锁写入数据。
(5)如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。
在这里插入图片描述

七、你在上面提到CAS是什么？自旋又是什么？

CAS 是乐观锁的一种实现方式，是一种轻量级锁，JUC 中很多工具类的实现就是基于 CAS 的。CAS原理机制分析
CAS 操作的流程如下图所示，线程在读取数据时不进行加锁，在准备写回数据时，比较原值是否修改，若未被其他线程修改则写回，若已被修改，则重新执行读取流程。
在这里插入图片描述
这是一种乐观策略，认为并发操作并不总会发生。
还是不明白？那我再说明下，乐观锁在实际开发场景中非常常见，大家还是要去理解。

就比如我现在要修改数据库的一条数据，修改之前我先拿到他原来的值，然后在SQL里面还会加个判断，原来的值和我手上拿到的他的原来的值是否一样，一样我们就可以去修改了，不一样就证明被别的线程修改了你就return错误就好了。
SQL伪代码大概如下：

update a set value = newValue where value = #{oldValue}

oldValue就是我们执行前查询出来的值

八、CAS就一定能保证数据没被别的线程修改过么？什么是ABA？那怎么解决ABA问题？

并不是的，比如很经典的ABA问题，CAS就无法判断了。
就是说来了一个线程把值改回了B，又来了一个线程把值又改回了A，对于这个时候判断的线程，就发现他的值还是A，所以他就不知道这个值到底有没有被人改过，其实很多场景如果只追求最后结果正确，这是没关系的。

但是实际过程中还是需要记录修改过程的，比如资金修改什么的，你每次修改的都应该有记录，方便回溯。

用版本号去保证就好了，就比如说，我在修改前去查询他原来的值的时候再带一个版本号，每次判断就连值和版本号一起判断，判断成功就给版本号加1。

update a set value = newValue ，vision = vision + 1 where value = #{oldValue} and vision = #{vision}

判断原来的值和版本号是否匹配，中间有别的线程修改，值可能相等，但是版本号100%不一样。除了版本号还有别的方法保证么？

其实有很多方式，比如时间戳也可以，查询的时候把时间戳一起查出来，对的上才修改并且更新值的时候一起修改更新时间，这样也能保证，方法很多但是跟版本号都是异曲同工之妙，看场景大家想怎么设计吧。

CAS性能很高，但是我知道synchronized性能可不咋地，为啥jdk1.8升级之后反而多了synchronized？

synchronized之前一直都是重量级的锁，但是后来java官方是对他进行过升级的，他现在采用的是锁升级的方式去做的。

针对 synchronized 获取锁的方式，JVM 使用了锁升级的优化方式，就是先使用偏向锁优先同一线程然后再次获取锁，如果失败，就升级为 CAS 轻量级锁，如果失败就会短暂自旋，防止线程被系统挂起。最后如果以上都失败就升级为重量级锁。
所以是一步步升级上去的，最初也是通过很多轻量级的方式锁定的。