LinkedHashMap源码阅读

爱被打了一巴掌 2022-12-20 13:58 96阅读 0赞

### 文章目录 ###

*   *  回顾一下使用
     *  LinkedHashMap结构
     *  继承结构
     *  存放的key-value的Node节点
     *  核心属性
     *  构造方法
     *  核心方法 public V get(Object key)
     *  核心方法 public V put(K key, V value)
     *  总结

[建议看之前先看HashMap][HashMap]

## 回顾一下使用 ##

LinkedHashMap是有序的HashMap。节点的存放或者访问维持着其中的顺序。**支持两种顺序**

1.  插入顺序  
    按照插入的前后顺序，先插入的在双向链表前，后插入的在双向链表后。修改已存在的节点不会改变顺序
2.  访问顺序  
    在插入顺序的基础上，增加了访问顺序。不存在访问的情况，依然按照插入顺序排序，节点被访问后，最新访问的节点会被放在双向链表的尾部。如果这个时候再插入个元素的话，插入的元素放在双向链表尾部，即在插入顺序的基础上。

Map<String, Integer> map = new LinkedHashMap<>();
    map.put("c",100);
    map.put("d",200);
    map.put("a",300);
    for(Entry<String,Integer> entry:map.entrySet()){ 
    	System.out.println(entry.getKey()+" "+entry.getValue());
    }

控制台按插入顺序输出

> c 100  
> d 200  
> a 300

Map<String, Integer> accessMap = new LinkedHashMap<>(16,0.75f,true);
    accessMap.put("c",100);
    accessMap.put("d",200);
    accessMap.put("a",300);
    for(Map.Entry<String,Integer> entry:accessMap.entrySet()){ 
        System.out.println(entry.getKey()+" "+entry.getValue());
    }
    accessMap.get("c");
    for(Map.Entry<String,Integer> entry:accessMap.entrySet()){ 
        System.out.println(entry.getKey()+" "+entry.getValue());
    }

控制台输出

> c 100  
> d 200  
> a 300

访问了c之后

> d 200  
> a 300  
> c 100

## LinkedHashMap结构 ##

数组+链表+红黑树+双向链表。可以可看到他的结构和HashMap几乎一样，只是多了更多的指针。  
（下图几个小问题修正一下，两个单链表和树的根节点是在数组中存放的。两个节点的链表两个节点中间少了两个箭头）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center]  
对比一下HashMap的结构，几乎一样，看源码就明白为什么了。  
![在这里插入图片描述][20201024225357324.png_pic_center]

## 继承结构 ##

LinkedHashMap继承了HashMap，是对HashMap做了增强。具体哪里做了增加后续分析  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 1]

## 存放的key-value的Node节点 ##

相对HashMap在节点上Entry继承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);
            }
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 2]

## 核心属性 ##

*  LinkedHashMap.Entry<K,V> head;  
    双向链表的头指针
 *  LinkedHashMap.Entry<K,V> tail;  
    双向链表的尾指针
 *  boolean accessOrder;  
    是否按照访问顺序排序，默认为false

## 构造方法 ##

基本上过一眼就行了，前面两个accessOrde都赋值为false。只有第三个是可以按照访问顺序存放的，accessOrder参数传true即可。

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

## 核心方法 public V get(Object key) ##

似乎也没什么好说的，调HashMap的getNode方法获取元素跟HashMap一样。但是前文说了LinkedHashMap可以按照访问顺序存放的，节点被访问后，最新访问的节点会被放在双向链表的尾部。往下看当accessOrder为true时（构造LinkedHashMap时构造函数参数传true）便会调用afterNodeAccess方法。

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

将节点移向双向链表的末尾

*  节点是头结点  
    头指针指向节点的后继，节点的前驱指向尾节点，尾节点的后继指向节点。节点的后继为Null。尾指针指向节点
 *  节点是尾节点  
    不用做处理。
 *  节点是中间节点  
    首先移除节点：节点前驱的后继指向节点的后继，节点的后继的前驱指向节点的前驱。  
    在尾节点后增加节点：节点的前驱指向尾节点，尾节点的后继指向节点。节点的后继为Null。尾指针指向节点。

