目录
Map涉及的集合框架体系图
什么是 Map
Map:双列数据，存储key-value对的数据 —类似于高中的函数：y = f(x)
存储结构的理解：
- Map中的key:无序的、不可重复的，使用Set存储所的key key所在的类要重写equals()和hashCode() （以HashMap为例)
- Map中的value:无序的、可重复的，使用Collection存储所有的value —>value所在的类要重写equals()
- 一个键值对：key-value构成了一个Entry对象。
- Map中的entry:无序的、不可重复的，使用Set存储所的entry
HashMap
基本特点
- 允许使用null作为key或value（源码写的，没有为什么，别问。）
- 线程不安全，运行效率高。（源码没加锁）
- HashMap 实现了Serializable接口，因此它支持序列化，实现了Cloneable接口，能被克隆。
- 实现原理基于哈希表，只是说1.7和1.8 解决冲突的方式不同
HashMap在jdk1.7中实现原理：
HashMap map = new HashMap():
在实例化以后，底层创建了长度是16的一维数组Entry[] table。
put
关于put的执行流程（再次之前可能执行过多次的put）
首先，调用key1所在类的hashCode()计算key1哈希值，此哈希值经过某种算法计算以后，得到在Entry数组中的存放位置。
如果此位置上的数据为空，此时的key1-value1添加成功。 ----情况1
如果此位置上的数据不为空，(意味着此位置上存在一个或多个数据(以链表形式存在)),比较key1和已经存在的一个或多个数据的哈希值：
- 如果key1的哈希值与已经存在的数据的哈希值都不相同，此时key1-value1添加成功。----情况2
如果key1的哈希值和已经存在的某一个数据(key2-value2)的哈希值相同，继续比较：调用key1所在类的equals(key2)方法比较：- 如果equals()返回false:此时key1-value1添加成功。----情况3
如果equals()返回true:使用value1替换value2。补充：关于情况2和情况3：此时key1-value1和原来的数据以链表的方式存储。 在不断的添加过程中，会涉及到扩容问题，当超出临界值(且要存放的位置非空)时，扩容。默认的扩容方式：扩容为原来容量的2倍，并将原的数据复制过来。
HashMap在jdk8中相较于jdk7在底层实现方面的不同：
- new HashMap():底层没创建一个长度为16的数组,首次调用put()方法时，底层创建长度为16的数组
- jdk 8底层的数组是：Node[],而非Entry[]
-
jdk7底层结构只：数组+链表。jdk8中底层结构：数组+链表+红黑树。
3.1 形成链表时，七上八下（jdk7:新的元素指向旧的元素。jdk8：旧的元素指向新的元素）
3.2 当数组的某一个索引位置上的元素以链表形式存在的数据个数 > 8 且当前数组的长度 > 64时，此时此索引位置上的数据改为使用红黑树存储。
当满足条件个数大于8以后调用treeifyBin方法尝试转化红黑树。但是数组如果长度小于MIN_TREEIFY_CAPACITY（64）就选择扩容，而不是转化为红黑树，这就是为什么s或尝试转换的原因。。
HashMap底层典型属性的属性的说明：
DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16
DEFAULT_LOAD_FACTOR：HashMap的默认加载因子：0.75
threshold：扩容的临界值，=容量*填充因子：16 * 0.75 => 12
TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树:8
MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量:64 同时 当树中的元素小于等于6的时候会退化为链表
面试题总结
LinkedHashMap的底层实现原理(了解)
LinkedHashMap底层使用的结构与HashMap相同，因为LinkedHashMap继承于HashMap. HashMap和双向链表合二为一即是LinkedHashMap。
同时hashMap是无序的，也就是说我们遍历map的顺序和最初插入的顺序是不一致的。但是LinkedHashMap保证了有序性，遍历map集合的时候，可以保证按照插入的顺序。
保证在遍历map元素时，可以照添加的顺序实现遍历。 原因：在原的HashMap底层结构基础上，添加了一对指针，指向前一个和后一个元素。
对于频繁的遍历操作，此类执行效率高于HashMap。
区别就在于：LinkedHashMap内部提供了Entry，替换HashMap中的Node.
HashTbale
Hashtable同样是基于哈希表实现的，同样每个元素是一个key-value对，其内部也是通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。
HashMap不能保证线程安全，但HashTable可以，JDK1.0引入的类，是线程安全的，能用于多线程环境中。
HashMap和HashTable的不同
主要区别就是
- 作为古老的实现类；线程安全的，效率低；
- 不能存储null的key和value
- 数据结构是数组+链表
- .计算hash值方式不同
为了得到元素的位置，首先需要根据元素的 KEY计算出一个hash值，然后再用这个hash值来计算得到最终的位置。
①：HashMap有个hash方法重新计算了key的hash值,因为hash冲突变高，所以通过一种方法重算hash值的方法：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
注意这里计算hash值，先调用hashCode方法计算出来一个hash值，再将hash与右移16位后相异或，从而得到新的hash值。
**②：Hashtable通过计算key的hashCode()**来得到hash值就为最终hash值。
- HashMap 哈希扩容必须要求为原容量的2倍，而且一定是2的幂次倍扩容结果，而且每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入；而Hashtable扩容为原容量2倍加1；
具体的加锁机制
Hashtable是在每个方法上都加上了Synchronized完成同步，效率低下。见图。
其有一个子类Properties：
Hashtable的子类，要求key和value都是String。通常与配置文件的读取。
ConcurrentHashMap
上面说到HashMap是线程不安全的，那么在并发的使用场景下，就要使用ConcurrentHashMap来保证安全，ConcurrentHashMap相比于同样线程安全的HashTable，效率要高很多（ConcurrentHashMap采用的锁有synchronized，CAS，自旋锁，分段锁，volatile等；）
ConcurrentHashMap是HashMap的线程安全版本，内部也是使用（数组 + 链表 + 红黑树1.8）的结构来存储元素。
同样也分1.7和1.8两个版本（这个东西它太值得探究了，写源码的小哥哥一次也不可能研究到位，就得一直改啊改）
参考分析
1.7和1.8共同的特性
- key和value都不允许为null
- ConCurrentHashMap支持高并发的访问和更新，它是线程安全的
- 读操作没有加锁其中vauel和next用了volatile 修饰，保证了在内存中的可见性是安全的，从而使得get方法是不用加锁的，是非阻塞的。
- 读写分离操作提高效率，多线程对不同的segment/Node 的插入/删除是可以并发并行的，对同一个的segment/Node的写操作互斥。读操作无锁。
- 键、值迭代器是弱一致迭代器，创建迭代器之后，可以对元素进行更新。
- JDK1.8底层是散列表+红黑树
- 在任何一个构造方法中，都没有对存储Map元素Node的table变量进行初始化。而是在第一次put操作的时候在进行初始化。
ConcurrentHashMap在1.7中实现原理
数组+链表+分段锁
底层的数据结构还是数组+链表，整个Hash表，segment（段），HashEntry（节点）。每个segment就相当于一个HashTable（一个哈希桶）。这里的数组是一个Segment 数组、链表的每一个结点是HashEntry ，HashEntry和 HashMap 一样，仍然是数组 + 链表。Hash链中的数据都是从头开始插入的。只有next的引用。
保证线程安全的机制
- 关于Segment
- Segment是一种可重入锁继承自ReentrantLock，在ConcurrentHashMap里扮演锁的角色。也就是说ConcurrentHashMap实现同步的方式时基于ReentrantLock锁机制的。
-
分段锁的原理
在 HashTable中锁是 HashTable这个对象，而在 ConcurrentHashMap是堆同一个segment进行同步枷锁，（这里可以就是理解对一个桶加锁），这样可以基于不同的segment实现并发写操作。
和HashMap一样，同样存在着hash冲突的问题，链表查询效率低。
HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组，Segment的结构和HashMap类似，是一种数组和链表结构， 一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素， 每个Segment守护一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时，必须首先获得它对应的Segment锁。
ConcurrentHashMap在1.8中实现原理
数组+链表+红黑树， 用CAS无锁算法 + synchronized来实现线程安全
保证安全的机制
结构和HashMap的结构一样，其中抛弃了分段锁，采用了CAS+synchronized来保证并发安全，1.7 中存放数据的 HashEntry 改为 Node，但作用都是相同的。
对一个结点进加锁
在 ConcurrentHashMap锁则是数组中的第一个元素。这样的话，我们比如我们要多数组中下标为0和1的桶进行操作，两个线程就可以同时对0和1进行操作。
1.7是一段一段的多个结点加锁（一个桶加锁），1.8是一个结点加锁（一个桶的第一个元素加锁）应该是这么理解的。
put
到底如果采用了CAS+synchronized，就得看看它的put方法的源码
参考源码分析
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
// key 和 value 都不能为 null
if (key == null || value == null) throw new NullPointerException();
// 计算 hash 存放数组哪一个索引
int hash = spread(key.hashCode());
int binCount = 0;
// 这里一直自旋，直到放入元素成功
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// 如果数组没有被初始化，则去初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// 如果桶中第一个元素没有元素，则通过CAS的方式进行放入
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// casTabAt --去调用 U.compareAndSwapObject 自旋
//为什么不是说如果失败就自旋还有重新再去判断一次
//因为并发操作的时候，有可能一个线程刚开始判断是第一个位置没有元素
//但是插入失败 其他线程插入成功更改了就会有元素 所以需要再次判断自旋
//而不是无条件自旋
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// 如果当前桶中的元素正在被迁移，则当前线程也帮助迁移元素
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
// 以桶中第一个元素为锁对象
synchronized (f) {
if (tabAt(tab, i) == f) {
// 如果第一个节点是链表节点，则以链表的方式放入元素
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
// 如果当前元素是树节点，则以树的方式放入元素
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
// 判断是否需要树化
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
// 键值对个数+1
addCount(1L, binCount);
return null;
}
TreeMap
TreeMap的使用向TreeMap中添加key-value，要求key必须是由同一个类创建的对象
因为要照key进行排序：自然排序 、定制排序
保证照添加的key-value对进行排序，实现排序遍历。此时考虑key的自然排序或定制排序
底层使用红黑树