coding……
但行好事 莫问前程

Java编程拾遗『LinkedHashMap』

在之前的文章,分别介绍过HashMap、TreeMap。HashMap就是普通的K-V存储数据结构,TreeMap在K-V存储数据结构的基础上添加了K-V之间按键值有序的特性。本篇文章来介绍一下,另一种特殊的K-V存储数据结构LinkedHashMap。LinkedHashMap是HashMap的子类,但可以保持元素按插入或访问有序(默认是按插入顺序有序)。LinkedHashMap继承关系如下:

LinkedHashMap是HashMap的子类,每个键值对都是通过之前讲HashMap的存储方式(数组 + 链表 + 红黑树)存储的,但同时内部各个键值对之间还有一个双向链表维护键值对的顺序。所以,HashMap除了键值对之间无序之外所有的特性,LinkedHashMap都有,比如存储方式、hash策略、扩容机制等。LinkedHashMap支持两种顺序,一种是插入顺序,另外一种是访问顺序。插入顺序是指,先添加的在前面,后添加的在后面,修改操作不影响顺序访问顺序是指get/put操作,对一个键执行get/put操作后,其对应的键值对会移到双向链表末尾,所以,最末尾的是最近访问的,最开始的最久没被访问的,这种顺序就是访问顺序

1. 调用示例

public static void main(String[] args) {
    /*默认构造函数,按照插入顺序有序*/
    System.out.println("按插入顺序有序:");
    Map<Integer, String> linkedHashMap = new LinkedHashMap<>();
    linkedHashMap.put(1, "a");
    linkedHashMap.put(2, "b");
    linkedHashMap.put(3, "c");
    linkedHashMap.put(4, "d");
    /*按插入顺序有序时,put修改操作,并不会改变顺序*/
    linkedHashMap.put(3, "e");

    Iterator iterator = linkedHashMap.entrySet().iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }

    /*调用
    * public LinkedHashMap(int initialCapacity,
                           float loadFactor,
                           boolean accessOrder)
      构造函数,指定accessOrder为true时,可以按照访问顺序有序
    * */
    System.out.println("按访问顺序有序:");
    linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);
    linkedHashMap.put(1, "a");
    linkedHashMap.put(2, "b");
    linkedHashMap.put(3, "c");
    linkedHashMap.put(4, "d");
    /*1 -> 2 -> 3 -> 4*/

    linkedHashMap.get(2);//2被访问了,移动到内部双向链表末尾
    /*1 -> 3 -> 4 -> 2*/

    linkedHashMap.get(4);//4被访问了,移动到内部双向链表末尾
    /*1 -> 3 -> 2 -> 4*/

    linkedHashMap.put(1, "e");//1被访问(put)了,移动到内部双向链表末尾
    /*3 -> 2 -> 4 -> 1*/

    linkedHashMap.put(5, "f");//插入5
    /*3 -> 2 -> 4 -> 1 -> 5*/

    iterator = linkedHashMap.entrySet().iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}

运行结果:

按插入顺序有序:
1=a
2=b
3=e
4=d
按访问顺序有序:
3=c
2=b
4=d
1=e
5=f

1.1 按插入有序使用场景

LinkedHashMap经常用来处理一些数据,接受一些键值对作为输入,处理,然后输出,输出时希望跟插入的顺序保持一致。比如从数据库查询数据放到内存时,已经使用SQL的order by语句让数据库对数据排序,在数据输入有序的前提下,希望通过Map存储查询结果,并且保持顺序输出,这时候就没必要使用TreeMap了,效率比LinkedHashMap低(TreeMap直接使用红黑树存储,LinkedHashMap使用Hash表),直接使用LinkedHashMap也能达到相同的排序目标。

1.2 按访问有序使用场景

上面的例子,已经讲了按访问有序的示例。那么按访问有序在开发中有什么使用场景?最常见的一个用法就是通过LinkedHashMap的按访问有序实现LRU(Least Recently Used—最近最久未使用)算法。

缓存,原始意义是指访问速度比一般随机存取存储器(RAM)快的一种RAM,通常它不像系统主存那样使用DRAM技术,而使用昂贵但较快速的SRAM技术。当CPU处理数据时,它会先到缓存中去寻找,如果数据因之前的操作已经读取而被暂存其中,就不需要再从随机存取存储器(Main memory)中读取数据——由于CPU的运行速度一般比主内存的读取速度快,主存储器周期(访问主存储器所需要的时间)为数个时钟周期。因此若要访问主内存的话,就必须等待数个CPU周期从而造成浪费。