//accessOrder属性为true时，新访问的节点需要放在双向链表的尾部
    void afterNodeAccess(Node<K,V> e) {  
            //临时记录尾节点
            LinkedHashMap.Entry<K,V> last = tail;
    		//如果已经是尾节点，则不需要移动
            if (accessOrder && last != e) { 
    		    //hashMap传递的引用是个Node，对象是Entry
                LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e;
                //前驱
    			LinkedHashMap.Entry<K,V> b = p.before;
    			//后继
    			LinkedHashMap.Entry<K,V> a = p.after;
    			
    			//节点的后继先设置为null，节点必定为尾节点，后继为Null
                p.after = null;
    			//节点为头结点
                if (b == null)
    			    //头指针移动到节点的后继
                    head = a;
                else
    			    //节点不为头节点,要么中间要么尾节点
    			    //前驱的后继指向节点后继
                    b.after = a;
    			
    			//后继不为null，不为尾节点（其实我不是很懂为什么要有这个判断）
    			//最外层if已经判断了节点不为尾节点了，a恒不为Null
                if (a != null)
    			    //后继的前驱指向节点的前驱
                    a.before = b;
                else
                    last = b;
                if (last == null)
                    head = p;
                else { 
                    //节点的前驱指向尾节点
                    p.before = last;
                    //尾节点的后继指向节点，让节点成为尾节点
                    last.after = p;
                }
    			//让尾指针指向尾节点
                tail = p;
                ++modCount;
            }
        }

## 核心方法 public V put(K key, V value) ##

put方法，LinkedHashMap没有重写put方法，而是重写了newNode方法来维护节点的先后顺序。  
先看看HashMap的put方法，其中在构造节点时，调用了newNode方法构造节点。看看LinkedHashMap重写的newNode  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 3]

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;
        }
    TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) { 
            TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
            linkNodeLast(p);
            return p;
        }
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { 
            LinkedHashMap.Entry<K,V> last = tail;
    		//尾指针移动向新节点
            tail = p;
    		//尾节点为null，那么这是第一个节点，头节点指针也指向该节点
            if (last == null)
                head = p;
            else { 
    		    //新节点的前驱指向尾节点
                p.before = last;
    			//尾节点后继指向新节点
                last.after = p;
            }
        }

remove时，linkedHashMap重写了void afterNodeRemoval(Node<K,V> p) \{ \}方法  
把节点从双向链表中删除。  
在HashMap中当节点删除后，调用了afterNodeRemoval方法，HashMap中是个空方法，LinkedHashMap重写了该方法。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 4]  
完成节点的移除工作。

*  头节点
 *  尾节点
 *  中间节点

void afterNodeRemoval(Node<K,V> e) {  // unlink
            LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e;
            LinkedHashMap.Entry<K,V> b = p.before;
            LinkedHashMap.Entry<K,V> a = p.after;
            //前驱后继置为null
            p.before = p.after = null;
            //节点E为头节点
            if (b == null)
                //头指针指向后继
                head = a;
            else
                //不为头节点
                //前驱的后继指向后继
                b.after = a;
            //E为尾节点
            if (a == null)
                //尾指针前移
                tail = b;
            else
                //后继前驱等于前驱
                a.before = b;
        }

## 总结 ##

linkedHashMap继承HashMap，在HashMap的基础上做了增加，增加了双向链表的结构用来维护各个节点之间的顺序，其中可以按照插入顺序或者访问顺序。

1.  插入顺序  
    按照插入的前后顺序，先插入的在双向链表前，后插入的在双向链表后。修改已存在的节点不会改变顺序
2.  访问顺序  
    不存在访问的情况，依然按照插入顺序排序，节点被访问后，最新访问的节点会被放在双向链表的尾部。

在插入元素时，调用newNode或者newTreeNode构造节点时会调整双向链表之间节点的顺序。如果只是改变某个节点的value则不会。因为并没有构造节点的过程。  
如果开启访问顺序，在调用get方法时会调整节点间的顺序。

[HashMap]: https://blog.csdn.net/wsdfym/article/details/109232470
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/e41a5b402fec4b4ba429a225f1372830.png
[20201024225357324.png_pic_center]: /images/20221120/e1756ba3918f453d82cd895655de3824.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/bbe608af71474784b7888064762710f4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/8ae48a895c3748029c3d11a6b68abc07.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/6bb00c7acd2e4036a529640d61614e31.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/4df7c25b44e7456197ee971f835c775d.png