HashMap

注：底层是由数组和链表组合构成的数据结构，数组中每一个元素都是key-value形式且数组长度是有限的，在有限的长度里面我们使用哈希，哈希本身就存在概率性，就存在hash冲突问题，出现冲突时采用链表的方式把hash冲突的元素链接起来，每一个节点都会保存自身的hash、key、value、以及下个节点。
注：hashmap初始化大小长度为16（实现均匀分布）

HsahMap扩容机制

• Hsah规则

 index = HashCode（Key） & （Length - 1）//key关键字，length数组的长度

• 属性

Capacity//HashMap当前长度。
LoadFactor//负载因子，默认值0.75f。

• 步骤
  扩容：创建一个新的Entry空数组，长度是原数组的2倍。（扩容会导致数组长度改变，hash规则改变，所以重新hash）。
  注：当数组容量>7时会转换为红黑树存储，当<7时会从红黑树转换为数组
  ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。

• 链表插入方式：1.8之前采用的头插法，1.8开始采用尾插(改用尾插，是因为重新hash时使用头插方法，有可能会造成无限循环)

Hashtable

跟HashMap相比Hashtable是线程安全的，适合在多线程的情况下使用，但是效率可不太乐观。它在对数据操作的时候都会上锁，所以效率比较低下。

Hashtable和HashMap的区别

• Hashtable 是不允许键或值为 null 的，HashMap 的键值则都可以为 null。
  这是因为Hashtable使用的是安全失败机制（fail-safe：采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。），这种机制会使你此次读到的数据不一定是最新的数据。如果你使用null值，就会使得其无法判断对应的key是不存在还是为空，因为你无法再调用一次contain(key）来对key是否存在进行判断，ConcurrentHashMap同理。
• 实现方式不同：Hashtable 继承了 Dictionary类，而 HashMap 继承的是 AbstractMap 类。
  Dictionary 是 JDK 1.0 添加的，貌似没人用过这个，我也没用过。
• 初始化容量不同：HashMap 的初始容量为：16，Hashtable 初始容量为：11，两者的负载因子默认都是：0.75。
• 扩容机制不同：当现有容量大于总容量 * 负载因子时，HashMap 扩容规则为当前容量翻倍，Hashtable 扩容规则为当前容量翻倍 + 1。
• 迭代器不同：HashMap 中的 Iterator 迭代器是 fail-fast（快速失败机制：在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。（这个过程包括多线程下的修改，也包括单线程的修改）） 的，而 Hashtable 的 Enumerator 不是 fail-fast 的。当其他线程改变了HashMap 的结构，如：增加、删除元素，抛出ConcurrentModificationException 异常，而 Hashtable 则不会。

ConcurrentHashMap

注：也是由数组+链表的形式实现的，数组元素为segment内部类

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;
}

volatile：

• 保证了不同线程对这个变量进行操作时的可见性，即一个线程修改了某个变量的值，这新值对其他线程来说是立即可见的。（实现可见性）
• 禁止进行指令重排序。（实现有序性）
• volatile 只能保证对单次读/写的原子性。i++ 这种操作不能保证原子性。

ConcurrentMap高并发：
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操作。

• 首先第一步的时候会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用 scanAndLockForPut() 自旋获取锁。
• 尝试自旋获取锁。
• 如果重试的次数达到了 MAX_SCAN_RETRIES 则改为阻塞锁获取，保证能获取成功。

get操作

• 将 Key 通过 Hash 之后定位到具体的 Segment ，再通过一次 Hash 定位到具体的元素上。
• 由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的，保证了内存可见性，所以每次获取时都是最新值。
• ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需要加锁。

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

ConcurrentHashMap 1.8之后的put操作

• 根据 key 计算出 hashcode 。
• 判断是否需要进行初始化。
• 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
• 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
• 如果都不满足，则利用 synchronized 锁写入数据。
• 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。

CAS

CAS 是乐观锁的一种实现方式，是一种轻量级锁，JUC 中很多工具类的实现就是基于 CAS 的。
CAS 操作的流程如下图所示，线程在读取数据时不进行加锁，在准备写回数据时，比较原值是否修改，若未被其他线程修改则写回，若已被修改，则重新执行读取流程。
这是一种乐观策略，认为并发操作并不总会发生。

• 解决ABA问题：在查询的数据中加入版本或者时间戳

1.8之后的synchronized

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

get获取数据操作

• 根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。
• 如果是红黑树那就按照树的方式获取值。
• 就不满足那就按照链表的方式遍历获取值。