LinkedHashMap源码分析

约定不等于承诺〃 2024-04-18 09:16 85阅读 0赞

### 1、特点 ###

LinkedHashMap有序的，内部维护了一个双向链表

### 2、LinkedHashMap是如何保证顺序的 ###

###    2.1 核心属性 ###

//是否根据操作顺序排序
    final boolean accessOrder;
    
    //链表头节点
    transient LinkedHashMap.Entry<K,V> head;
    
    //链表尾节点
    transient LinkedHashMap.Entry<K,V> tail;

## ##

//当accessOrder=true是，LinkedHashMap链表顺序不是根据插入的顺序排序，而是根据操作的顺序显示
    @Test
        public void test4(){
            LinkedHashMap<String,String> map = new LinkedHashMap(16,0.75f,true);
            map.put("1","1");
            map.put("2","2");
            map.put("3","3");
            map.get("1");
            map.put("4","4");
            map.put("3","33");
            for(String key : map.keySet()){
                System.out.println(key);
            }
        }
    
    显示结果为：2 1 4 3

###  2.2、put()方法 ###

/**
     * 1、LinkedHashMap继承了HashMap
     * 2、put()方法走HashMap的put方法
     * 
     * 改变：
     * 在putVal()方法中，linkedHashMap重写了newNode()方法
     */
    
    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;
            //如果尾节点为空
            if (last == null)
                //则p为头节点
                head = p;
            else {
                //如果尾结点不为空，p的头结点为原始的尾结点，原始的尾结点的下一节点为p
                //这样就形成了链表结构，就有了顺序
                p.before = last;
                last.after = p;
            }
        }

### 3、LinkedHashMap独特的功能 ###

linkedHashMap可以根据操作顺序排序

void afterNodeAccess(Node<K,V> e) {
            LinkedHashMap.Entry<K,V> last;
            //如果accessOrder=true,且当前节点不是尾结点
            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节点
                    last = b;
                //如果last(可以理解为倒数第二个节点)节点为空，说明链表中只有一个元素，设置头结点为p
                if (last == null)
                    head = p;
                else {
                    //更新当前节点的前节点为last，last的尾结点为p
                    p.before = last;
                    last.after = p;
                }
                //设置尾结点为p
                tail = p;
                //更新操作次数
                ++modCount;
            }
        }