CPU的缓存曾经是用在超级计算机上的一种高级技术,不过现今计算机上使用的的AMD或Intel微处理器都在芯片内部集成了大小不等的数据缓存和指令缓存,通称为L1缓存;而比L1更大容量的L2缓存曾经被放在CPU外部(主板或者CPU接口卡上),但是现在已经成为CPU内部的标准组件;更昂贵的CPU会配备比L2缓存还要大的L3缓存(level 3 On-die Cache第三级高速缓冲存储器)。L1容量缓存非常小、价格非常贵、读取速度快,三级缓存容量会大一些、便宜一些、读取速度也慢一些。

如今缓存的概念已被扩充,不仅在CPU和主内存之间有Cache,而且在内存和硬盘之间也有Cache(磁盘缓存),乃至在硬盘与网络之间也有某种意义上的Cache──称为Internet临时文件夹或网络内容缓存等。凡是位于速度相差较大的两种硬件之间,用于协调两者数据传输速度差异的结构,均可称之为Cache。

主存容量远大于CPU缓存,磁盘容量远大于主存,因此无论是哪一层次的缓存都面临一个同样的问题:当容量有限的缓存的空闲空间全部用完后,又有新的内容需要添加进缓存时,如何挑选并舍弃原有的部分内容,从而腾出空间放入这些新的内容。解决这个问题的算法有几种,如最久未使用算法(LFU)、先进先出算法(FIFO)、最近最少使用算法(LRU)、非最近使用算法(NMRU)等,这些算法在不同层次的缓存上执行时拥有不同的效率和代价,需根据具体场合选择最合适的一种。而本文讲的LinkedHashMap的按访问有序,就可以很容易的实现LRU算法。

LinkedHashMap中存在一个protected方法,如下:

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

这个方法用于插入键值对后调用,如果返回true,则会清除LinkedHashMap中“最老”(最久未访问)的键值对,LinkedHashMap的实现总是返回false,所以无论何时插入键值对,都不会对之前的键值对进行清除。所以如果要实现实现LRU算法,只要继承LinkedHashMap类,并按照具体策略重写此方法即可,如下:

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int maxSize;

    public LRUCache(int maxSize){
        super(16, 0.75f, true);
        this.maxSize = maxSize;
    }

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

    public static void main(String[] args) {
        LRUCache<Integer, String> lruCache = new LRUCache<>(3);
        lruCache.put(1, "a");
        lruCache.put(2, "b");
        lruCache.put(3, "c");
        //访问1->a
        //key顺序为:2 -> 3 -> 1
        System.out.println(lruCache.get(1));

        //插入一个新键值对,理论上,由于超过LruCache的maxSize了,所以会删除最老的键值对
        //插入后,删除最老键值对前,key顺序:2 -> 3 -> 1 -> 4
        //所以最老的键值对,key为2
        lruCache.put(4, "d");

        System.out.println(lruCache);
    }
}

运行结果:

a
{3=c, 1=a, 4=d}

限定缓存容量为3,先后添加了4个键值对,最久没被访问的key是”2″,会被删除。

2. 方法说明

LinkedHashMap的设计很巧妙,使用了钩子方法的设计模式,在HashMap中定义了钩子方法,然后再LinkedHashMap中实现,在钩子方法中保证键值对之间的顺序。

2.1 构造函数

S.N. 方法 说明
1 public LinkedHashMap() 默认构造函数,调用HashMap默认构造函数,元素保持按插入有序
2 public LinkedHashMap(int initialCapacity) 指定初始化时HashMap的容量,元素保持按插入有序
3 public LinkedHashMap(int initialCapacity, float loadFactor) 指定初始化时HashMap的容量和负载因子,元素保持按插入有序
4 public LinkedHashMap(Map<? extends K, ? extends V> m) 通过Map构建LinkedHashMap,,元素保持按插入有序
5 public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder)
指定初始化时HashMap的容量和负载因子,以及迭代输出节点的顺序,accessOrder为true时,
元素间保持按访问有序

2.2 Map接口

除了构造函数之外的方法,全部继承自HashMap,但是针对个别方法,进行了重写。

