【Java源码分析】LinkedHashMap源码分析

刺骨的言语ヽ痛彻心扉 2022-07-20 12:05 297阅读 0赞

类的定义

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

1.  基于双向链表实现，属于Map的一类，其父类是HashMap。最主要的是LinkedHashMap可以保证迭代顺序。如果既想要使用Map的功能又想要键值对插入和取出是有序的，可以使用LinkedHashMap
2.  **键和值支持任意类型，包括null**
3.  迭代的顺序就是键值对被插入Map的顺序。如果三个参数的构造方法中accessOrder参数被设置为true，那么键值对的迭代顺序就变为访问顺序（可以影响访问的操作是put get putAll），在Android的LRUCache中使用的数据结构就是LinkedHashMap。
4.  非线程安全的，如果同时有多个线程执行改变Map结构的操作如put或者remove等操作的时候就需要调用者保证线程安全性
5.  迭代器进行迭代的时候同样是不允许有修改Map结构的操作，否则抛出`ConcurrentModificationException`

主要成员变量

// true的时候按访问顺序排列键值对，false的时候按插入顺序
    private final boolean accessOrder;
    transient LinkedEntry<K, V> header;

构造函数

public LinkedHashMap() {
        init();
        accessOrder = false;
    }
    
    public LinkedHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        this(initialCapacity, loadFactor, false);
    }
    
    public LinkedHashMap(
            int initialCapacity, float loadFactor, boolean accessOrder) {
        super(initialCapacity, loadFactor);
        init();
        this.accessOrder = accessOrder;
    }
    
    public LinkedHashMap(Map<? extends K, ? extends V> map) {
        this(capacityForInitSize(map.size()));
        constructorPutAll(map);
    }

构造函数和前面的集合类差不多，只是这里多了一个访问顺序的标志位

键值对实体

static class LinkedEntry<K, V> extends HashMapEntry<K, V> {
        LinkedEntry<K, V> nxt;
        LinkedEntry<K, V> prv;
    
        /** Create the header entry */
        LinkedEntry() {
            super(null, null, 0, null);
            nxt = prv = this;
        }
    
        /** Create a normal entry */
        LinkedEntry(K key, V value, int hash, HashMapEntry<K, V> next,
                    LinkedEntry<K, V> nxt, LinkedEntry<K, V> prv) {
            super(key, value, hash, next);
            this.nxt = nxt;
            this.prv = prv;
        }
    }

在HashMap键值对的实体上增加了nxt prv指针。除此之外在构造函数中调用了super();方法，该方法在HashMap中用于将映射实体加入到数组中。

返回最早加入的实体

public Entry<K, V> eldest() {
        LinkedEntry<K, V> eldest = header.nxt;
        return eldest != header ? eldest : null;
    }

如果Map为空，那么返回NULL

添加新的映射实体

@Override void addNewEntry(K key, V value, int hash, int index) {
        LinkedEntry<K, V> header = this.header;
    
        // Remove eldest entry if instructed to do so.
        LinkedEntry<K, V> eldest = header.nxt;
        if (eldest != header && removeEldestEntry(eldest)) {
            remove(eldest.key);
        }
    
        // Create new entry, link it on to list, and put it into table
        LinkedEntry<K, V> oldTail = header.prv;
        LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
                key, value, hash, table[index], header, oldTail);
        table[index] = oldTail.nxt = header.prv = newTail;
    }

这个方法在LruCache中会用到，每当添加一个新的实体的时候就删除最久的那个，是否删除通过`removeEldestEntry(eldest)`来判断，该方法返回true 或者false。方法的后半部分是一个双向链表的增加节点操作，头节点的nxt指向第一个节点，prv指向最后一个节点。添加新节点的时候主要是修改prv和prv所指向的节点的指针。

添加NULL key的映射实体

@Override void addNewEntryForNullKey(V value) {
        LinkedEntry<K, V> header = this.header;
    
        // Remove eldest entry if instructed to do so.
        LinkedEntry<K, V> eldest = header.nxt;
        if (eldest != header && removeEldestEntry(eldest)) {
            remove(eldest.key);
        }
    
        // Create new entry, link it on to list, and put it into table
        LinkedEntry<K, V> oldTail = header.prv;
        LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
                null, value, 0, null, header, oldTail);
        entryForNullKey = oldTail.nxt = header.prv = newTail;
    }

