JDK1.8 LinkedHashMap源码

电玩女神 2022-02-23 22:16 411阅读 0赞

LinkedHashMap，根据插入值的顺序读取  
key和value都可以为null，和hashmap相同

## 使用 ##

Map<String, String> linkedMap = new LinkedHashMap<String, String>();
            linkedMap.put("a", "1");
            linkedMap.put("d", "4");
            linkedMap.put("b", "2");
            linkedMap.put("c", "3");
            linkedMap.put("a", "10");
            linkedMap.remove("b");
            linkedMap.put("e", null);
            linkedMap.put(null, "f");
            System.out.println("LinkedHashMap:" + linkedMap);//LinkedHashMap:{a=10, d=4, c=3, e=null, null=f}

## 原理 ##

LinkedHashMap，继承了HashMap。

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

HashMap为了避免碰撞，因此用拉链法解决冲突，HashMap中的连接只是同一个桶中的元素连接，而LinkedHashMap是将所有桶中的节点串联成一个双向链表。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21pbmd3dWxpcG8_size_16_color_FFFFFF_t_70]  
它继承了HashMap的Node，Node基础上添加了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);
            }
        }

LinkedHashMap使用的是LRU算法(Least Recently Used，最近最少使用) ，当你插入元素时它会将节点插入双向链表的链尾，如果key重复，则也会将节点移动至链尾，当用get()方法获取value时也会将节点移动至链尾。

构造方法，默认同hashmap一样，创建容量16，加载因子是0.75的数组，默认是插入顺序

//accessOrder默认为false，即按照插入顺序来连接，true则为按照访问顺序来连接
       public LinkedHashMap() {
            super();
            accessOrder = false;
        }

## 写入 ##

LinkedHashMap使用HashMap的put方法，即使用hashmap的putVal（）方法

if ((p = tab[i = (n - 1) & hash]) == null)
                 //调用newNode()方法
                tab[i] = newNode(hash, key, value, null);
            else {

其创建节点的方法是newNode()方法，而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;
        }
        private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
            LinkedHashMap.Entry<K,V> last = tail;
            tail = p;
            // 如果链尾为空，则双向链表为空，则p即为头结点也为尾节点
            if (last == null)
                head = p;
            else {
                //否则的话修改指针，让之前链尾的after指针指向p，p的before指向之前链尾
                p.before = last;
                last.after = p;
            }
        }

插入新值时将其插入双向链表链尾，根据插入值得顺序，构成一个顺序链表

那么接下来put()更新值则节点移动至链尾怎么实现的呢?

if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                      //在节点被访问后移动链尾
                    afterNodeAccess(e);
                    return oldValue;
                }
            }

如果是默认的插入顺序，此方法无效。如果是访问顺序，

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;
                //如果前面没有元素，则p之前为头结点，直接让a成为头结点
                if (b == null)
                    head = a;
                else
                    // 否则b的尾指针指向a
                    b.after = a;
                if (a != null)
                    //如果a不为空，则a的头指针指向b
                    a.before = b;
                else
                //否则 p之前就为尾指针，则另b成为尾指针
                    last = b;
                if (last == null)
                    //如果双向链表中只有p一个节点，则令p即为头结点，也为尾节点
                    head = p;
                else {
                //否则 将p插入链尾
                    p.before = last;
                    last.after = p;
                }
                tail = p;
                ++modCount;
            }
        }

此外HashMap的putVal()方法，还调用了afterNodeInsertion()方法，

++modCount;
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;

LinkedHashMap重写了afterNodeInsertion方法，不过removeEldestEntry()默认是返回false的，需要子类继承重写removeEldestEntry()方法。

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

## 删除 ##

调用的HashMap的remove()方法

public V remove(Object key) {
            Node<K,V> e;
            return (e = removeNode(hash(key), key, null, false, true)) == null ?
                null : e.value;
        }

removeNode方法中

//回调从双向链表中移除node
                    afterNodeRemoval(node);
                    return node;
                }
            }
            return null;
        }

LinkedHashMap重写了afterNodeRemoval方法

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

## 读取 ##

LinkedHashMap重写了get()方法，实现了LRU

public V get(Object key) {
            Node<K,V> e;
            if ((e = getNode(hash(key), key)) == null)
                return null;
                // accessOder为true时，被访问的节点被置于双向链表尾部
            if (accessOrder)
                afterNodeAccess(e);
            return e.value;
        }

## 遍历 ##

LinkedHashIterator() {
                next = head;
                expectedModCount = modCount;
                current = null;
            }
    
            public final boolean hasNext() {
                return next != 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;
            }

从头结点开始，向后开始遍历

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21pbmd3dWxpcG8_size_16_color_FFFFFF_t_70]: /images/20220224/3431b17627204168a2b9e9f0223d6de0.png