0%

Java Map 和 Set（六）：剖析 LinkedHashMap

发表于 更新于 分类于
本文字数： 4.9k 阅读时长 ≈ 4 分钟

1. LinkedHashMap 的概念

  • LinkedHashMap 是 HashMap 的子类
  • LinkedHashMap 可以保持元素按插入或访问有序，这与 TreeMap 按键排序不同

2. LinkedHashMap 的数据结构图

LinkedHashMap 的数据结构图

3. LinkedHashMap 的基本用法

  • LinkedHashMap 是 HashMap 的 子类
  • LinkedHashMap 内部还有一个双向链表维护键值对的顺序，每个键值对既位于哈希表中，也位于这个双向链表中
  • LinkedHashMap 支持两种顺序：一种是插入顺序，一种是访问顺序

4. 怎样理解插入顺序和访问顺序

  • 插入顺序

    • 先添加的在前面，后添加的在后面
    • 修改操作（对已有的键进行 put）不影响排序

  • 访问顺序

    • 所谓访问是指 get/put 读写操作
    • 对一个键执行 get/put 操作后，其对应的键值对会移到链表末尾
    • 所以，最末尾的键值对是最近访问的，最开始的键值对是最久没被访问的，这种顺序就是访问顺序

5. LinkedHashMap 基本用法之构造方法

  • 源码基于 Java 7
  • LinkedHashMap 有 5 个构造方法，其中 4 个都是按插入排序，只有一个构造方法可以指定按访问顺序，即：public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
  • 参数 accessOrder 就是用来指定是否按访问顺序，如果为 true，就是按访问顺序

6. 下面代码的输出结果

1
2
3
4
5
6
7
8
9
Map<String, Integer> seqMap = new LinkedHashMap<> ();
seqMap.put("c", 100);
seqMap.put("d", 200);
seqMap.put("a", 500);
seqMap.put("d", 300);

for(Entry<String, Integer> entry : seqMap.entrySet()) {
    System.out.print(entry.getKey() + ", " + entry.getValue() + "   ");
}
  • 结果：c 100 d 300 a 500
  • 分析：LinkedHashMap 的默认构造方法是按插入有序的，修改 d 的值不会修改顺序

7. 什么时候希望保持插入顺序呢，或者说保持插入顺序的使用场景有哪些

  • 场景一

    • Map 经常用来处理一些数据，其处理模式是：接收一些键值对作为输入，进行处理，然后输出，输出时希望保持原来的顺序
    • 比如，一个配置文件，其中有一些键值对形式的配置项，但其中有一些键是重复的，希望保留最后一个值，但还是按原来的键顺序输出，这种情况下，LinkedHashMap 就是一个合适的数据结构

  • 场景二

    • 希望的数据模型可能就是一个 Map，但希望保持添加时的顺序
    • 比如，一个购物车，键为购买的项目，值为购买数量或者价格，按用户添加时的顺序保存

  • 场景三

    • 希望 Map 能够按键有序，但在添加到 Map 前，键已经通过其他方式排好序了。这时，就没有必要使用 TreeMap 了，毕竟 TreeMap 的开销要大一些
    • 比如，从数据库查询数据放到内存时，可以使用 SQL 的 order by 语句让数据库对数据排序

8. 下面代码的输出结果是

1
2
3
4
5
6
7
8
9
10
Map<String, Integer> accessMap = new LinkedHashMap<> (16, 0.75f, true);
accessMap.put("c", 100);
accessMap.put("d", 200);
accessMap.put("a", 500);
accessMap.put("c");
accessMap.put("d", 300);

for(Entry<String, Integer> entry : accessMap.entrySet()) {
    System.out.print(entry.getKey() + " " + entry.getValue() + "   ");
}
  • 结果：a 500 c 100 d 300
  • 分析：accessOrder 参数为 true，即指定按访问顺序排序。所以，每次访问都会将被访问的键值对移到双向链表的末尾

9. 怎样理解缓存

  • 缓存：计算机技术中一种非常有用的技术，是一个通用的提升数据访问性能的思路，一般用来保存常用的数据，容量较小，但访问速度更快

    • 缓存是相对主存而言的，主存的容量更大，但访问更慢
    • 缓存的基本假设是：数据会被多次访问，一般访问数据时都先从缓存中找，缓存中没有再从主存中找，找到后再放入缓存，这样下次如果再找相同数据访问就快了

  • 缓存用于计算机技术的各个领域

    • CPU 里有缓存，有一级缓存、二级缓存、三级缓存等。一级缓存非常小、非常贵、也非常快，三级缓存则大一些、便宜一些、也慢一些。CPU 缓存是相对于内存而言的，它们都比内存快
    • 内存里也有缓存，内存的缓存一般是相对于硬盘数据而言的
    • 硬盘也可能是缓存，缓存网络上其他机器的数据，比如浏览器访问网页时，会把一些网页缓存到本地硬盘

  • LinkedHashMap 可以用于缓存，比如缓存用户基本信息，键是用户 ID，值是用户信息。所有用户信息可能保存在数据库中，部分活跃用户的信息可能保存在缓存中