S.N. 方法 说明
1 void clear() 清除Map中所有的KV映射
2 default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) Java 8新方法,如果key在Map中不存在,则根据Function规则计算key对应的value值,
并进行put操作(前提计算得到的value值也不为null)
3 default V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction)
Java 8新方法,如果key在Map中存在,则根据BiFunction规则通过key和对应的value
计算newValue,如果newValue为null,则删除key对应的键值对,否则替换key对应的value值
4 default V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) Java 8新方法,相当于上述两个方法的综合,根据BiFunction,通过key和对应的value
计算newValue,如果newValue为null,会删除对应KV映射,否则会插入或替换原KV映射
5 boolean containsKey(Object key) 判断Map中是否存在key键
6 boolean containsValue(Object value) 判断Map中是否存在value值
7 Set<Map.Entry<K, V>> entrySet() 将Map所有的键值对转换为Set集合
8 boolean equals(Object o) equals方法
9 default void forEach(BiConsumer<? super K, ? super V> action) Java 8新方法,遍历Map,通过BiConsumer处理Map中每一个键值对的key、value
10 V get(Object key) 获取Map中key对应的value
11 default V getOrDefault(Object key, V defaultValue) Java 8新方法,获取Map中key对应的value,如果key不存在,则返回defaultValue
12 int hashCode() hashCode方法
13 boolean isEmpty() 判断Map是否为空
14 Set<K> keySet() 将Map中所有的key转化为Set集合
15 default V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction)
如果key在Map中不存在或者对应的值为null,则给其一个对应的非null值value。否则根据
BiFunction规则通过oldValue和value计算一个newValue,替换或删除(newValue为null)原
键值对
16 V put(K key, V value); 为Map添加一个键值对
17 void putAll(Map<? extends K, ? extends V> m) 将另一个Map的所有键值对添加到该Map中
18 default V putIfAbsent(K key, V value) Java 8新方法,如果Map中key不存在,则添加一个key-value键值对
19 V remove(Object key) 从Map中移除key对应的键值对
20 default boolean remove(Object key, Object value) Java8新方法,删除key-value键值对
21 default V replace(K key, V value) Java8新方法,将Map中key对应的值替换为value
22 default boolean replace(K key, V oldValue, V newValue) Java8新方法,将Map中key-oldValue键值对的value值替换为newValue
23 default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) Java8新方法,将Map中所有的键值对的value,替换为根据BiFunction规则通过key-value
得到的新值
24 int size() 返回Map中EntrySet的数目
25 Collection<V> values() 返回Map中所有value组成的集合

3. 实现源码分析

3.1 LinkedHashMap类声明

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
	/**
     * LinkedHashMap键值对类
     */
    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);
        }
    }

    /**
     * 双向链表头(最老的元素)
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * 双向链表尾(最新的元素)
     */
    transient LinkedHashMap.Entry<K,V> tail;

    /**
     * LinkedHashMap访问顺序:
     * true: 按访问有序
     * false: 按插入有序
     * @serial
     */
    final boolean accessOrder;

    //成员方法

}  

相比于HashMap,LinkedHashMap中的每一个节点Entry除了有一个next指针(继承自HashMap.Node)外,还有一个指向当前Entry前驱和后继的before、after指针。除此之外,还添加了一个成员变量accessOrder,表示LinkedHashMap访问顺序。LinkedHashMap可以说是通过数组 + 链表 + 红黑树 + 双向链表实现的。假设hash算法就是简单的用key mod 一下表的大小(也就是数组的长度),其中的哈希桶数组table的size=4,负载因子loadFactor=1,通过put顺序添加如下四个元素(5、1、9、3为键值对的key),则LinkedHashMap存储结构如下:


由上图可以清楚的看到,LinkedHashMap = HashMap + before&after构成的双向链当LinkedHashMap发生改变时,当前双向链表结构也会发生改变,保证head始终指向“最老”的节点,tail始终指向“最新”的节点。比如按访问有序前提下,现有LinkedHashMap结构如上图,这时候代码调用了linkedHashMap.get(1)操作,那么节点1会移动到双向链表的尾部,tail指向节点1,节点5的后继变为节点9。下面讲实现时,会详细讲解。

3.2 构造函数

/*
* 调用HashMap默认构造函数初始化HashMap,访问顺序按插入有序
*/
public LinkedHashMap() {
    super();
    accessOrder = false;
}

/*
* 指定HashMap初始容量,访问顺序按插入有序
*/
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

/*
* 通过Map初始化LinkedHashMap
*/
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    //调用HashMap默认构造函数初始化HashMap
    super();
    accessOrder = false;
    //通过调用putMapEntries方法,将Map中的键值对插入到默认构造函数构造的HashMap中
    //putMapEntries方法第二个参数控制插入后是否进行检查,清除最老元素
    //按插入有序,所以在插入元素后,不用考虑是否需要删除最老元素,直接赋值false即可
    putMapEntries(m, false);
}

