LinkedHashMap源码剖析

LinkedHashMap源码导读:

1,概述

2,LinkedHashMap与hashMap的一些关系

3,LinkedHashMap核心成员变量

4,LinkedHashMap核心方法

1,概述

前面讲了hashMap的一些原理,LinkedHashMap继承自hashMap,这篇文章我们来大概看看LinkedHashMap的原理。首先说明一下,HashMap是无序的也就是不会基于插入的顺序来读取,这种场景之下就会考虑使用LinkedHashMap。

2,LinkedHashMap与HashMap的一些关系

LinkedHashMap继承自HashMap,也就是是HashMap的子类,在HashMap那篇文章中,有一些回调函数就是子类来实现的,所以等会我们可以来看看。

HashMap数据结构存放的元素是一个内部实现的类:Node<K,V>,同理LinkedHashMap也有个类似的元素Entry,也是继承自HashMap的Node<K,V>:

    static class Entry<K,V> extends HashMap.Node<K,V> {
        #多出来两个节点:before、after 可以组成一个双向链表,保持顺序。
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

3,LinkedHashMap核心成员变量

    //用于指向双向链表的头部
    transient LinkedHashMap.Entry<K,V> head;
    //用于指向双向链表的尾部
    transient LinkedHashMap.Entry<K,V> tail;
    //用来指定LinkedHashMap的迭代顺序:true表示的是按照基于访问的顺序来排序,就是把最近读的元素,放在链表的尾部;false表示的是按照插入的顺序来排序。
    final boolean accessOrder;

4,LinkedHashMap核心方法

4.1 put()

通过查看源码可以发现,LinkedHashMap调用的就是HashMap的put()方法。不过LinkedHashMap复写了其中的3个方法:newNode()、afterNodeAccess()、afterNodeInsertion()

    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        #构造了一个LinkedHashMap.Entry对象,并调用linkNodeLast方法
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        
        linkNodeLast(p);
        return p;
    }

下面看看linkNodeLast()方法:

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

下面简单画个图,看看这个执行过程会怎么样。场景是:三个节点没有冲突,插入的图形是怎么样的:

可以看出来是一个双向链表维持了一个顺序,遍历的时候只要知道首尾,就可以维持住顺序。

我来评几句
登录后评论

已发表评论数()

相关站点

热门文章