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

骑猪看日落 2023-07-10 15:50 19阅读 0赞

### 文章目录 ###

*  简介
 *  继承体系
 *  数据结构
 *  源码解析
 *   *  1.属性
     *  2.构造方法
     *   *  LinkedHashMap()
         *  LinkedHashMap(int initialCapacity)
         *  LinkedHashMap(int initialCapacity, float loadFactor)
         *  LinkedHashMap(Map<? extends K, ? extends V> m)
         *  LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder)
     *  3.添加元素及删除元素
     *   *  putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict)
     *  4.获取元素
 *  总结
 *  \*LinkedHashMap如何实现LRU缓存淘汰策略呢？\*

# 简介 #

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

# 继承体系 #

![图片][format_png]

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

# 数据结构 #

![图片][format_png 1]

# 源码解析 #

## 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.添加元素及删除元素 ##

![图片][format_png 2]

上图为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]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWRlci5zaGltby5pbS9mL1ZVY2t0SW1PSUxNRXkwdjcucG5nIXRodW1ibmFpbA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWRlci5zaGltby5pbS9mL3VLdzhrTW9IdUtJSFlkNUoucG5nIXRodW1ibmFpbA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWRlci5zaGltby5pbS9mLzNISGxoQXRxUmNvZmNDdlMucG5nIXRodW1ibmFpbA?x-oss-process=image/format,png