1.1 map的分类和常见的情况
java为数据结构中的映射定义了一个接口java.util.Map；它有四个实现类，分别是HashMap、Hashtable、LinkedHashMap和TreeMap。
Map主要用于存储键值对，根据键得到值，因此不允许键重复（重复了覆盖了），但允许值重复。
1.1.1 HashMap
HashMap是一个最常用的Map，他根据键的HashCode值存储数据，根据键可以直接获取它的值，具有很快的访问速度，遍历时，取得数据的顺序完全是随机的。HashMap最多只允许一条记录的键为Null；允许多条记录的值为Null；HashMap不支持线程的同步，即任一时刻可以有多个线程同时写HashMap；可能会导致数据的不一致。如果需要同步，可以用Collections.synchronizedMap方法使HashMap具有同步的能力，或者使用ConcurrentHashMap。
1.1.2 Hashtable
Hashtable与HashMap类似，它继承自Dictionary类，不同的是：它不允许记录的键或者值为Null。它支持线程的同步，即任一时刻只有一个线程能写Hashtable，因此也导致了HashTable在写入时会比较慢。
1.1.3 LinkedHashMap
LinkedHashMap时HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的。也可以在构造时带参数按照应用次数排序。在遍历的时候会比HashMap慢，不过有种情况例外，当HashMap容量很大，实际数据较少时，遍历起来可能会比LinkedHashMap慢，因为LinkedHashMap的遍历速度只和实际数据有关，和容量无关，而HashMap的遍历速度它的容量有关。
1.1.4 TreeMap
TreeMap实现SortMap接口，能够把它保存的记录根据键排序，默认是案件值的升序排列，也可以指定排序的比较器，当用Iterator遍历TreeMap时，得到的记录是排过序的。
一般情况下我们用的最多的是HashMap，在Map中插入、删除和定位元素，HashMap是最好的选择。但如果要按照自然顺序或自定义顺序遍历键，那么TreeMap会更好。如果需要输出的顺序和输入的相同，那么用LinkedHashMap可以实现，它还可以按照读取顺序来排列。
1.2 HashMap为什么线程不安全
1.2.1 JDK1.7中的HashMap
- 扩容造成数据丢失
- 扩容造成死循环
我们都知道HashMap是线程不安全的，在多线程环境中不建议使用，但是其线程不安全主要体现在什么地方呢？
下面举两个可能出现线程不安全的地方。
- put的时候导致的多线程数据不一致。
比如有两个线程A和B，首先A希望插入一个key-value对到HashMap中，首先计算记录所要落到的桶的索引坐标index，然后获取到该桶里面的链表头结点，此时线程A的时间片用完了，而此时线程B被调度得以执行，和线程A一样执行，只不过线程B成功将记录插到了桶里面，假设线程A插入的记录计算出来的桶索引和线程B要插入的记录计算出来的桶索引是一样的，那么当线程B成功插入之后，线程A再次被调度运行时，它依然持有过期的链表头但是它并不知道，它认为它还应该这样做，因此就覆盖了线程B插入的记录，这样线程B插入的记录就凭空消失了，造成了数据不一致。 - 另外一个比较明显的线程不安全的问题是HashMap的get操作可能因为resize而引起死循环
下面是进行resize时调用的transfer()方法的代码，然后在多线程环境下，假设有两个线程A和B都在进行put操作。线程A在执行到transfer函数中第11行代码处挂起。
void transfer(Entry[] newTable,boolean rehash){
int newCapacity = newTable.length;
for(Entry<K,V> e : table){
while(null != e){
Entry<K,V> next = e.next;
if(rehash){
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash,newCapacity);
e.next = newTable[i];
newTable[i] = e; //线程A在这里挂起
e = next;
}
}
}
线程A挂起后，此时线程B正常执行，并完成resize操作，由于线程B已经执行完毕，根据Java内存模型，现在newTable和table中的Entry都是主存中最新值。
1.2.2 JDK1.8中的HaspMap
在jdk1.8中对HashMap进行了优化，在发生hash碰撞，不再采用头插法方式，而是直接插入链表尾部，因此不会出现环形链表的情况，但是在多线程的情况下仍然不安全。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) // 如果没有hash碰撞则直接插入元素
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
这是jdk1.8中HashMap中put操作的主函数， 注意第6行代码，如果没有hash碰撞则会直接插入元素。如果线程A和线程B同时进行put操作，刚好这两条不同的数据hash值一样，并且该位置数据为null，所以这线程A、B都会进入第6行代码中。假设一种情况，线程A进入后还未进行数据插入时挂起，而线程B正常执行，从而正常插入数据，然后线程A获取CPU时间片，此时线程A不用再进行hash判断了，问题出现：线程A会把线程B插入的数据给覆盖，发生线程不安全。
1.3 HashMap在多线程环境下存在线程安全问题，如何处理？
一般在多线程的场景，我都会使用好几种不同的方式去代替：
- 使用Collections.synchronizedMap(Map)创建线程安全的map集合；
- Hashtable
- ConcurrentHashMap
不过出于线程并发度的原因，都会舍弃前两者使用最后的ConcurrentHashMap，他的性能和效率明显高于前两者。
1.3.1 Collections.synchronizedMap是怎么实现线程安全的
在SynchronizedMap内部维护了一个普通对象Map，还有排斥锁mutex，代码如下:
private static class SynchronizedMap<K,V> implements Map<K,V>, Serializable{
private static final long serialVersionUID = 1978198479659022715L;
private final Map<K,V> m;
final Object mutex;
SynchronizeMap(Map<K,V> m){
this.m = Objects.requireNonNull(m);
mutex = this;
}
SynchronizeMap(Map<K,V> m, Object mutex){
this.m = m;
this.mutex = mutex;
}
collections.synchronizedMap(new HashMap<>(16));
我们在调用这个方法的时候就需要传入一个Map，可以看到有两个构造器，如果你传入了mutex参数，则将对象排斥锁赋值为传入的对象。
如果没有，则将对象排斥锁赋值为this，即调用synchronizedMap的对象，就是上面的Map。
创建出synchronizedMap之后，再操作map的时候，就会对方法上锁。
1.3.2 Hashtable效率低的原因
跟HashMap相比Hashtable是线程安全的，适合在多线程的情况下使用，但是效率可不太乐观。
Hashtable在对数据操作的时候都会上锁，所以效率比较低下。源码如下：
public synchronized V get(Object key){
Entry<?,?> tab[] = table;
int hash = key.hashCode();
}
HashMap和Hashtable的不同点：
- 键值要求 ：Hashtable 是不允许键或值为 null 的，HashMap 的键值则都可以为 null。
- 实现方式不同：Hashtable 继承了 Dictionary类，而 HashMap 继承的是 AbstractMap 类。
- 初始化容量不同：HashMap 的初始容量为：16，Hashtable 初始容量为：11，两者的负载因子默认都是：0.75。
- 扩容机制不同：当现有容量大于总容量 * 负载因子时，HashMap 扩容规则为当前容量翻倍，Hashtable 扩容规则为当前容量翻倍 + 1。
- 迭代器不同：HashMap 中的 Iterator 迭代器是 fail-fast 的，而 Hashtable 的 Enumerator 不是 fail-fast 的。
快速失败（fail—fast）是java集合中的一种机制， 在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。
1.3.3 ConcurrentHashMap
1.3.3.1 它在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 只能保证对单次读/写的原子性。i++ 这种操作不能保证原子性。
1.3.3.2 它在1.8中的数据结构：
其中抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。
跟HashMap很像，也把之前的HashEntry改成了Node，但是作用不变，把值和next采用了volatile去修饰，保证了可见性，并且也引入了红黑树，在链表大于一定值的时候会转换（默认是8）。
1.3.3.3 并发度高的原因
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值的存取操作？
ConcurrentHashMap在进行put操作
- 根据 key 计算出 hashcode 。
- 判断是否需要进行初始化。
- 即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。
CAS 是乐观锁的一种实现方式，是一种轻量级锁，JUC 中很多工具类的实现就是基于 CAS 的。
- 如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。
- 如果都不满足，则利用 synchronized 锁写入数据。
- 如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。
ConcurrentHashMap的get操作
ConcurrentHashMap 的 get 方法是非常高效的，因为整个过程都不需要加锁。
- 根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。
- 如果是红黑树那就按照树的方式获取值。
- 都不满足那就按照链表的方式遍历获取值。
1.8 在 1.7 的数据结构上做了大的改动，采用红黑树之后可以保证查询效率（从O(n)变成了O(logn)），甚至取消了 ReentrantLock 改为了 synchronized，这样可以看出在新版的 JDK 中对 synchronized 优化是很到位的。
