计算机程序的思维逻辑 (49) - 剖析LinkedHashMap

之前我们介绍了Map接口的两个实现类HashMap和TreeMap,本节来介绍另一个实现类LinkedHashMap。它是HashMap的子类,但可以保持元素按插入或访问有序,这与TreeMap按键排序不同。

按插入有序容易理解,按访问有序是什么意思呢?这两个有序有什么用呢?内部是怎么实现的呢?本节就来探讨这些问题。从用法开始。

用法

基本概念

LinkedHashMap是HashMap的子类,但内部还有一个双向链表维护键值对的顺序,每个键值对既位于哈希表中,也位于这个双向链表中。

LinkedHashMap支持两种顺序,一种是插入顺序,另外一种是访问顺序。

插入顺序容易理解,先添加的在前面,后添加的在后面,修改操作不影响顺序。

访问顺序是什么意思呢?所谓访问是指get/put操作,对一个键执行get/put操作后,其对应的键值对会移到链表末尾,所以,最末尾的是最近访问的,最开始的最久没被访问的,这种顺序就是访问顺序。

LinkedHashMap有五个构造方法,其中四个都是按插入顺序,如下所示:

public LinkedHashMap()
public LinkedHashMap(int initialCapacity)
public LinkedHashMap(int initialCapacity, float loadFactor)
public LinkedHashMap(Map<? extends K, ? extends V> m)

只有一个构造方法,可以指定按访问顺序,如下所示:

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder)

其中参数accessOrder就是用来指定是否按访问顺序,如果为true,就是访问顺序。

下面,我们通过一些简单的例子来看下。

按插入有序

默认情况下,LinkedHashMap是按插入有序的,我们来看代码:

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.println(entry.getKey()+" "+entry.getValue());
}

键是按照"c", "d", "a"的顺序插入的,修改"d"的值不会修改顺序,所以输出为:

c 100
d 300
a 500

什么时候希望保持插入顺序呢?

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

再比如,希望的数据模型可能就是一个Map,但希望保持添加的顺序,比如一个购物车,键为购买项目,值为购买数量,按用户添加的顺序保存。

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

按访问有序

我们来看按访问有序的例子,代码如下:

Map<String,Integer> accessMap = new LinkedHashMap<>(16, 0.75f, true);

accessMap.put("c", 100);
accessMap.put("d", 200);
accessMap.put("a", 500);
accessMap.get("c");
accessMap.put("d", 300);

for(Entry<String,Integer> entry : accessMap.entrySet()){
    System.out.println(entry.getKey()+" "+entry.getValue());
}

每次访问都会将该键值对移到末尾,所以输出为:

a 500
c 100
d 300

什么时候希望按访问有序呢?一种典型的应用是LRU缓存,它是什么呢?

LRU缓存

缓存是计算机技术中一种非常有用的技术,是一个通用的提升数据访问性能的思路,一般用来保存常用的数据,容量较小,但访问更快,缓存是相对而言的,相对的是主存,主存的容量更大、但访问更慢。缓存的基本假设是,数据会被多次访问,一般访问数据时,都先从缓存中找,缓存中没有再从主存中找,找到后,再放入缓存,这样,下次如果再找相同数据,访问就快了。

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

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

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

使用LinkedHashMap,可以非常容易的实现LRU缓存,默认情况下,LinkedHashMap没有对容量做限制,但它可以容易的做的,它有一个protected方法,如下所示:

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

在添加元素到LinkedHashMap后,LinkedHashMap会调用这个方法,传递的参数是最久没被访问的键值对,如果这个方法返回true,则这个最久的键值对就会被删除。LinkedHashMap的实现总是返回false,所有容量没有限制,但子类可以重写该方法,在满足一定条件的情况,返回true。

下面就是一个简单的LRU缓存的实现,它有一个容量限制,这个限制在构造方法中传递,代码是:

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;
    }
}

这个缓存可以这么用:

LRUCache<String,Object> cache = new LRUCache<>(3);
cache.put("a", "abstract");
cache.put("b", "basic");
cache.put("c", "call");
cache.get("a");

cache.put("d", "call");
System.out.println(cache);

限定缓存容量为3,先后添加了4个键值对,最久没被访问的键是"b",会被删除,所以输出为:

{c=call, a=abstract, d=call}

实现原理

理解了LinkedHashMap的用法,下面我们来看其实现代码。关于代码,我们说明下,本系列文章,如果没有额外说明,都是基于JDK 7的。

内部组成

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

private transient Entry<K,V> header;
private final boolean accessOrder;

accessOrder表示是按访问顺序还是插入顺序。header表示双向链表的头,它的类型Entry是一个内部类,这个类是HashMap.Entry的子类,增加了两个变量before和after,指向链表中的前驱和后继,Entry的完整定义为:

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中,将该节点从链表中移除。

了解了内部组成,我们来看操作方法,先看构造方法。

构造方法

在HashMap的构造方法中,会调用init方法,init方法在HashMap的实现中为空,也是被设计用来被重写的。LinkedHashMap重写了该方法,用于初始化链表的头节点,代码如下:

