Java LinkedHashMap源码解析

上周把HashMapTreeMap这两个Map体系中比较有代表性的类介绍完了,大家应该也能体会到,如果该类所对应的数据结构与算法掌握好了,再看这些类的源码真是太简单不过了。

其次,我希望大家能够触类旁通,比如我们已经掌握了HashMap的原理,我们可以推知HashSet的内部实现

HashSet 内部用一个HashMap对象存储数据,更具体些,只用到了key,value全部为一dummy对象。

HashSet这个类太简单了,我不打算单独写文章介绍。今天介绍个比较实用的类——LinkedHashMap

签名

public class LinkedHashMap<K,V>
       extends HashMap<K,V>
       implements Map<K,V>

可以看到,LinkedHashMap是HashMap的一子类,它根据自身的特性修改了HashMap的内部某些方法的实现,要想知道LinkedHashMap具体修改了哪些方法,就需要了解LinkedHashMap的设计原理了。

设计原理

双向链表

LinkedHashMap是key键有序的HashMap的一种实现。它除了使用哈希表这个数据结构,使用双向链表来保证key的顺序

双向链表

双向链表算是个很常见的数据结构,上图中的头节点的prev、尾节点的next指向null,双向链表还有一种变种,见下图

环型双向链表

可以看到,这种链表把首尾节点相连,形成一个环。

LinkedHashMap中采用的这种环型双向链表,环型双向链表的用途比较多,感兴趣可以看这里:

双向链表这种数据结构,最关键的是保证在增加节点、删除节点时不要断链,后面在分析LinkedHashMap具体代码时会具体介绍,这里就不赘述了。

LinkedHashMap 特点

一般来说,如果需要使用的Map中的key无序,选择HashMap;如果要求key有序,则选择TreeMap。
但是选择TreeMap就会有性能问题,因为TreeMap的get操作的时间复杂度是O(log(n))的,相比于HashMap的O(1)还是差不少的,LinkedHashMap的出现就是为了平衡这些因素,使得

能够以O(1)时间复杂度增加查找元素,又能够保证key的有序性

此外,LinkedHashMap提供了两种key的顺序:

  • 访问顺序(access order)。非常实用,可以使用这种顺序实现LRU(Least Recently Used)缓存
  • 插入顺序(insertion orde)。同一key的多次插入,并不会影响其顺序

源码分析

首先打开eclipse的outline面版看看LinkedHashMap里面有那些成员

LinkedHashMap结构
可以看到,由于LinkedHashMap继承自HashMap,所以大部分的方法都是根据key的有序性而重写了HashMap中的部分方法。

构造函数

//accessOrder为true表示该LinkedHashMap的key为访问顺序
//accessOrder为false表示该LinkedHashMap的key为插入顺序
private final boolean accessOrder;
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    //默认为false,也就是插入顺序
    accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
public LinkedHashMap() {
    super();
    accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super(m);
    accessOrder = false;
}
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}
/**
 * Called by superclass constructors and pseudoconstructors (clone,
 * readObject) before any entries are inserted into the map.  Initializes
 * the chain.
 */
@Override
void init() {
    header = new Entry<>(-1, null, null, null);
    //通过这里可以看出,LinkedHashMap采用的是环型的双向链表
    header.before = header.after = header;
}

LinkedHashMap.Entry

private static class Entry<K,V> extends HashMap.Entry<K,V> {
    // These fields comprise the doubly linked list used for iteration.
    //每个节点包含两个指针,指向前继节点与后继节点
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
        super(hash, key, value, next);
    }
    /**
     * Removes this entry from the linked list.
     */
    //删除一个节点时,需要把
    //1. 前继节点的后继指针 指向 要删除节点的后继节点
    //2. 后继节点的前继指针 指向 要删除节点的前继节点 
    private void remove() {
        before.after = after;
        after.before = before;
    }
    /**
     * Inserts this entry before the specified existing entry in the list.
     */
    //在某节点前插入节点
    private void addBefore(Entry<K,V> existingEntry) {
        after  = existingEntry;
        before = existingEntry.before;
        before.after = this;
        after.before = this;
    }
    /**
     * This method is invoked by the superclass whenever the value
     * of a pre-existing entry is read by Map.get or modified by Map.set.
     * If the enclosing Map is access-ordered, it moves the entry
     * to the end of the list; otherwise, it does nothing.
     */
    void recordAccess(HashMap<K,V> m) {
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
        // 如果需要key的访问顺序,需要把
        // 当前访问的节点删除,并把它插入到双向链表的起始位置
        if (lm.accessOrder) {
            lm.modCount++;
            remove();
            addBefore(lm.header);
        }
    }
    void recordRemoval(HashMap<K,V> m) {
        remove();
    }
}

为了更形象表示双向链表是如何删除、增加节点,下面用代码加图示的方式

删除节点

删除节点
上图中,删除的是b节点

private void remove() {
    before.after = after;  //相当于上图中的操作 1
    after.before = before; //相当于上图中的操作 3
}

增加节点

增加节点
上图中的c节点相当于下面代码中的existingEntry,要插入的是x节点

private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;         //相当于上图中的操作 1
    before = existingEntry.before;  //相当于上图中的操作 3
    before.after = this;            //相当于上图中的操作 4
    after.before = this;            //相当于上图中的操作 2
}

知道了增加节点的原理,下面看看LinkedHashMap的代码是怎么实现put方法的

 

/**
* This override alters behavior of superclass put method. It causes newly
* allocated entry to get inserted at the end of the linked list and
* removes the eldest entry if appropriate.
*/
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;
//如果有必要移除最老的节点,那么就移除。LinkedHashMap默认removeEldestEntry总是返回false
//也就是这里if里面的语句永远不会执行
//这里removeEldestEntry主要是给LinkedHashMap的子类留下的一个钩子
//子类完全可以根据自己的需要重写removeEldestEntry,后面我会举个现实中的例子



相关文章

发表评论

Comment form

(*) 表示必填项

还没有评论。

跳到底部
返回顶部