HashMap的问题

HashMap 在并发扩容过程中，在 JDK7 中的实现可能会形成环形链表从而引发死循环，在JDK8中的实现又可能造成数据覆盖的问题。HashMap 是线程不安全的。

为了解决线程安全问题，对 Java 发展影响深远的 Doug Lea 编写了 ConcurrentHashMap 供开发者使用。

ConcurrentHashMap是Java并发编程（J.U.C, eg java.util.concurrent包的简称）下的一个HashMap的线程安全的类。

Unsafe类

Unsafe 是 JDK 提供的一个直接访问操作系统资源的工具类（底层c++实现），它可以直接分配内存，内存复制，copy，提供 CPU级别的 CAS 乐观锁等操作。

目的：增强Java语言直接操作底层资源的能力。

使用举例：类 User 有一个成员变量 name，new了一个对象 User 后，就知道了它在内存中的起始值，而成员变量 name 在对象中的位置偏移是固定的。这样通过这个起始值和这个偏移量就能够定位到 name 在内存中的具体位置。

Unsafe 提供了相应的方法获取静态成员变量、成员变量偏移量的方法，可以使用 Unsafe 直接更新内存中 name 的值。

ConcurrentHashMap 使用Unsafe类目的：避免使用高速缓冲区（CPU内）中的过期数据。

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
    return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}

static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,Node<K,V> c, Node<K,V> v) {
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

tabAt：Unsafe 类根据偏移量直接从内存中获取数据，避免了从高速缓冲区获得了过期数据。

casTabAt：通过 Unsafe 类直接操作内存，通过比较交换赋值，该操作不用加锁，所以可以提高操作效率

CAS

CAS 译为 Compare And Swap，它是乐观锁的一种实现。

假设内存值为 v，预期值为 e，想要更新成得值为 u，当且仅当内存值v等于预期值e时，才将v更新为u。

CAS 操作不需要加锁，比起加锁的方式， CAS 效率更高。

put方法（JDK 1.8）

1、根据 key 计算出 hash 值；

2、判断是否需要进行初始化；

3、定位到 Node，拿到首节点 f，判断首节点 f：

31. 如果为 null ，则通过 CAS 的方式尝试添加；

32. 如果为 f.hash = MOVED = -1 ，说明其他线程在扩容，参与一起扩容；

33. 如果都不满足 ，synchronized 锁住 f 节点，判断是链表还是红黑树，遍历插入

transfer扩容方法

支持多线程扩容，而且也没有进行加锁，所以实现有儿复杂。整个扩容操作分为两步：

1、构建一个nextTable，其大小为原来大小的两倍，这个步骤是在单线程环境下完成的。

2、将原来table里面的内容复制到nextTable中，这个步骤是允许多线程操作的，所以性能得到提升，减少了扩容的时间消耗。

PS：根据服务器CPU数量来决定每个线程负责的bucket数量，避免因为扩容的线程过多反而影响性能。分配任务和控制当前线程的任务进度，这部分是transfer()的核心逻辑

get 方法是否要加锁

不需要加锁。

因为 Node 的元素 value 和指针 next 是用 volatile 修饰的，在多线程环境下线程A修改节点的 value 或者新增节点的时候是对线程B可见的。

这也是它比其他并发集合比如 Hashtable、用 Collections.synchronizedMap()包装的 HashMap 效率高的原因之一。

不支持 key 或者 value 为 null 的原因

Doug用了反证法，先假定ConcurrentHashMap也可以存放value为null的值。那不管是HashMap还是ConcurrentHashMap调用map.get(key)的时候，如果返回了null，那么这个null，都有两重含义:

1、这个key从来没有在map中映射过。

2、这个key的value在设置的时候，就是null。

ConcurrentHashMap因为并发的原因，containsKey可能存在多个线程参与的情况，同时，作者认为HashMap有null值是公开邀请错误进容器，所以后来设计ConcurrentHashMap的时候就不支持了，设计理念的问题，源码如此。

JDK1.8中为什么使用内置锁 synchronized替换ReentrantLock？

1、在 JDK1.6 中，对 synchronized 锁的实现引入了大量的优化，并且 synchronized 有多种锁状态，会从无锁 -> 偏向锁 -> 轻量级锁 -> 重量级锁一步步转换。

2、减少内存开销 。假设使用可重入锁来获得同步支持，那么每个节点都需要通过继承 AQS 来获得同步支持。但并不是每个节点都需要获得同步支持的，只有链表的头节点（红黑树的根节点）需要同步，这带来了内存浪费。

链表和红黑树的转换

链表转化为红黑树，和HashMap一样，定位节点的 hash 算法简化会带来弊端，hash 冲突加剧，因此在链表节点数量大于 8（且数据总量大于等于 64）时，会将链表转化为红黑树进行存储。

HashTable

HashTable是一个线程安全的类，它使用synchronized来锁住整张Hash表来实现线程安全，即每次锁住整张表让线程独占，相当于所有线程进行读写时都去竞争一把锁，导致效率非常低下。

使用Collections.synchronizedMap方法，对方法进行加同步锁，本质也是对 HashMap 进行全表锁，使用mutex来加锁。