【Java集合】--LinkedHashMap源码解析

目录

简介

LinkedHashMap内部维护了一个双向链表,能保证元素按插入的顺序访问,也能以访问顺序访问,所以可以用来实现LRU缓存策略。

继承体系

【Java集合】--LinkedHashMap源码解析

可知该集合继承了HashMap,拥有HashMap的部分特性。又有链表的有序

数据结构

【Java集合】--LinkedHashMap源码解析

源码解析

1.属性

//存放头节点
transient LinkedHashMap.Entry<K,V> head;
//存放尾节点
transient LinkedHashMap.Entry<K,V> tail;
//访问顺序ture为访问顺序false为插入顺序
final boolean accessOrder;

2.构造方法

LinkedHashMap()

public LinkedHashMap() {
    //设置默认访问因子,同HashMap,为0.75。默认容量16
    super();
    //表示按插入顺序排序
    accessOrder = false;
}

LinkedHashMap(int initialCapacity)

// 构造一个空的按插入顺序排序的 LinkedHashMap 实例,初始容量为 initialCapacity 的二次幂取整的值 和负载因子(0.75)。
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}

LinkedHashMap(int initialCapacity, float loadFactor)

//通过给定的数值构造一个LinkedHashMap对象
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;

LinkedHashMap(Map<? extends K, ? extends V> m)

public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    putMapEntries(m, false);
}

LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder)

// 该构造方法accessOrder从构造方法参数传入,如果传入true,则就实现了按访问顺序存储元素,这也是实现LRU缓存策略的关键。
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

3.添加元素及删除元素

【Java集合】--LinkedHashMap源码解析

上图为LinkwdHashMap的内部方法,可以看到没有相应的put及remove方法。而LinkedHashMap又是继承自HashMap,故可以推测出LinkedHashMap的调用了HashMap中的对应方法。

putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)

//位于HashMap中
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    /*代码省略*/
    afterNodeAccess(e);
    /*代码省略*/
    afterNodeInsertion(evict);
    return null;
}

在HashMap的putVal方法中有以上两个方法没有具体实现,是给其具体继承类来实现。故在LinkedHashMap中:

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    //如果默认排序方式按访问来排序,且被访问节点不是尾节点
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        //把p节点从双向链表中移除
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        //把p头节点链表末尾
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}
void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // 如果evict为true,且头节点不为空,且确定移除最老的元素,那么就调用HashMap.removeNode()把双向链表的头节点移除
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}
// 这里调用的是 HashMap 中的方法删除,已在 HashMap 中分析过
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;
}
//e节点从链中被删除
void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}

4.获取元素

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

如果元素存在且内部按照访问顺序排序,则在排序后返回value,否则直接返回

总结

  • LinkedHashMap继承自HashMap,具有HashMap的所有特性;
  • LinkedHashMap内部维护了一个双向链表存储所有的元素;
  • 如果accessOrder为false,则可以按插入元素的顺序遍历元素;
  • 如果accessOrder为true,则可以按访问元素的顺序遍历元素;
  • LinkedHashMap的实现非常精妙,很多方法都是在HashMap中留的钩子(Hook),直接实现这些Hook就可以实现对应的功能了,并不需要再重写put()等方法;
  • 默认的LinkedHashMap并不会移除旧元素,如果需要移除旧元素,则需要重写removeEldestEntry()方法设定移除策略;
  • LinkedHashMap可以用来实现LRU缓存淘汰策略

LinkedHashMap如何实现LRU缓存淘汰策略呢?

LRU,Least Recently Used,最近最少使用,也就是优先淘汰最近最少使用的元素。

如果使用LinkedHashMap,我们把accessOrder设置为true是不是就差不多能实现这个策略了呢?答案是肯定的。请看下面的代码:

public class LRUDemo {

    public static void main(String[] args) {
        LRU lru = new LRU(3);
        lru.put("1","a");
        lru.put("2","b");
        lru.put("3","c");
        System.out.println(lru.entrySet());

        lru.get("3");
        lru.get("3");
        lru.get("3");
        System.out.println(lru.entrySet());
        lru.put("4","d");
        System.out.println(lru.entrySet());
    }
}
class LRU extends LinkedHashMap{
    private int capacity;

    public LRU(int capacity){
        //此处一定要默认为true,true才是按访问顺序排序
        super(capacity,0.75f,true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size()>this.capacity;
    }
}

运行结果:

[1=a, 2=b, 3=c]
[1=a, 2=b, 3=c]
[2=b, 3=c, 4=d]
上一篇:总结oninput、onchange与onpropertychange事件的使用方法和差别


下一篇:LinkedHashMap 底层分析