前言

前面我们对Java集合框架有了一个基本的认识; 本文将主要讲解LinkedHashMap的实现原理和处理细节

LinkedHashMap继承于HashMap, 所以需要先对HashMap有一个基本的认识, 可以参见Java集合框架之HashMap

文章源码基于JDK8

Java集合框架系列博客:

正文

一. 概述

LinkedHashMap继承于HashMap, 除了HashMap元素遍历无序, LinkedHashMap元素遍历有序以外, 具有HashMap的大多数特点; 另外, LinkedHashMap内部还有一个双向链表, 用于记录元素顺序(这也是保证其遍历有序的原因), 具体有两种顺序, 一个是插入顺序, 一个访问顺序; 同时, LinkedHashMap还可以用来实现LRU算法(Least Recently Used, 即最近最少使用算法); 本文将主要分析LinkedHashMap的两个大方面: 一个是遍历有序, 另一个是用于LRU算法的特性

二. 遍历有序

LinkedHashMap遍历有序, 主要是因为其在HashMap的基础上, 增加了一个双向链表, 按照元素的插入顺序或者访问顺序, 将数据重新组织成一个双向链表; 根据标志位final boolean accessOrder;来决定是按照插入顺序(insertion-order, 此时需要accessOrder = false)还是访问顺序(access-order, 此时需要accessOrder = true)来组织

LinkedHashMap改写了HashMap的节点, 如下; 在其中增加了before和after域用于帮助组织双向链表

    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

对于accessOrder值的指定只能在创建LinkedHashMap的时候, 也就是说LinkedHashMap并没有提供明确的set()方法来改变该值(一旦在构造函数中指定, 就无法改变); LinkedHashMap提供了如下构造函数可以用于指定accessOrder的值, 其余构造函数中, accessOrder都默认为false, 即默认以insertion-order的顺序组织双向链表

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

LinkedHashMap重写了HashMap的newNode()函数, newNode()在进行元素插入的时候会被HashMap.putVal()调用, LinkedHashMap用自己的Entry节点替换HashMapNode节点的同时, 进行双向链表的构建, 使得程序改动最小

    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        linkNodeLast(p); // 将节点插入到双向链表的末尾
        return p;
    }

至于linkNodeLast()函数, 即将节点插入到双向链表的末尾, 该方法比较简单, 这里就不再贴源码啦 !

那么当我们指定了accessOrder为true的时候, 即以元素访问顺序来组织双向链表的时候, 其实就只是在获取元素的时候, 将被访问的元素移动到链表末尾; 如下; 那么链表表头的元素就是最近没有被访问的元素, 这也是我们实现LRU算法的依据(稍后会细讲)

    public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder) // 如果指定为按照元素访问顺序组织元素
            afterNodeAccess(e); // 将元素移动到链表末尾
        return e.value;
    }

    void afterNodeAccess(Node<K,V> e) { // move node to last
        // 省略具体细节
        ...
    }

到这里, 我们对LinkedHashMap遍历有序的原因有了较为详细的了解; 接下来要讲的是LinkedHashMap的一个应用, 即用于实现LRU算法的特性

三. LRU算法

LRU算法即Least Recently Used, 其依据是如果数据最近被访问过, 那么其将来被访问的几率也更大

Android中的LruCache(内存缓存)内部就是利用LinkedHashMap实现的

前面我们讲了, 当accessOrder设置为true, 即按照元素访问顺序组织数据的时候, 会在get()方法中将被访问的元素移动到链表的末尾, 那么链表首部的元素就是最久没有访问的, 所以, 当要使用LinkedHashMap实现LRU的时候, 必须将accessOrder置为true

另外, 还需要我们自己去定义LRU的实现规则, 即自己定义什么时候应该移除最久没有使用的元素; 此时我们需要去重写LinkedHashMap的removeEldestEntry()函数, removeEldestEntry()是在我们插入一个元素完毕之后, 回调afterNodeInsertion()中调用的, 如下; 但是removeEldestEntry()默认返回false, 所以需要我们自己去定义规则

    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) { // 插入元素之后, 判断是否需要移除最久没有访问的元素
            K key = first.key;
            removeNode(hash(key), key, null, false, true); // 移除链表首部的元素
        }
    }

至于自定义规则, 比如: 约定最多在内存中缓存多少个元素, 超过该阈值之后, removeEldestEntry()返回true, 即将旧元素移除; 或者, 规定缓存占用多少内存, 当达到该阈值之后, 即进行旧元素移除; 当然, 这些都是后话, 具体的LRU算法, 可以根据实际需求来定

四. 总结

LinkedHashMap基于HashMap, 总体上比较简单, 主要掌握上文说的两个主要特点即可, 不再赘述 !

Java集合框架之LinkedHashMap

LinkedHashMap源码讲解

前言

正文

一. 概述

二. 遍历有序

三. LRU算法

四. 总结

FEATURED TAGS

FRIENDS