void init() {
    header = new Entry<>(-1, null, null, null);
    header.before = header.after = header;
}

header被初始化为一个Entry对象,前驱和后继都指向自己,如下图所示:

计算机程序的思维逻辑 (49) - 剖析LinkedHashMap

header.after指向第一个节点,header.before指向最后一个节点,指向header表示链表为空。

put方法

在LinkedHashMap中,put方法还会将节点加入到链表中来,如果是按访问有序的,还会调整节点到末尾,并根据情况删除最久没被访问的节点。

HashMap的put实现中,如果是新的键,会调用addEntry方法添加节点,LinkedHashMap重写了该方法,代码为:

void addEntry(int hash, K key, V value, int bucketIndex) {
    super.addEntry(hash, key, value, bucketIndex);

    // Remove eldest entry if instructed
    Entry<K,V> eldest = header.after;
    if (removeEldestEntry(eldest)) {
        removeEntryForKey(eldest.key);
    }
}

它先调用父类的addEntry方法,父类的addEntry会调用createEntry创建节点,LinkedHashMap重写了createEntry,代码为:

void createEntry(int hash, K key, V value, int bucketIndex) {
    HashMap.Entry<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<>(hash, key, value, old);
    table[bucketIndex] = e;
    e.addBefore(header);
    size++;
}

新建节点,加入哈希表中,同时加入链表中,加到链表末尾的代码是:

e.addBefore(header)

比如,执行如下代码:

Map<String,Integer> countMap = new LinkedHashMap<>();
countMap.put("hello", 1);

执行后,图示结构如下:

计算机程序的思维逻辑 (49) - 剖析LinkedHashMap

添加完后,调用removeEldestEntry检查是否应该删除老节点,如果返回值为true,则调用removeEntryForKey进行删除,removeEntryForKey是HashMap中定义的方法,删除节点时会调用HashMap.Entry的recordRemoval方法,该方法被LinkedHashMap.Entry重写了,会将节点从链表中删除。

在HashMap的put实现中,如果键已经存在了,则会调用节点的recordAccess方法,LinkedHashMap.Entry重写了该方法,如果是按访问有序,则调整该节点到链表末尾。

get方法

LinkedHashMap重写了get方法,代码为:

public V get(Object key) {
    Entry<K,V> e = (Entry<K,V>)getEntry(key);
    if (e == null)
        return null;
    e.recordAccess(this);
    return e.value;
}

与HashMap的get方法的区别,主要是调用了节点的recordAccess方法,如果是按访问有序,recordAccess调整该节点到链表末尾。

查看是否包含某个值

查看HashMap中是否包含某个值需要进行遍历,由于LinkedHashMap维护了单独的链表,它可以使用链表进行更为高效的遍历,containsValue的代码为:

public boolean containsValue(Object value) {
    // Overridden to take advantage of faster iterator
    if (value==null) {
        for (Entry e = header.after; e != header; e = e.after)
            if (e.value==null)
                return true;
    } else {
        for (Entry e = header.after; e != header; e = e.after)
            if (value.equals(e.value))
                return true;
    }
    return false;
}

代码比较简单,就不解释了。

原理小结

以上就是LinkedHashMap的基本实现原理,它是HashMap的子类,它的节点类LinkedHashMap.Entry是HashMap.Entry的子类,LinkedHashMap内部维护了一个单独的双向链表,每个节点即位于哈希表中,也位于双向链表中,在链表中的顺序默认是插入顺序,也可以配置为访问顺序,LinkedHashMap及其节点类LinkedHashMap.Entry重写了若干方法以维护这种关系。

LinkedHashSet

之前介绍的Map接口的实现类都有一个对应的Set接口的实现类,比如HashMap有HashSet,TreeMap有TreeSet,LinkedHashMap也不例外,它也有一个对应的Set接口的实现类LinkedHashSet。LinkedHashSet是HashSet的子类,但它内部的Map的实现类是LinkedHashMap,所以它也可以保持插入顺序,比如:

Set<String> set = new LinkedHashSet<>();
set.add("b");
set.add("c");
set.add("a");
set.add("c");

System.out.println(set);

输出为:

[b, c, a]

LinkedHashSet的实现比较简单,我们就不再介绍了。

小结

本节主要介绍了LinkedHashMap的用法和实现原理,用法上,它可以保持插入顺序或访问顺序,插入顺序经常用于处理键值对的数据,并保持其输入顺序,也经常用于键已经排好序的场景,相比TreeMap效率更高,访问顺序经常用于实现LRU缓存。实现原理上,它是HashMap的子类,但内部有一个双向链表以维护节点的顺序。

最后,我们简单介绍了LinkedHashSet,它是HashSet的子类,但内部使用LinkedHashMap。

如果需要一个Map的实现类,并且键的类型为枚举类型,可以使用HashMap,但应该使用一个专门的实现类EnumMap,为什么呢?让我们下节来探讨。

----------------

未完待续,查看最新文章,敬请关注微信公众号“老马说编程”(扫描下方二维码),从入门到高级,深入浅出,老马和你一起探索Java编程及计算机技术的本质。用心原创,保留所有版权。