10. 怎样理解 LRU 缓存替换算法

  • 替换算法：一般而言，缓存容量有限，不能无限存储所有数据。如果缓存满了，当准备存储新数据时，就需要一定的策略将一些老的数据清理出去，这个策略一般称为替换算法
  • 概念：LRU 是一种流行的替换算法，它的全称是：Least Recently Used，即最近最少使用
  • 思路：最近刚被使用的很快再次被用的可能性最高，而最久没被访问的很快再次被用的可能性最低，所以被优先清理

11. 什么时候希望按访问有序呢，或者说按访问有序的使用场景有哪些

  • 一种典型的应用是 LRU 缓存。使用 LinkedHashMap，可以非常容易地实现 LRU 缓存

  • 默认情况下，LinkedHashMap 没有对容量做限制，但它可以容易地做到

    • LinkedHashMap 有一个 protected 方法，即：protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return false; }
    • 在添加元素到 LinkedHashMap 后，LinkedHashMap 会调用这个方法，传递的参数是最久没被访问的键值对
    • 如果这个方法返回 true，则这个最久没被访问的键值对就会被删除

  • LinkedHashMap 对这个方法的实现总是返回 false，所以容量没有限制，但子类可以重写这个方法，在满足一定条件的情况下返回 true，实现替换清理策略

12. 请实现一个 LRU 缓存

  • Demo

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public class LRUCache<K, V> extends LinkedHashMap<K, V> {

        private int maxEntries;

        public LRUCache(int maxEntries) { //在构造方法中传递一个容量限制
            super(16, 0.75f, true);
            this.maxEntries = maxEntries;
        }

        @Override
        protected boolean removeEldestEntry(Entry<K, V> eldest) {
            return size() > maxEntries;
        }
    }

  • 这个缓存可以这么用

    1
    2
    3
    4
    5
    6
    7
    LRUCache<String, Object> cache = new LRUCache<> (3);
    cache.put("a", "abstract");
    cache.put("b", "basic");
    cache.put("c", "call");
    cache.put("a");
    cache.put("d", "call");
    System.out.print(cache);

  • 因为限定缓存容量为 3，先后添加了 4 个键值对，最久没被访问（最近最少使用）的键是 b，会被删除。所以输出为：{c=call, a=abstract, d=call}

13. LinkedHashMap 的内部组成

  • 源码基于 Java 7

  • LinkedHashMap 是 HashMap 的子类，内部增加了如下实例变量

    1
    2
    private transient Entry<K, V> header;
    private final boolean accessOrder;
    • accessOrder 表示是按访问顺序还是插入顺序
    • header 表示双向链表的头，它的类型 Entry 是一个内部类，这个类是 HashMap.Entry 的子类，增加了两个变量 before 和 after，指向双向链表中的前驱和后继

  • LinkedHashMap 中的 Entry 的代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    private static class Entry<K, V> extends HashMap.Entry<K, V> {

        Entry<K, V> before, after;

        Entry(int hash, K key, V value, HashMap.Entry<K, V> next) {
            super(hash, key, value, next);
        }

        private void remove() {
            before.after = after;
            after.before = before;
        }

        private void addBefore(Entry<K, V> existingEntry) {
            after = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

        void recordAccess(HashMap<K, V> m) {
            LinkedHashMap<K, V> lm = (LinkedHashMap<K, V> m);
            if(lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }

        void recordRemoval(HashMap<K, V> m) {
            remove();
        }

    }
    • recordAccess() 和 recordRemoval() 是 HashMap.Entry 中定义的方法，在 HashMap 中，这两个方法的实现为空，它们就是被设计用来被子类重写的。在 put() 被调用且键存在时，HashMap 会调用 Entry 的 recordAccess() 方法；在键被删除时，HashMap 会调用 Entry 的 recordRemoval() 方法
    • LinkedHashMap.Entry 重写了这两个方法。在 recordAccess() 方法中，如果是按访问顺序的，则将该节点移到链表的末尾；在 recordRemoval() 方法中，将该节点从链表中移除
    • LinkedHashMap 及其节点类 LinkedHashMap.Entry 重写了父类的 init() 方法、addEntry() 方法、createEntry() 方法、get() 方法等相关方法以维护这种关系

14. LinkedHashSet 的概念

  • LinkedHashSet 是 HashSet 的子类
  • 它内部的 Map 的实现类是 LinkedHashMap，所以它也可以保持插入顺序

15. 下面代码的输出结果是

1
2
3
4
5
6
Set<String> set = new LinkedHashSet<> ();
set.add("b");
set.add("c");
set.add("a");
set.add("c");
System.out.print(set);
  • 结果：[b, c, a]
  • 分析：默认是按插入排序，修改操作（对已有的键进行 put）不影响排序
-------------------- 本文结束感谢您的阅读 --------------------