Java从入门到放弃（十五）集合框架之LinkedHashMap源码

阳光穿透心脏的1/2处 2022-05-24 04:42 160阅读 0赞

LinkedHashMap是一个有序的HashMap，各个节点以双向链表的形式链接着，结构如图所示：![LinkedHashMap结构图][LinkedHashMap]  
LinkedHashMap的真实结构不会死这样子的，因为长度原因截图部分。节点里的数字标识实际上是没有的，是为了表示插入的顺序（如果是jdk1.7图会有不同，因为1.8之前hashmap是头插入，1.8之后是尾插入）。每一个节点就是一个内部类Entry对象，这个结构图和HashMap的结构图基本上是一样的，LindedHashMap和HashMap的区别是：LinkedHashMap还需要维护插入的顺序，节点之间的绿色的线是after指向，红色的线是before指向。

## 属性 ##

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);
            }
        }
        transient LinkedHashMap.Entry<K,V> head;   //链表头结点
        transient LinkedHashMap.Entry<K,V> tail;   //链表尾节点
        final boolean accessOrder;    //实现LRU

LinkedHashMap继承了HashMap，本质上来说，它还是一个HashMap,只是多维护了几个属性而已。主要通过Entry不同来实现。如上，Entry继承了HashMap.Entry，多了before和after属性，然后比起HashMap还多了head和tail两个属性，指向链表的头尾节点。

## 构造方法 ##

public LinkedHashMap(int initialCapacity, float loadFactor) {
            super(initialCapacity, loadFactor);  //容量，负载因子
            accessOrder = false;
        }
        public LinkedHashMap(int initialCapacity) {
            super(initialCapacity);
            accessOrder = false;
        }
        public LinkedHashMap() {
            super();
            accessOrder = false;
        }
        public LinkedHashMap(Map<? extends K, ? extends V> m) {
            super();
            accessOrder = false;
            putMapEntries(m, false);
        }
        public LinkedHashMap(int initialCapacity,
                             float loadFactor,
                             boolean accessOrder) {
            super(initialCapacity, loadFactor);
            this.accessOrder = accessOrder;
        }

这里构造方法都是调用了父类的构造方法，然后accessOrder默认是false，accessOrder设置为true时，链表会实现LRU，把最近访问的节点放到链表的末尾。对于HashMap的方法这里不再讲述，具体参考[ Java从入门到放弃（十）集合框架之HashMap源码(1)][Java_HashMap_1]。

## put方法 ##

这里并没有重写put方法调用的还是HashMapd的put方法。如下：

public V put(K key, V value) {  
               return putVal(hash(key), key, value, false, true);  
          }  
    //hash就是key的hash值，根据这个hash得出数据存放再数组中的位置，onlyIfAbsent为true时，不存在key才会执行put操作。 
          final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {  
               Node<K,V>[] tab; Node<K,V> p; int n, i;  
               if ((tab = table) == null || (n = tab.length) == 0)   // 初始化是一个空的Node数组 
                   n = (tab = resize()).length;   // 扩容方法，初始化扩容默认容量为16 
               if ((p = tab[i = (n - 1) & hash]) == null)  //如果数组索引处为null 
                   tab[i] = newNode(hash, key, value, null);    //就把key-value构造一个Node数组插入数组中 
               else {  
                   Node<K,V> e; K k;  
                   if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))  //如果hash和key都相等 
                       e = p;  
                   else if (p instanceof TreeNode)   //如果是红黑树结构 
                       e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);  
                   else {  
                       for (int binCount = 0; ; ++binCount) {  
                           if ((e = p.next) == null) {  
                               p.next = newNode(hash, key, value, null);   // 把新的Node节点插入链表的尾部(尾插法，1.8之前是头插入) 
                               if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //如果链表长度大于等于8，转换为红黑树 
                                   treeifyBin(tab, hash);  
                               break;  
                           }  
                           if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))  //已经插入完成，直接退出循环 
                               break;  
                           p = e;  
                       }  
                   }  
                   if (e != null) { // existing mapping for key，如果存在对应的key值，直接进行更新操作 
                       V oldValue = e.value;  
                       if (!onlyIfAbsent || oldValue == null)    // onlyIfAbsent为false,就更新 
                           e.value = value;  
                       afterNodeAccess(e);  
                       return oldValue;  //返回旧值 
                   }  
               }  
               ++modCount;         //修改记录值 
               if (++size > threshold)   //size大于负载因子要求的容量值就进行扩容 
                   resize();  
               afterNodeInsertion(evict);  
               return null;  
       }