/*
* 初始化一定容量,负载因子的HashMap,并指定LinkedHashMap的访问顺序
* 这个构造函数也是唯一一个能够指定访问顺序的构造函数
*/
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

3.3 put操作

LinkedHashMap类中没有重写HashMap的put和putAll,那么它是怎么实现上面讲的双向链表元素顺序的?我们可能有两个显而易见的疑问,第一LinkedHashMap的节点类型是内部类LinkedHashMap.Entry而非HashMap.Node,LinkedHashMap内部的Entry节点是如何初始化出来的;第二LinkedHashMap没有重写put/putAll方法,是通过什么方式维护双向链表的;

第一个问题,LinkedHashMap内部的Entry节点是如何实例化出来的。在之前讲HashMap的文章中,我们讲过在putVal方法中,通过调用newNode方法,构建一个待插入的Node对象,而LinkedHashMap重写了newNode方法,构建一个带插入的LinkedHashMap.Entry对象。在HashMap类中,newNode方法被putVal方法调用,而putVal方法会在put及putAll方法中调用,所以当LinkedHashMap对象调用put或putAll方法时,就能保证插入的节点是LinkedHashMap.Entry对象。

第二个问题,LinkedHashMap对象在调用put或putAll方法后,是如何保证双向链表顺序的。LinkedHashMap.newNode方法中,调用了一个linkNodeLast的linkNodeLast方法,新节点链接在内部双向链表的尾部。下面结合源码来看一下:

public V put(K key, V value) {
    // 对key的hashCode()做hash
    return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 1:tab为空则创建
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2:计算index,并对null做处理 
    if ((p = tab[i = (n - 1) & hash]) == null) 
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 3:节点key存在,直接覆盖value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 4:判断该链为红黑树
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 5:该链为链表
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key,value,null);
                     //链表长度大于8转换为红黑树进行处理
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st  
                        treeifyBin(tab, hash);
                    break;
                }
                 // key已经存在直接覆盖value
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k)))) 
                           break;
                p = e;
            }
        }
        
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }

    ++modCount;
    // 6:超过最大容量 就扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

上面是HashMap的put方法,在putVal方法中,如果需要插入节点,则调用newNode方法生成待插入的节点对象。LinkedHashMap类中重写的newNode如下:

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    //调用LinkedHashMap.Entry的构造函数,生成Entry节点
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    //调整双向链表结构,是新插入的节点p插入到双向链表尾部
    linkNodeLast(p);
    return p;
}

private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    //tail指针移到p节点
    tail = p;
    //如果插入p节点之前链表为null,则讲head指针指向新插入的节点p
    if (last == null)
        head = p;
    else {
        //讲新插入的节点p插入到双向链表尾部
        p.before = last;
        last.after = p;
    }
}

这就是为什么调用HashMap的put/putAll方法,可以生成LinkedHashMap.Entry类型的节点插入,同时可以维护双向链表顺序的原因,如下图所示:

 下面看一下HashMap类putVal方法两个比较“别致”的方法afterNodeAccess和afterNodeInsertion。这两个方法是钩子方法,在HashMap中并没有具体实现,只是一个空方法,LinkedHashMap中重写了这两个方法。

  • afterNodeAccess:负责当LinkedHashMap按访问有序时,节点被访问后,调整双向链表结构,讲最新访问的节点移动到双向链表的尾部。
  • afterNodeInsertion:负责在插入节点后检查是否需要清除最老的节点(就是上文讲的实现LRU)

LinkedHashMap中afterNodeAccess实现如下:

void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    //如果LinkedHashMap按访问有序,并且刚被访问的节点e不是双向链表尾节点,则调整双向链表
    if (accessOrder && (last = tail) != e) {
        //p为刚被访问的节点,b为p的前驱节点,a为p的后继节点
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        //首先将p的后继指针断开
        p.after = null;
        //如果p为双向链表头结点,则将head指针指向p的后继节点a
        if (b == null)
            head = a;
        else
            //如果p不是双向链表头结点,则将p的前驱节点的后继指针指向p的后继节点a
            b.after = a;
        //如果p的后继节点a不为null,则将a的前驱指针指向p的前驱节点b
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            //将p节点连接到双向链表尾部
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}


afterNodeAccess除了在HashMap类的put方法中调用外,在replace、merge、compute方法中也有调用,保证按访问有序情况下,最后被访问的节点会被移到双向链表尾部。

LinkedHashMap中afterNodeInsertion实现如下:

