学习JDK1.8集合源码之--LinkedHashMap

迷南。 2021-12-15 14:09 311阅读 0赞

## 1. LinkedHashMap简介 ##

LinkedHashMap继承自HashMap，实现了Map接口。

LinkedHashMap是HashMap的一种有序实现（多态，HashMap的有序态），可以说是HashMap的一种拓展，弥补了HashMap无序这一缺点，但它实现有序的代价是牺牲了时间和空间上的开销。

LinkedHashMap的有序是通过维护一条双向链表保证了元素的有序性，除了有序这一点之外，LinkedHashMap和HashMap差不多，也就没有太多需要描述的了。

## 2. LinkedHashMap实现 ##

### 1. 核心参数 ###

//内部Entry实体，继承自HashMap.Node
        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;
        
        //排序方式，true：访问顺序，false：插入顺序
        final boolean accessOrder;

从上面可以看出，LinkedHashMap核心属性都是继承自HashMap，只是在HashMap的基础上增加了前后节点来维护一个双向链表，head和tail为链表的头尾节点，而且它的排序方式有两种：访问顺序和插入顺序。

### 2. 构造函数 ###

//无参构造，构造一个初始容量16、加载因子0.75的LinkedHashMap，默认按照插入顺序排序
        public LinkedHashMap() {
            super();
            accessOrder = false;
        }
        
        //构造一个指定初始容量、加载因子0.75的LinkedHashMap，默认按照插入顺序排序
        public LinkedHashMap(int initialCapacity) {
            super(initialCapacity);
            accessOrder = false;
        }
        
        //构造一个指定初始容量、指定加载因子的LinkedHashMap，默认按照插入顺序排序
        public LinkedHashMap(int initialCapacity, float loadFactor) {
            super(initialCapacity, loadFactor);
            accessOrder = false;
        }
        
        //构造一个指定初始容量、指定加载因子的LinkedHashMap，指定顺序方式
        public LinkedHashMap(int initialCapacity,
                             float loadFactor,
                             boolean accessOrder) {
            super(initialCapacity, loadFactor);
            this.accessOrder = accessOrder;
        }
        
        //构建一个能够容纳传入map中元素的最小2次幂的初始容量（最小16）、加载因子0.75的LinkedHashMap，默认按照插入顺序排序
        public LinkedHashMap(Map<? extends K, ? extends V> m) {
            super();
            accessOrder = false;
            putMapEntries(m, false);
        }

LinkedHashMap的构造也是基于HashMap进行构造的，只是在构造时加了排序方式的设置。

### 3. 核心方法 ###

LinkedHashMap的实现基本上调用HashMap的API实现存储、获取、删除、扩容等操作，只是在这些操作的基础上增加了一些维护双向链表的逻辑，保证了有序性。如果是按照插入顺序的话，每次调用newNode的时候都会调用linkNodeLast来把新建的节点放到链表尾部，如果是按照访问顺序排序的话，则增加了修改和获取节点时调用afterNodeAccess将该节点放到链表尾部。

