LinkedHashMap 集合源码分析

LinkedHashMap__0">LinkedHashMap 集合源码分析

文章目录

LinkedHashMap 集合源码分析
一、字段分析
二、内部类分析
三、构造方法分析
四、内部方法分析
五、总结

在这里插入图片描述

LinkedHashMap 是 HashMap 的子类，在 HashMap 的基础上维护了双向链表，保证了有序性。默认是不排序的，可在初始化时传入 accessOrder = true，则进行排序

一、字段分析

java">// 指向LinkedHashMap 维护的双向链表的头结点
transient LinkedHashMap.Entry<K,V> head;
// 指向LinkedHashMap 维护的双向链表的尾结点
transient LinkedHashMap.Entry<K,V> tail;
// 是否排序：默认false：不排序。设为true时：越近访问的节点越靠近尾结点，即头结点 -> 尾结点
// 按 最近访问时间降序排列，即越靠近尾结点，离上次访问时间越近。
final boolean accessOrder;

二、内部类分析

java">//可以看到是继承了 hashmap 的 node，再次基础上多了 before 和  after，就是用来维护双向链表的
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);
        }
    }

三、构造方法分析

java">	//传入默认的初始容量 和 加载因子，默认不排序
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

   //闯入默认的初始容量，默认不排序
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

    //无参构造，默认不排序
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }
	
	//传入集合m来，使用集合m的所有元素来构建 LinkedHashMap，默认不排序
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }

    //传入初始容量，加载因子，也可指定进行排序即true
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

四、内部方法分析

LinkedHashMap 的添加元素、删除元素，扩容等方法都是直接使用了 HashMap 的方法。
但在 HashMap 的基础上做了扩展，体现了多态性。主要是三种方法：
- afterNodeRemoval：将被删除的节点从 LinkedHashMap 维护的双向链表中移除。
- afterNodeInsertion：用来判断是否删除 LinkedHashMap 维护的双向链表的头结点，即最久未被访问的节点。
- afterNodeAccess：将传入的node节点放置末尾，即最近访问的元素。

java">    //将 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;
    }
	
	//evict：true：删除最久未被访问的元素，即双向链表的头结点
    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

	//节点e是刚刚访问的节点，判断是否需将其移动至双向链表的尾结点
    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.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

五、总结

我们知道 HashMap 并不能保证有序性，而 LinkedHashMap 作为 HashMap 子类解决了排序的问题。在构造时，通过传入afterNodeAccess = true 来设置LinkedHashMap是有序的。
通过维护双向来链表来保证有序性，拥有变量 head 和 tail 分别指向双向链表的头结点和尾结点，越靠近尾结点，越是最近访问的节点，越是靠近头结点，越是越久未被访问的节点。

可用于实现 LRU 算法：

使用 LinkedHashMap 实现 LRU：

java">class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int capacity;
    
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

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

不适用 LinkedHashMap 实现 LRU：

java">class LRUCache {
    
    static class Node{
        public int key;
        public int val;
        public Node prev;
        public Node next;
        public Node(){
            this.key = -1;
            this.val = -1;
        }
        public Node(int key,int val){
            this.key = key;
            this.val = val;
        }
    }
    //最大容量    
    int capacity;
    //节点数量
    int size;
    //虚拟头节点
    Node dummyHead;
    //虚拟尾节点
    Node dummyTail;
    
    Map<Integer,Node> map = new HashMap<>();
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        dummyHead = new Node();
        dummyTail = new Node();
        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }
    
    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }
        Node node = map.get(key);
        
        //将该节点从原位置删除
        remove(node);
        //将该节点添加到链表尾部
        addLeast(node);
        
        return node.val;
    }
    
    public void put(int key, int value) {
        Node cur = new Node(key,value);
        remove(map.get(key));
        addLeast(cur);
    }
    
    //删除节点
    public void remove(Node node){
        if(node == null) return;
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.next = null;
        node.prev = null;
        size --;
        
        map.remove(node.key);
    }
    
    //将节点添加到尾部
    public void addLeast(Node node){
        Node prev = dummyTail.prev;
        prev.next = node;
        node.prev = prev;
        node.next = dummyTail;
        dummyTail.prev = node;
        size ++;
        map.put(node.key,node);
        //超过最大容量了
        if(size > capacity){
            removeFirst();
        }
    }
    
    //删除头节点
    public Node removeFirst(){
        if(dummyHead.next == dummyTail) return null;
        Node remove = dummyHead.next;
        remove(remove);
        return remove;
    }
}