两万字长文读懂 Java 集合( 三 ) _Java

SortedMap 定义了该类 Map 具有排序行为，同时它在内部定义好有关排序的抽象方法，当子类实现它时，必须重写所有方法，对外提供排序功能。

文章插图

HashMapHashMap 是一个最通用的利用哈希表存储元素的集合，将元素放入 HashMap 时，将 key 的哈希值转换为数组的索引下标确定存放位置，查找时，根据 key 的哈希地址转换成数组的索引下标确定查找位置。
HashMap 底层是用数组 + 链表 + 红黑树这三种数据结构实现，它是非线程安全的集合。

文章插图
发送哈希冲突时，HashMap 的解决方法是将相同映射地址的元素连成一条链表，如果链表的长度大于 8 时，且数组的长度大于 64 则会转换成红黑树数据结构。
关于 HashMap 的简要总结：

它是集合中最常用的 Map 集合类型，底层由数组 + 链表 + 红黑树组成。
HashMap 不是线程安全的。
插入元素时，通过计算元素的哈希值，通过哈希映射函数转换为数组下标；查找元素时，同样通过哈希映射函数得到数组下标定位元素的位置。

LinkedHashMapLinkedHashMap 可以看作是 HashMap 和 LinkedList 的结合：它在 HashMap 的基础上添加了一条双向链表，默认存储各个元素的插入顺序，但由于这条双向链表，使得 LinkedHashMap 可以实现 LRU缓存淘汰策略，因为我们可以设置这条双向链表按照元素的访问次序进行排序。

文章插图
LinkedHashMap 是 HashMap 的子类，所以它具备 HashMap 的所有特点，其次，它在 HashMap 的基础上维护了一条双向链表，该链表存储了所有元素，默认元素的顺序与插入顺序一致。若 accessOrder 属性为 true，则遍历顺序按元素的访问次序进行排序。
// 头节点transient LinkedHashMap.Entry<K, V> head;// 尾结点transient LinkedHashMap.Entry<K, V> tail;利用 LinkedHashMap 可以实现 LRU 缓存淘汰策略，因为它提供了一个方法：
protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) {return false;}该方法可以移除最靠近链表头部的一个节点，而在 get 方法中可以看到下面这段代码，其作用是挪动结点的位置：
if (this.accessOrder) {this.afterNodeAccess(e);} 只要调用了 get 且 accessOrder=true，则会将该节点更新到链表尾部，具体
的逻辑在afterNodeAccess中，感兴趣的可翻看源码，篇幅原因这里不再展开。
现在如果要实现一个LRU缓存策略，则需要做两件事情：

指定 accessOrder = true 可以设定链表按照访问顺序排列，通过提供的
构造器可以设定 accessOrder

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder;}

重写 removeEldestEntry 方法，内部定义逻辑，通常是判断容量是否达到上限，若是则执行淘汰。

这里就要贴出一道大厂面试必考题目：146. LRU 缓存机制，只要跟着我的步骤，就能顺利完成这道大厂题了。
关于 LinkedHashMap 主要介绍两点：

它底层维护了一条双向链表，因为继承了 HashMap，所以它也不是线程安全的
LinkedHashMap 可实现LRU缓存淘汰策略，其原理是通过设置 accessOrder 为 true 并重写 removeEldestEntry 方法定义淘汰元素时需满足的条件

TreeMapTreeMap 是 SortedMap 的子类，所以它具有排序功能。它是基于红黑树数据结构实现的，每一个键值对 <key, value> 都是一个结点，默认情况下按照key自然排序，另一种是可以通过传入定制的 Comparator 进行自定义规则排序。

// 按照 key 自然排序，Integer 的自然排序是升序TreeMap<Integer, Object> naturalSort = new TreeMap<>;// 定制排序，按照 key 降序排序TreeMap<Integer, Object> customSort = new TreeMap<>((o1, o2) -> Integer.compare(o2, o1));

TreeMap 底层使用了数组+红黑树实现，所以里面的存储结构可以理解成下面这幅图哦。