Map是Java里的一个接口，常见的实现类有HashMap、LinkedHashMap、TreeMap和ConcurrentHashMap

HashMap

HashMap底层数据结构是数组+链表/红黑树（JDK1.8后使用Node来存放键值对，Node实现Map.Entry接口）

• 当我们new一个HashMap的时候会发生什么？

HashMap有几个构造方法，但最主要的就是指定初始size和负载因子的大小，如果我们不指定，默认HashMap的大小为16负载因子的大小为0.75。还有就是：HashMap的大小只能是2的整数次幂，比如你指定HashMap大小为10，实际上最终HashMap的大小是16，具体可以在tableSizeFor方法看到。

• 元素是在HashMap中是如何存储的？（put和get方法的实现？）

当我们把元素放进HashMap的时候（put的时候），需要先算出这个元素（用Entry对象的key来算）的hash值，然后再根据hash值算出这个元素在hash表（数组）中的位置（HashTable是用hash值对size进行取模运算得到，HashMap是用hash值对size-1按位与运算得到，HashMap更加高效，所以HashMap的size只能是2的整数次幂就是为了方便位运算）。

当两个元素的hash值计算出在hash表同一个位置时，就会在hash表对应的位置使用尾插法（JDK1.8之前是头插）将元素插入链表，如果链表的长度超过了8在JDK1.8中会将链表结构转为红黑树结构（如果红黑树大小小于6则会自动退化为链表结构），因为链表长度过长的话查找效率就低（O(n)），而红黑树的插入和查找效率相对均衡（都是O(logn)）。

当HashMap中存放元素的个数超过了size0.75后，则HashMap会进行扩容，每次扩容都扩为原来size的两倍*（能否把负载因子调高，减少扩容的次数？可以，但不建议，因为会增加hash冲突的概率，影响查找效率）。

在get的时候，还是对key做hash运算，计算出该key在hash表中的index，然后判断是否有hash冲突，如果没有hash冲突就直接返回数据，如果有hash冲突就再判断存储的数据结构是链表还是红黑树，按照对应的数据结构取出数据。

• 在HashMap中怎么判断两个元素（key）是否相同？

首先会比较hash值，如果hash值不同，那这两个元素一定不同，如果hash值相同，则说明产生了hash冲突，接着用equals方法判断两个元素是否相同。

• HashMap是线程安全的吗？

HashMap不是线程安全的。在多线程环境下，HashMap有可能会有数据丢失和获取不了最新数据的问题，比如：线程A put一条数据进去了，但是线程B get不到这条数据。

LinkedHashMap

LinkedHashMap底层数据结构是数组+链表+双向链表

• LinkedHashMap的插入为什么是有序的？

LinkedHashMap实际上是继承了HashMap，在HashMap的基础上维护了一个双向链表。有了这个双向链表，我们的插入就可以是有序的。LinkedHashMap在遍历的时候实际用的是双向链表来遍历的，所以LinkedHashMap的大小不会影响遍历的性能。

TreeMap

TreeMap底层数据结构是红黑树，每个节点就是一个Entry对象。

• TreeMap为什么是有序的？

TreeMap的有序是通过Comparator比较器来比较的（在TreeMap构造时传入Comparator比较器，如果没有传入比较器，则使用默认的比较器，即自然顺序）。TreeMap的key不能为null，因为null值无法比较大小。

ConcurrentHashMap

ConcurrentHashMap底层数据结构也是数组+链表/红黑树

• 除了ConcurrentHashMap还有什么线程安全的Map？

还有HashTable和使用Collections来包装出一个线程安全的Map（Collections.synchronizedMap）。但是这两种线程安全Map效率比较低，是直接在HashMap的外层套synchronized，所以使用线程安全的Map一般用ConcurrentHashMap。

• ConcurrentHashMap如何实现线程安全？

ConcurrentHashMap通过部分加锁和CAS算法来实现同步。部分加锁：在put操作时，对数组的每一个元素（数组中的元素是链表头或者是红黑树根）进行加锁（JDK1.7中是对某几个连续元素组成的segment进行加锁，JDK1.8缩小了锁的粒度，大大减小了锁的竞争），在hash完美不冲突的情况下最多可以支持n（n为数组大小）个线程同时put操作。

put操作：

1. 首先判断数组是否为null，因为ConcurrentHashMap把数组的初始化推迟到了第一次put操作时，如果数组为null，则调用数组初始化方法。在调用初始化方法时，有一个sizeCtl属性，如果sizeCtl<0则表示有另外的线程在执行初始化操作，当前线程让出CPU时间片（Thread.yield()）
2. 当数组不为null，则判断此次put是否存在hash冲突，如果不存在hash冲突，则直接使用CAS的方式（判断此次插入的数组下标对应的CAS值，相等则直接插入数据，不相等更新该线程所得到的CAS值，并重新进行put操作）在数组中插入此次put的Node
3. 在hash冲突的put之前，先检查是否有其他线程正在扩容，如果有，则调用helpTransfer方法帮助其他线程进行扩容
4. 当此次put存在hash冲突时，synchronized锁住数组中的Node节点（即链表的表头或者红黑树的根），然后判断存储Node节点的数据结构，根据不同的数据结构进行遍历，遍历时先看是否链表或红黑树中有与此次put相同的key，如果有相同的key就修改其对应的value，如果没有就在链表尾部插入或红黑树的插入方式插入此次put的Node。如果是hash冲突的链表插入，在插入完成后会判断链表的长度是否达到临界值8，如果达到8，则会调用treeifyBin方法把链表转为红黑树。treeifyBin在执行前会先判断数组的长度是否小于64，若小于64则会优先做扩容操作，再把链表转为红黑树
5. 当put操作结束后，调用addCount方法统计元素个数，并判断是否要进行扩容操作

get操作：get操作不加锁，通过CAS的方法取数组中对应的节点（如果CAS失败则更新CAS值再取一次）。ConcurrentHashMap支持边扩容边进行get操作。