前半部分和上面的添加操作一样，后面就是倒数第二句不同，没有设置key和hash，以及table\[\]

只添加不移除

@Override HashMapEntry<K, V> constructorNewEntry(
            K key, V value, int hash, HashMapEntry<K, V> next) {
        LinkedEntry<K, V> header = this.header;
        LinkedEntry<K, V> oldTail = header.prv;
        LinkedEntry<K, V> newTail
                = new LinkedEntry<K,V>(key, value, hash, next, header, oldTail);
        return oldTail.nxt = header.prv = newTail;
    }

功能和上面的两个方法差不多，只没有判断是够进行移除操作

根据给定的key返回指定值

@Override public V get(Object key) {
        /*
         * This method is overridden to eliminate the need for a polymorphic
         * invocation in superclass at the expense of code duplication.
         */
        if (key == null) {
            HashMapEntry<K, V> e = entryForNullKey;
            if (e == null)
                return null;
            if (accessOrder)
                makeTail((LinkedEntry<K, V>) e);
            return e.value;
        }
    
        int hash = Collections.secondaryHash(key);
        HashMapEntry<K, V>[] tab = table;
        for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
                e != null; e = e.next) {
            K eKey = e.key;
            if (eKey == key || (e.hash == hash && key.equals(eKey))) {
                if (accessOrder)
                    makeTail((LinkedEntry<K, V>) e);
                return e.value;
            }
        }
        return null;
    }
    
    private void makeTail(LinkedEntry<K, V> e) {
        // Unlink e
        e.prv.nxt = e.nxt;
        e.nxt.prv = e.prv;
    
        // Relink e as tail
        LinkedEntry<K, V> header = this.header;
        LinkedEntry<K, V> oldTail = header.prv;
        e.nxt = header;
        e.prv = oldTail;
        oldTail.nxt = header.prv = e;
        modCount++;
    }

这部分代码和父类HashMap有些重复，但是优点是减少了由于多态导致的父类方法调用。代码中的`entryForNullKey`是父类HahMap中的成员变量，如果没有NULL key的映射，那么entryForNullKey也是NULL。

代码中使用的makeTail()的作用是将给定的映射实体从双向链表中取出，然后添加到链表尾部，在访问操作或者删除操作过程中，如果`accessOrder`为true，也就是需要按访问顺序进行排序的时候，都要调用MakeTail方法，将指定节点移动到尾部。

get()方法的后半部分看起来可能有一些奇怪，不是说LinkedHashMap是基于双向循环链表吗，为什么还有数组的迭代操作？？实际上LinkedHashMap是数组和双向链表的结合，HashMap基于数组，LinkedHashMap是其子类，在HashMap的基础上增加了两个指针，除了将映射实体加入到数组中之外，还额外维护了两个指针。这样理解的话，get()方法的后半部分就比较好理解了，直接是按key的Hash值对数组进行遍历，如果找到对应的映射，则返回值，否则返回Null

删除指定节点

@Override void postRemove(HashMapEntry<K, V> e) {
        LinkedEntry<K, V> le = (LinkedEntry<K, V>) e;
        le.prv.nxt = le.nxt;
        le.nxt.prv = le.prv;
        le.nxt = le.prv = null; // Help the GC (for performance)
    }

判断是否包含

@Override public boolean containsValue(Object value) {
        if (value == null) {
            for (LinkedEntry<K, V> header = this.header, e = header.nxt;
                    e != header; e = e.nxt) {
                if (e.value == null) {
                    return true;
                }
            }
            return false;
        }
    
        // value is non-null
        for (LinkedEntry<K, V> header = this.header, e = header.nxt;
                e != header; e = e.nxt) {
            if (value.equals(e.value)) {
                return true;
            }
        }
        return false;
    }

由于LinkedHashMap继承于HashMap，支持null key 和null value，所以需要判断key是否为空。在父类HashMap中已经有了containsValue()方法了，这里的重载是基于链表的查找，这样可以减少迭代的开销。

清空集合

public void clear() {
        super.clear();
    
        // Clear all links to help GC
        LinkedEntry<K, V> header = this.header;
        for (LinkedEntry<K, V> e = header.nxt; e != header; ) {
            LinkedEntry<K, V> nxt = e.nxt;
            e.nxt = e.prv = null;
            e = nxt;
        }
    
        header.nxt = header.prv = header;
    }

清空操作不仅仅是清空链表间的指针链，还需要调用父类的clear()清空映射实体