Map有哪些类？HashMap如何实现？

Map是Java中最常用的接口之一，它以键值对的形式保存数据。Map接口主要有四个常用的实现类，分别是HashMap、Hashtable、以键值LinkedHashMap和TreeMap。

接下来将分别介绍每一个实现类。

·Hash Map是最常用的Map，它根据键的HashCode值存储数据，根据键可以直接获取它的值，具有快速的访问速度。然而，它的内部方法都没有使用synchronized关键字修饰，是线程不安全的。

·HashMap允许空键值且最多只允许一条记录的key为空，但允许多条记录的value为空。

·TreeMap实现了SortedMap接口，也是一个常用的Map实现类。它的一个很大特点是会对Key进行排序。使用TreeMap存储键值对，再使用Iterator进行输出时会发现其默认采用key由小到大的顺序输出键值对。

如果想要按照其他的方式来排序，需要重写它的compartor接口，可参考右侧代码示例。TreeMap底层的存储结构也是一颗红黑树，红黑树是一种自平衡的二叉查找树，在每次插入和删除节点时都可以自动调节树结构，以保证树的高度是log n，因此查找效率相对较高。

·Hashtable是遗留类，很多映射的常用功能与HashMap类似，不同的是它继承自Dictionary类，是线程安全的Map实现类。它实现线程安全的方法是在各个方法上添加了synchronized关键字，但现在已经不再推荐使用Hashtable了。

因为有了Concurrent Hash Map这个专门用于并发场景下的Map实现类，其大大优化了多线程下的性能。后面再做专题介绍。

LinkedHashMap底层是用链表来进行存储的，相对于其他的无序的Map实现类。还有像TreeMap这样的排序类。LinkedHashMap最大的特点在于有序，但是它的有序主要体现在先进先出（FIFO）上。

·先出上：Linked HashMap主要依靠双向链表和hash表来实现的。在用Iterator遍历LinkedHash Map时，先得到的记录肯定是先插入的，也可以在构造时带参数按照访问次序排序。与普通的HashMap类似，WeakHashMap的不同之处在于，当其内部的key不再被外部引用时，会被垃圾回收器自动回收。而普通的HashMap则采用了“强引用”的方式，即当其内部的key没有被外部引用时，还需将其从HashMap中删除，才可被垃圾回收器回收。

HashMap是如何实现的呢？它的数据结构采用了开放壁纸方式和冲突链表方式两种实现方式。在JDK7中，HashMap采用了冲突链表方式。从图中可以看出，当选择合适的哈希函数时，put和get方法的时间复杂度可以在常数级别，但是在对HashMap进行迭代时，需要遍历整个table以及后面的冲突链表。因此，对于迭代操作较多的场景，不宜将HashMap的初始大小设置过大。有两个参数可以影响HashMap的性能：初始容量和负载系数。初始容量指定了初始table的大小，而负载系数则用于指定自动扩容的临界值。当entry的数量超过初始容量和负载系数的乘积时，容器将自动扩容并重新哈希。

对于插入元素较多的场景，将初始容量设置为较大的值可以减少重新哈希的次数。在查找时，HashMap可以根据hash值快速定位到数组的具体下标，但是之后需要顺着链表一个个比较下去才能找到所需的元素。因此，HashMap的时间复杂度取决于链表的长度，即为O(N)。当n较大时，查找效率会降低。为了降低这部分的开销，在JDK8中，当链表中的元素达到8个时，会将链表转换为红黑树，此时进行查找的时间复杂度可以降低为0(log N)。

以上就是关于Map相关的分享，欢迎留言讨论。