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

之前我们介绍了Map接口的两个实现类HashMapTreeMap,本节来介绍另一个实现类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对象,前驱和后继都指向自己,如下图所示:

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

执行后,图示结构如下:

添加完后,调用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,为什么呢?让我们下节来探讨。

原文发布于微信公众号 - 老马说编程(laoma_shuo)

原文发表时间:2016-10-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏闪电gogogo的专栏

【数据结构(C语言版)系列一】 线性表

数据是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

5223
来自专栏数据魔术师

数据结构-线性表|顺序表|链表(下)

1 1 1 哈喽。各位小伙伴好久不见,热心的小编赶在开学季又来给大家送上满满的干货了。祝大家开心快乐! 继上两次咱们聊了顺序表、单链表、静态链表等知识。那么热爱...

2887
来自专栏机器学习入门

LWC 62:745. Prefix and Suffix Search

LWC 62:745. Prefix and Suffix Search 传送门:745. Prefix and Suffix Search Problem: ...

2306
来自专栏编程理解

数据结构(五):哈夫曼树(Huffman Tree)

哈夫曼树(或者赫夫曼树、霍夫曼树),指的是一种满二叉树,该类型二叉树具有一项特性,即树的带权路径长最小,所以也称之为最优二叉树。

2162
来自专栏java一日一条

Java HashSet工作原理及实现

HashSet是基于HashMap来实现的,操作很简单,更像是对HashMap做了一次“封装”,而且只使用了HashMap的key来实现各种特性,我们先来感性的...

792
来自专栏专注 Java 基础分享

堆结构的优秀实现类----PriorityQueue优先队列

     之前的文章中,我们有介绍过动态数组ArrayList,双向队列LinkedList,键值对集合HashMap,树集TreeMap。他们都各自有各自的优...

2426
来自专栏java一日一条

java中HashMap详解

通过HashMap、HashSet 的源代码分析其 Hash 存储机制 实际上,HashSet 和 HashMap 之间有很多相似之处,对于 HashSet ...

1222
来自专栏你不就像风一样

Java核心数据结构(List,Map,Set)使用技巧与优化

JDK提供了一组主要的数据结构实现,如List、Map、Set等常用数据结构。这些数据都继承自 java.util.Collection 接口,并位于 java...

2923
来自专栏轮子工厂

深入理解Java中的List、Set与Map集合

784
来自专栏对角另一面

lodash源码分析之compact中的遍历

小时候, 乡愁是一枚小小的邮票, 我在这头, 母亲在那头。 长大后,乡愁是一张窄窄的船票, 我在这头, 新娘在那头。 后来啊, 乡愁是一方矮矮...

1920

扫码关注云+社区