当前位置:首页 > 分类 > JAVA基础 > JDK源码-LinkedHashMap

JDK源码-LinkedHashMap

LinkedHashMap常作为HashMap(了解HashMap)的替补出现,它继承自HashMap,并继承了HashMap百分之八十的功能,剩下的百分之二十的功能则是用于排序。


1,LinkedHashMap同样使用table存储元素,但元素不再是Node类,而是继承自Node类的Entry类。并新增了两个属性,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);
        }
    }


2,同时LinkedHashMap类新增了三个属性

     /**
     * 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;

    2.1 head 表头,表示最早放入的元素。

    2.2 tail 表尾,表示最后放入的元素。

    2.3 accessOrder 是否使用访问排序(最后一个被访问的元素放在表尾),false将使用插入顺序排序。


3,put时使用父类HashMap的put方法,并重写了put方法中调用的newNode方法。

    //HashMap
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        return new Node<>(hash, key, value, next);
    }
    
    //LinkedHashMap
    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }

    差异1:实例化Node换成了实例化Entry(Entry继承自Node),Entry类的构造器里面调用super(hash, key, value, next);也就是调用的Node的构造方法。注意是调用,不是继承。构造函数是不能继承的。此时Entry新增的before, after两个参数并没有被使用。

    差异2:Entry构造器多调了一个方法linkNodeLast。


4,linkNodeLast

 // link at the end of list
    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;
        }
    }

如果表尾是空,则把新元素同时作为表头和表尾。

如果表尾不是空,则把新元素作为表尾并链接原来的表尾。

head是当需要移除最老的元素时使用,而tail则是根据accessOrder不同,记录最后添加的元素或最后访问的元素。

这里使用了Entry新增的before, after两个参数。


5,上面说LinkedHashMap新增了三个参数,但现在只用了head和tail两个,还有一个accessOrder未使用。看下构造函数。

   
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }
    
    
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

第一个无参构造函数,调用hashmap的无参构造函数,并给final变量accessOrder赋值false。此时LinkedHashMap是一个插入顺序排序的hash表。

第二个构造函数给final变量accessOrder赋值自定义boolean参数。

默认使用插入排序,可使用第二个构造函数实现访问排序。



6,还记得hashmap中putval方法调用的空实现afterNodeAccess方法吗,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.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;
        }
    }

有注释为:// move node to last

如果accessOrder为true,则把传入的元素放到表尾。现实访问排序。

访问排序是在插入排序的基础上实现的。先new entry()插入排序,完了再put时根据accessOrder视情况实现访问排序。


7,另一个空实现的方法afterNodeInsertion也实现了。

     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);
        }
    }
    
    
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

注释为可能移除最老的元素,但由于条件中调用的removeEldestEntry方法一直返回false,所以不会移除。


总结:LinkedHashMap使用entry新增的两个参数来维护元素之间的关系。