Map集合

常见的Map有：HashMap，HashTable，LinkedHashMap, ConcurrentHashMap， TreeMap

Map都是双列的集合，采用键值对的方式存储，底层实现都是 数组 + 链表，也就是 hash表

HashMap

• HashMap 的 key 和值都可以为 null
• HashMap是 线程不安全的（任意时刻，可以有多个线程同时写HashMap）
• JDK1.7 底层采用 数组 + 链表 ，JDK1.8时 底层采用 数组 + 链表 + 红黑树

HashMap底层实现：

HashMap根据 键的HashCode值存储数据，向HashMap中存储元素时，首先会计算一个hash值，然后根据hash值存到指定数组索引位置，数组的每一个元素都是一对 key-value，但由于hash值具有概率性，可能出现hash冲突，定位到同一数组下标处，此时就产生了链表结构。

由于链表的遍历效率较低，取决于链表的长度，时间复杂度为 O(N), 如果链表太长，则查找效率低。所以JDK1.8 新增了红黑树结构，当链表中的元素超过 8 之后，改用红黑树存储，查找的时间复杂度为 O(log N)

红黑树的特点：
每个节点只有两种颜色：红色或者黑色
根节点必须是黑色
每个叶子节点（NIL）都是黑色的空节点
从根节点到叶子节点，不能出现两个连续的红色节点
从任一节点出发，到它下边的子节点的路径包含的黑色节点数目都相同

大致地，HashMap里面是一个数组，数组中每个元素是一个单向链表，链表元素达到 8 以后，转为红黑树存储

每一个数组或链表元素（即下图中 绿色实体）都是 一个 Entry嵌套类的示例

Entry包含四个属性： Key 、 value 、 该数组下标的hash值、 链表的next指针

三个属性：

1. capacity： 当前数组容量，始终保持 2 ^ n（默认初始化容量是 16），可以扩容，扩容后容量为 数组大小的 2 倍

2. Loadfactor：负载因子，默认为 0.75 (使用0.75，是时间和空间的权衡)

3. threshold：扩容阈值，等于 capacity * Loadfactor (当存储的元素的容量达到这个阈值时，需要扩容)

ConcurrentHashMap（线程安全）

• 支持并发操作，是线程安全的HashMap

• 由Segment数组组成，每个Segment元素是可以看成一个HashMap结构，每个Segment都通过继承ReentranLock来实现线程同步

• ConcurrencyLevel：并发数、Segment数，默认是16，就是默认Segment数量为 16，理论上支持16个并发操作

• ConcurrentLevel 在初始化时，可以设置为其他值，一旦初始化，就不可以再扩容

HashTable（线程安全）

• HashTable是遗留类，很多功能与HashMap类似（不同的是HashTable继承自 Dictionary 类，是线程安全的）
• 虽然线程安全，但由于ConcurrentHashMap引入了分段锁，其并发性不如 ConcurrentHashMap,一般不建议使用HashTable

LinkedHashMap（记录插入顺序）

• LinkedHashMap是HashMap的一个子类，保存了元素的插入顺序
• 使用 Iterator 迭代器遍历时，得到的记录顺序就是 元素插入的顺序

TreeMap（可排序）

• TreeMap 实现 SortedMap 接口，能够把它保存的记录根据键排序，默认是按键值的升序排序
• 也可以指定排序的比较器，当用 Iterator 遍历 TreeMap 时，得到的记录是排过序的
• 如果使用排序的映射，建议使用 TreeMap
• 在使用 TreeMap 时，key 必须实现 Comparable 接口或者在构造 TreeMap 传入自定义的 Comparator，否则会在运行时抛出 java.lang.ClassCastException 类型的异常