LinkedHashMap 源码分析 - 访问

2022 年 5 月 25 日
本文字数：1543 字
阅读完需：约 5 分钟

LinkedHashMap 源码分析-

HashMap 是无序的，TreeMap 是根据 key 进行排序，而 LinkedHashMap，是根据插入顺序排序的。

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

复制代码

LinkedHashMap 继承了 HashMap ，所以它拥有 HashMap 的所有特性，额外的，LinkedHashMap 还包含了两大特性：

按照插入顺序进行访问；
实现了访问最少最先删除功能，把很久都没有访问的 key 自动删除。

LinkedHashMap 链表结构

LinkedHashMap 把 Map 的元素都串联起来，形成了一个链表，而链表可以保证顺序，如此就实现了按插入顺序访问。

    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);        }    }
    private static final long serialVersionUID = 3801124242820219131L;
    /**     * The head (eldest) of the doubly linked list.     */    transient LinkedHashMap.Entry<K,V> head;
    /**     * The tail (youngest) of the doubly linked list.     */    transient LinkedHashMap.Entry<K,V> tail;
    /**     * The iteration ordering method for this linked hash map: <tt>true</tt>     * for access-order, <tt>false</tt> for insertion-order.     *     * @serial     */    final boolean accessOrder;

复制代码

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

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

static class Entry<K,V> extends HashMap.Node<K,V> {......} 继承 Node，数组中元素属性增加了 before 和 after 属性

final boolean accessOrder; 控制两种访问模式的字段,true 按照访问顺序，会把经常访问的 key 放到队尾,false 按照插入顺序提供访问

按照顺序新增

新增节点，并追加到链表的尾部。LinkedHashMap 通过新增头节点、尾节点，给每个节点增加 before、after 属性，每次新增时，都把节点追加到尾节点等手段，在新增的时候，就已经维护了按照插入顺序的链表结构了。

    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {        LinkedHashMap.Entry<K,V> last = tail;        tail = p;        if (last == null)            head = p;        else {            p.before = last;            last.after = p;        }    }

复制代码

tail = p;新增节点等于位节点

if (last == null) head = p; last 为空，说明链表为空，首尾节点相等

else { p.before = last; last.after = p; }链表有数据，直接建立新增节点和上个尾节点之间的前后关系即可

按照顺序访问

LinkedHashMap 只提供了单向遍历访问，按照插入的顺序从头到尾进行访问。

通过迭代器进行访问，迭代器初始化的时候，默认从头节点开始访问，在迭代的过程中，不断访问当前节点的 after 节点。

        LinkedHashIterator() {            next = head;            expectedModCount = modCount;            current = null;        }
        final LinkedHashMap.Entry<K,V> nextNode() {            LinkedHashMap.Entry<K,V> e = next;            if (modCount != expectedModCount)                throw new ConcurrentModificationException();            if (e == null)                throw new NoSuchElementException();            current = e;            next = e.after;            return e;        }

复制代码

next = head;头节点作为第一个访问的节点

if (modCount != expectedModCount) throw new ConcurrentModificationException(); 校验

next = e.after; 通过链表的 after 结构，找到下一个迭代的节点

发布于: 刚刚阅读数: 3

zarmnosaj

关注

还未添加个人签名 2020.02.06 加入

还未添加个人简介

发布

暂无评论

创作场景

LinkedHashMap 源码分析 - 访问

LinkedHashMap 源码分析-

LinkedHashMap 链表结构

按照顺序新增

按照顺序访问

zarmnosaj

评论