//将p节点放到链表尾部
        private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
            //取LinkedHashMap的尾节点赋值给last
            LinkedHashMap.Entry<K,V> last = tail;
            //将尾节点设为p
            tail = p;
            //如果不存在尾节点，说明链表是空的，把链表头部也设为p
            if (last == null)
                head = p;
            else {
                //否则则将p设为last的下一节点，last设为p的上一节点
                p.before = last;
                last.after = p;
            }
        }
        
        //将节点src替换为dst节点
        private void transferLinks(LinkedHashMap.Entry<K,V> src,
                                   LinkedHashMap.Entry<K,V> dst) {
            //将src的上一个节点设为dst的上一个节点并赋值给b
            LinkedHashMap.Entry<K,V> b = dst.before = src.before;
            //将src的下一个节点设为dst的下一个节点并赋值给a
            LinkedHashMap.Entry<K,V> a = dst.after = src.after;
            //如果b==null，说明src就是头节点，将dst设为头节点
            if (b == null)
                head = dst;
            //否则将b的下一节点设为dst
            else
                b.after = dst;
            //如果哦a==null，说明src就是尾节点，将dst设为尾节点
            if (a == null)
                tail = dst;
            //否则则将a的上一节点设为dst
            else
                a.before = dst;
        }
        
        /**下面的方法都是重写HashMap到的方法**/
        
        //重置LinkedHashMap
        void reinitialize() {
            super.reinitialize();
            head = tail = null;
        }
        
        //HashMap中的untreeify时调用，将树形节点替换成普通节点
        Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
            LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
            LinkedHashMap.Entry<K,V> t = new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
            transferLinks(q, t);
            return t;
        }
        
        //新建一个树形节点并追加到LinkedHashMap尾部，调用父类的TreeNode
        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;
        }
        
        //HashMap中的treeifyBin时调用，将普通节点替换成树形节点
        TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
            LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
            TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
            transferLinks(q, t);
            return t;
        }
        
        //HashMap中移除元素后调用，调整LinkedHashMap的链表结构
        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;
        }
    
        //HashMap中添加元素后调用，evict为false说明底层HashMap在初始化模式
        void afterNodeInsertion(boolean evict) { // possibly remove eldest
            LinkedHashMap.Entry<K,V> first;
            //removeEldestEntry方法直接返回false，没有具体实现，所以这个方法是用来给子类重写的
            if (evict && (first = head) != null && removeEldestEntry(first)) {
                K key = first.key;
                removeNode(hash(key), key, null, false, true);
            }
        }
    
        //访问一个元素后调用，包括put、replace、get等操作
        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;
                //如果该节点是头节点，则将下一节点设为头节点
                if (b == null)
                    head = a;
                //否则将上一节点的下一节点设为该节点的下一节点
                else
                    b.after = a;
                //如果下一节点不为空，则将上一节点设为下一节点的上一节点
                if (a != null)
                    a.before = b;
                //否则将上一节点设为尾节点
                else
                    last = b;
                //如果尾节点为空，则将该节点设置头节点
                if (last == null)
                    head = p;
                //否则将尾节点的下一节点设为该节点，尾节点设为该节点的上一节点
                else {
                    p.before = last;
                    last.after = p;
                }
                //将该节点设为尾节点
                tail = p;
                ++modCount;
            }
        }
    
        //判断LinkedHashMap中是否包含value
        public boolean containsValue(Object value) {
            //从链表头部开始依次遍历
            for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
                V v = e.value;
                if (v == value || (value != null && value.equals(v)))
                    return true;
            }
            return false;
        }
        
        //根据key获取value
        public V get(Object key) {
            Node<K,V> e;
            //通过HashMap的getNode方法获取节点
            if ((e = getNode(hash(key), key)) == null)
                return null;
            //如果是按照访问顺序排序，则将该元素放到链表尾部
            if (accessOrder)
                afterNodeAccess(e);
            return e.value;
        }
        
        //根据key获取value，与get不同的是key不存在时会返回指定的默认值
        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;
       }
       
       //清空LinkedHashMap
       public void clear() {
            //调用父类的清空方法
            super.clear();
            //将链表首尾节点都置空
            head = tail = null;
        }
        
        //返回key的有序set集合
        public Set<K> keySet() {
            Set<K> ks = keySet;
            if (ks == null) {
                ks = new LinkedKeySet();
                keySet = ks;
            }
            return ks;
        }
        
        //返回value的有序集合
        public Collection<V> values() {
            Collection<V> vs = values;
            if (vs == null) {
                vs = new LinkedValues();
                values = vs;
            }
            return vs;
        }
        
        //返回key-value实体的有序set集合
        public Set<Map.Entry<K,V>> entrySet() {
            Set<Map.Entry<K,V>> es;
            return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
        }

转载于:https://www.cnblogs.com/despacito/p/10899740.html