void afterNodeInsertion(boolean evict) {
    LinkedHashMap.Entry<K,V> first;
    //如果evit为tur(需要删除最老元素),并且双向链表不为null,并且removeEldestEntry方法返回true
    //则清除head指向的节点(最老的节点)
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

这里回头看一下本文开头讲的LRUCache类,重写了removeEldestEntry方法,因为LinkedHashMap中默认返回false,如下:

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

如果想要实现LRU,子类中要重写该方法。

3.4 remove操作

LinkedHashMap也没有重写remove()方法,remove操作是通过调用HashMap的remove方法实现的,根据上节讲的LinkedHashMap要维护双向链表,那么是不是HashMap的remove方法中定义了钩子方法,然后在LinkedHashMap中实现,删除双向链表中的相应节点,答案是肯定的。

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

afterNodeRemoval就是钩子方法,LinkedHashMap中实现如下:

/*
* LinkedHashMap删除节点后,将节点从双向链表中移除
*/
void afterNodeRemoval(Node<K,V> e) {
    //当前删除的节点是p,b是删除节点的前驱节点,a是删除节点的后继节点1
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    //首先将p的前驱指针和后继指针清空
    p.before = p.after = null;
    //如果p为双向链表头结点,则直接将head指针指向p的后继节点a
    if (b == null)
        head = a;
    //如果p不是双向链表头结点,则将p的前驱节点的后继指针指向p的后继节点a
    else
        b.after = a;
    //如果p为双向链表尾节点,则直接将tail指针指向p的前驱节点b
    if (a == null)
        tail = b;
    //如果p不是双向链表的尾节点,则将p的后继节点的前驱指针指向p的前驱节点b
    else
        a.before = b;
}

 也就是讲当LinkedHashMap删除节点,是通过调用HashMap的remove方法实现的,在HashMap删除节点后,会调用afterNodeRemoval方法,该方法在LinkedHashMap中实现,讲待删除节点从双向链表中移除。

3.5 get方法

LinkedHashMap中重写了HashMap的get方法,如果LinkedHashMap按访问有序,则在访问后会调用上面讲的afterNodeAccess方法,调整双向链表结构。实现如下:

public V get(Object key) {
    Node<K,V> e;
    //调用HashMap的getNode方法,获取key对应的Node节点
    if ((e = getNode(hash(key), key)) == null)
        return null;
    //如果LinkedHashMap按访问有序,则将刚访问的节点e,移动到双向链表的尾部
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

同样,getOrDefault的实现思想也是一样的,如下:

public V getOrDefault(Object key, V defaultValue) {
   Node<K,V> e;
   if ((e = getNode(hash(key), key)) == null)
       return defaultValue;
   if (accessOrder)
       afterNodeAccess(e);
   return e.value;
}

其实对比HashMap的实现,可以发现,LinkedHashMap其实就是比HashMap多了个如果按访问有序,则维护双向链表的逻辑。

3.6 containsKey方法

LinkedHashMap中没有重写containsKey方法,完全复用HashMap的containsKey方法,因为判断key是否存在,不涉及双向链表的维护,且HashMap的containsKey方法的时间复杂度为O(1),效率较高,没必要重写。

3.7 containsValue方法

HashMap中判断value是否存在,是通过遍历hash桶数组的每个元素,然后依次判断链表/红黑树中是否存在相等的value得到的,如下:

public boolean containsValue(Object value) {
    Node<K,V>[] tab; V v;
    if ((tab = table) != null && size > 0) {
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                if ((v = e.value) == value ||
                    (value != null && value.equals(v)))
                    return true;
            }
        }
    }
    return false;
}

两层for循环,时间复杂度应该在O(n) ~ O(n^2)之间。虽然判断value在Map中是否存在也不涉及双向链表的改变,但LinkedHashMap依然没有采用这种方式,因为LinkedHashMap内部维护了一个双向链表,直接通过双向链表访问HashMap所有节点,依次判断即可,时间复杂度为O(n)。LinkedHashMap中重写的containsValue方法如下:

public boolean containsValue(Object value) {
    //遍历双向链表,判断value是否存在
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}

4. LinkedHashMap特点

  • LinkedHashMap是基于HashMap实现的,除了HashMap键值对之间无序这一特点之外的特点,LinkedHashMap都有
  • LinkedHashMap可以保证插入有序或访问有序,访问有序可以很方便地实现LRU算法

参考链接:

  1. Java API源码
  2. 《Java编程的逻辑》

赞(0) 打赏
Zhuoli's Blog » Java编程拾遗『LinkedHashMap』
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

zhuoli's blog

联系我关于我

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