不同的地方在于LinkedHashMap重写了**newNode方法**：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
            LinkedHashMap.Entry<K,V> p =
                new LinkedHashMap.Entry<>(hash, key, value, e);   //创建节点对象
            linkNodeLast(p);
            return p;
        }
    
        private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
            LinkedHashMap.Entry<K,V> last = tail;    //尾节点
            tail = p;    //把新节点设为尾节点
            if (last == null)    //如果尾节点为null，说明集合是空的，把head也指向新的节点
                head = p;
            else {             //如果集合不为空
                p.before = last;    //把p的before指向之前的尾节点
                last.after = p;     //把之前的尾节点的after指向p
            }
        }

和LinkedList的操作是一样的，就是重新设置tail以及节点的before和after指向。具体可查看[Java从入门到放弃（八）集合框架之LinkedList源码(1)][Java_LinkedList_1]。  
这里有两个方法**afterNodeAccess**和**afterNodeInsertion**方法，在HashMap里面这是两个空的方法，LinkedHashMap里面的具体实现如下：

//方法是把e对应的节点移到链表的末尾
        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;    //e转换为Entry对象
                p.after = null;     //设置p的after为null,
                if (b == null)
                    head = a;     //如果是p为 first节点，把p的after设为首节点 
                else
                    b.after = a;          //把p的befor节点的after指向p的after指向的节点
                if (a != null)
                    a.before = b;       //p不是尾节点，就把p的after节点的before指向p的before指向的节点
                else
                    last = b;             //如果是尾节点，就把last指向p的before指向的节点
                if (last == null)
                    head = p;         //如果last为null,即 集合为空，把head指向p
                else {
                    p.before = last;         //p的before指向之前的tail节点
                    last.after = p;            //之前的tail的after指向p节点
                }
                tail = p;
                ++modCount;
            }
        }

就是为了维护链表，把新插入的数据放在链表的尾部。  
看一下**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;
        }

这里LinkedHashMap并没有实际操作，因为removeEldestEntry是一直返回false，我们可以自己继承重写这个方法，这样子可以把头节点删除，实现LRU，把集合内的数据维持在一个固定的数，经常作为缓存topN使用。就是把最少使用的数据删除。

## remove方法 ##

这里不贴remove的方法，就是HashMap的remove方法，可参考之前的文章，唯一的不同是**afterNodeRemoval**方法，在HashMap里是空方法，LinkeHashMap里重写了这个方法：

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;   把p的before，after引用都置为null,便于GC
            if (b == null)
                head = a;   
            else
                b.after = a;
            if (a == null)
                tail = b;
            else
                a.before = b;
        }

其实这个方法和前面的一些逻辑是一样的，就是把删除节点的前节点和后节点之间的引用进行更改。把删除节点的引用都置为null,便于GC；

## get方法 ##

public V get(Object key) {
            Node<K,V> e;
            if ((e = getNode(hash(key), key)) == null)
                return null;
            if (accessOrder)
                afterNodeAccess(e);
            return e.value;
        }
        public V getOrDefault(Object key, V defaultValue) {
           Node<K,V> e;
           if ((e = getNode(hash(key), key)) == null)
               return defaultValue;
           if (accessOrder)
               afterNodeAccess(e);
           return e.value;
       }

这两个方法唯一的区别是getOrDefault在找不到对应的key时，会返回第二个参数。这里还是调用了HashMap的get方法。只是在开启LRU的模式下会把对应的节点移到链表的末尾。

## 迭代遍历示例 ##

LinkedHashMap<String,Integer> linkedHashMap = new LinkedHashMap(8,0.75f,true);
            linkedHashMap.put("a",1);
            linkedHashMap.put("b",2);
            linkedHashMap.put("c",3);
            linkedHashMap.put("d",4);
            linkedHashMap.put("e",5);
            Set<String> str1 = linkedHashMap.keySet();
            System.out.println(str1);    //[a, b, c, d, e]
    
            linkedHashMap.get("b");
            linkedHashMap.get("c");
            Set<String> str2 = linkedHashMap.keySet();
            System.out.println(str2);    //[a, d, e, b, c]
    
            linkedHashMap.put("a",6);
            Set<String> str3 = linkedHashMap.keySet();
            System.out.println(str3);    //[d, e, b, c, a]

可以看到输出的key和插入的key顺序是一样的，在对某个key进行操作后，这个key会出现在链表的结尾。注意要实现LRU就要在构造函数设置LRU模式，不设置的话顺序就一直是插入的顺序。

[LinkedHashMap]: /images/20220524/e8b8deee4b994e789249a6f7f7dbf112.png
[Java_HashMap_1]: https://blog.csdn.net/qq_34101608/article/details/80138761
[Java_LinkedList_1]: https://blog.csdn.net/qq_34101608/article/details/79941473