LinkedHashMap

LinkedHashMap 源码阅读

---

概要

• 类继承关系

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

LinkedHashMap继承自HashMap

• 核心成员变量

jdk 7:(下文都是该环境)

/**
 * The head of the doubly linked list.
 */
private transient Entry<K,V> header;   //链表头结点

final boolean accessOrder;   //按元素插入顺序(默认)或元素最近访问顺序(LRU)排列

jdk 8:

transient LinkedHashMap.Entry<K,V> head;   //链表头结点

transient LinkedHashMap.Entry<K,V> tail;  //链表尾节点

final boolean accessOrder;

jdk 8中新增了一个链表尾节点

• 特点

一般来说，如果需要使用的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的多次插入，并不会影响其顺序

设计原理

• 环型双向链表

LinkedHashMap中采用就是这种环型双向链表

• LinkedHashMap 结构图

采用双向链表（doubly-linked list）的形式将所有entry连接起来，这样是为保证元素的迭代顺序跟插入顺序相同;header指向双向链表的头部（是一个哑元），该双向链表的迭代顺序就是entry的插入顺序。

源码分析

• 构造函数

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

• 内部节点

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

Entry继承自HashMap.Entry，同时增加了指向前一个和后一个节点的引用。

• put方法

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。可以看下文LRU cache实现例子
    if (removeEldestEntry(eldest)) {
        //从这里看，最久未访问的节点是头部节点
        removeEntryForKey(eldest.key);
    }
}

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;
    //这里把新增的Entry加到了双向链表的header的前面，成为新的header
    e.addBefore(header);
    size++;
}   

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

上面是LinkedHashMap中重写了HashMap的两个方法，当调用put时添加Entry（新增Entry之前不存在）整个方法调用链是这样的：

HashMap.put -> LinkedHashMap.addEntry ->
HashMap.addEntry -> LinkedHashMap.createEntry

注意，通过addEntry()方法插入新的entry，这里的插入有两重含义：

1. 从table的角度看，新的entry需要插入到对应的bucket里，当有哈希冲突时，采用头插法将新的entry插入到冲突链表的头部。
2. 从header的角度看，新的entry需要插入到双向链表的尾部。

上述代码中用到了addBefore()方法将新entry e插入到双向链表头引用header的前面，这样e就成为双向链表中的最后一个元素。头结点代表最久未访问的节点。

• get方法

public V get(Object key) {
        Entry<K,V> e = (Entry<K,V>)getEntry(key);
        if (e == null)
            return null;
        // 如果是key的访问顺序，需要把
        // 当前访问的节点删除，并把它插入到双向链表的尾部
        e.recordAccess(this);
        return e.value;
    }

LRU Cache

利用LinkedHashMap简单视线LRU cache.

public class LRUCache {
    
    private int capacity;
    private Map<Integer, Integer> cache;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        // access_order为true，按访问顺序排序
        this.cache = new java.util.LinkedHashMap<Integer, Integer> (capacity, 0.75f, true) {
            // 定义put后的移除规则，大于容量就删除eldest
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;
            }
        };
    }
    
    public int get(int key) {
        if (cache.containsKey(key)) {
            return cache.get(key);
        } else
            return -1;
    }
    
    public void set(int key, int value) {
        cache.put(key, value);
    }
}