Map接口

本文主要介绍Map接口下的HashMap，TreeMap，HashTable，LinkedHashMap，ConcurrentHashMap五个类。

对比这5种Map结构，其中HashMap和ConcurrentHashMap最为常用，前者用于单线程，后者用于多线程。

TreeMap和LinkedHashMap可以看做两种有特殊用途的Map结构，前者是基于红黑树构造的有序Map，后者在HashMap的基础上多维护了一个双向链表，记录Map中元素顺序（有插入顺序和访问顺序两种，可用于实现LRUCache之类的需求）。

HashMap

HashMap实现了Map接口，主要用来存放键值对，它基于哈希表的 Map 接口实现，是常用的 Java 集合之一，是非线程安全的。 其特点如下：

1. JDK1.8 之前 HashMap 底层是数组和链表 ，之后使用数组+链表+红黑树。

   

2. 哈希冲突：采用拉链法，数组中每一格代表链表，遇到冲突的哈希值，将其加入链表中即可。

3. 数组扩容：HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍 。 并且， HashMap 总是使用 2 的幂作为哈希表的大小（因为计算数组下标采用“与”操作(n-1)&hash）。 是否扩容由loadFactor参数控制，当size>=threshold时，进行数组扩容。其中threshold = capacity * loadFactor，loadFactor称之为加载因子，默认值为0.75。扩容机制的详细介绍，可参考https://zhuanlan.zhihu.com/p/114363420。

   

   这里大概总结下扩容的过程：

   • 先重新建立一个数组，然后把原来数组中元素，放到新数组对应位置；

   • 链表中的插入，采用的是头插法，上图中原来3在7前面，但是扩容后，7在3前面。

4. 允许放入key为null的元素，也允许插入value为null的元素，会将key为null的元素放到index=0处。

TreeMap

Java TreeMap实现了SortedMap接口，也就是说会按照key的大小顺序对Map中的元素进行排序，key大小的评判可以通过其本身的自然顺序(natural ordering)，也可以通过构造时传入的比较器(Comparator)。其特性如下：

1. 底层实现：TreeMap底层通过红黑树(Red-Black tree)实现，也就意味着containsKey(), get(), put(), remove()都有着log(n)的时间复杂度。
2. 线程不安全，是非同步的。

HashTable

其实现和HashMap十分类似，但是它是一个过时类，不建议使用，下面将其和HashMap进行对比：

1. 实现：两者类似，都是数组+链表。
2. Null值：HashMap的key和value都可以是Null，但是HashTable不允许key-value为空。
3. 线程安全：HashTable大部分方法都有synchronized修饰是线程安全的，而HashMap多线程下存在安全问题。

LinkedHashMap

大多数情况下，只要不涉及线程安全问题，Map基本都可以使用HashMap，不过HashMap有一个问题，就是迭代HashMap的顺序并不是HashMap放置的顺序，也就是无序。HashMap的这一缺点往往会带来困扰，因为有些场景，我们期待一个有序的Map。

LinkedHashMap继承自HashMap，其底层除了有和HashMap一样的数组+链表结构外，还额外维护了一个双向链表，用于保存元素加入顺序，可以认为是HashMap+LinkedList。其特性如下：

1. 和HashMap.Entry相比，其Entry中还有Entry<K,V> before和Entry<K,V>after两个属性，记录该Entry在链表中位置。
2. LinkedHashMap中具有accessOrder属性，默认为false，表示链表按照插入顺序维护，若为true，链表则按照访问顺序维护。
3. 应用：可以用来实现LRUCache，即基于LRU算法的Cache。
4. 它也是非线程安全的。

ConcurrentHashMap

前面提到单线程下大多数情况首选HashMap，但是在多线程场景下ConcurrentHashMap更为适用。

JDK1.7

其底层存储结构如下图所示：

ConcurrnetHashMap 由很多个 Segment 组合，而每一个 Segment 是一个类似于 HashMap 的结构，所以每一个 HashMap 的内部可以进行扩容。但是 Segment 的个数一旦初始化就不能改变，默认 Segment 的个数是 16 个，你也可以认为 ConcurrentHashMap 默认支持最多 16 个线程并发。

JDK1.8

JDK1.8后其底层存储结构由 Segment 数组 + HashEntry 数组 + 链表 进化成了 Node 数组 + 链表 / 红黑树 ，如下图所示：

当冲突链表达到一定长度时，链表会转换成红黑树。 这也导致了JDK1.8和JDK1.7中ConcurrentHashMap的另外一个区别是： Java7 中 ConcruuentHashMap 使用的分段锁，也就是每一个 Segment 上同时只有一个线程可以操作；而 Java8 中的 ConcruuentHashMap 使用的 Synchronized 锁加 CAS 的机制。

参考资料

1. https://pdai.tech/md/java/collection/java-map-TreeMap&TreeSet.html
2. https://javaguide.cn/java/collection/java-collection-questions-02
3. https://www.jianshu.com/p/6c95f8216950
4. https://www.cnblogs.com/xiaoxi/p/6170590.html
5. https://mp.weixin.qq.com/s/AHWzboztt53ZfFZmsSnMSw