Java容器LinkedHashMap源代码解析

深藏阁楼爱情的钟 2022-06-15 05:59 167阅读 0赞

## **写在前面的话** ##

本文针对的是Java1.6进行的源码分析，与其他版本可能存在差异。

## **概述** ##

LinkedHashMap是继承自HashMap，所以HashMap的特性，它都有。与HashMap不同之处在于，它自身还维护了一个双向链表，这个链表是有序的，可以根据元素的插入顺序或者访问顺序排列。关于HashMap的解析请参考[ Java容器HashMap源代码解析][Java_HashMap]

## **源代码解析** ##

**1.LinkedHashMap属性**

/**
         * 双向链表头结点
         */
        private transient Entry<K,V> header;
    
        /**
         * 双向链表中元素的排列顺序
         */
        private final boolean accessOrder;

除了HashMap中的属性，LinkedHashMap新增了两个属性。header是双向链表的头结点，accessOrder是双向链表中元素的排列顺序，accessOrder为true时，链表中的元素按照访问顺序排列；accessOrder为false时，链表中的元素按照插入顺序排列。

**2.底层数据结构**

LinkedHashMap的Entry同样继承了HashMap的Entry类，代码如下：

private static class Entry<K,V> extends HashMap.Entry<K,V> {
        
            //双向链表的前结点和后结点
            Entry<K,V> before, after;
    
            Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
                //调用HashMap的Entry构造方法
                super(hash, key, value, next);
            }
    
            //在双向链表中删除该结点
            private void remove() {
                //当前结点的前结点的after引用指向当前结点的后结点
                before.after = after;
                //当前结点的后结点的before引用指向当前结点的前结点
                after.before = before;
            }
    
            //把当前结点加到existingEntry结点的前面
            private void addBefore(Entry<K,V> existingEntry) {
                after  = existingEntry;
                before = existingEntry.before;
                before.after = this;
                after.before = this;
            }
    
            //put和get的时候会调用此方法
            void recordAccess(HashMap<K,V> m) {
                LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
                //如果是按照插入顺序排列，不做任何操作
                //如果是按照元素访问顺序排列，则把当前结点删除，并添加到链表末尾位置
                if (lm.accessOrder) {
                    lm.modCount++;
                    remove();
                    addBefore(lm.header);
                }
            }
    
            //删除元素的时候会调用此方法，在双向链表中也删除掉
            void recordRemoval(HashMap<K,V> m) {
                remove();
            }
        }

相比HashMap的Entry类，LinkedHashMap的Entry类多了before和after两个属性，它们分别指向当前结点的前结点和后结点。remove是删除当前结点，addBefore是把当前结点添加到给定结点的前面，都是对链表的基本操作，不再详述。recordAccess和recordRemoval两个方法，在HashMap中也介绍过，它们在HashMap中没有实现任何操作，在LinkedHashMap中对这两个方法重写。recordAccess在添加元素和查找元素时会调用，如果是按照插入顺序排列，则不做任何操作；如果是按照元素的访问顺序排列，则在链表中删除当前结点，并把该结点添加到链表末尾位置。recordRemoval在删除元素时会调用，在链表中删除当前结点。

**3.构造方法**

LinkedHashMap提供了5个构造方法：

//给定容量和加载因子的构造方法
        public LinkedHashMap(int initialCapacity, float loadFactor) {
            //调用HashMap的构造方法
            super(initialCapacity, loadFactor);
            //默认按照元素的插入顺序排列
            accessOrder = false;
        }
    
        //给定容量的构造方法，加载因子用默认值
        public LinkedHashMap(int initialCapacity) {
            //调用HashMap的构造方法
            super(initialCapacity);
            //默认按照元素的插入顺序排列
            accessOrder = false;
        }
    
        //默认构造方法，容量和加载因子都用默认值
        public LinkedHashMap() {
            //调用HashMap的构造方法
            super();
            //默认按照元素的插入顺序排列
            accessOrder = false;
        }
    
        //带有map参数的构造函数
        public LinkedHashMap(Map<? extends K, ? extends V> m) {
            //调用HashMap的构造方法
            super(m);
            //默认按照元素的插入顺序排列
            accessOrder = false;
        }
    
        //给定容量、加载因子和accessOrder的构造函数
        public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
            //调用HashMap的构造方法
            super(initialCapacity, loadFactor);
            //根据传进来的accessOrder值确定元素的排列顺序
            this.accessOrder = accessOrder;
        }

前四个构造函数与HashMap的构造函数相对应，分别调用相应的构造函数实现，accessOrder 都默认为false，即默认按照元素的插入顺序排列。最后一个构造函数，可以设置accessOrder 值，指定元素的排列顺序。

**4.其它方法**

init()方法：HashMap的构造函数会调用，在HashMap中没有任何操作，在LinkedHashMap中重写该方法。用来初始化双向链表：

void init() {
            //初始化头结点
            header = new Entry<K,V>(-1, null, null, null);
            header.before = header.after = header;
        }

transfer()方法：在HashMap中介绍过该方法，用于在扩容时，把原先的数据全都存放到新的数组中。在LinkedHashMap中重写该方法，主要是为了优化性能，在HashMap实现该方法时，需要遍历整个table数组，而LinkedHashMap维护了双向链表，可以直接遍历链表。

void transfer(HashMap.Entry[] newTable) {
            int newCapacity = newTable.length;
            //遍历双向链表
            for (Entry<K,V> e = header.after; e != header; e = e.after) {
                //计算出在新table中的索引值
                int index = indexFor(e.hash, newCapacity);
                e.next = newTable[index];
                //存入到新table中
                newTable[index] = e;
            }
        }

containsValue()方法：重写该方法的目的与重写transfer()方法一样，都是通过遍历双向链表来代替遍历table，以优化性能。

public boolean containsValue(Object value) {
            //遍历双向链表，优化性能
            if (value==null) {
                for (Entry e = header.after; e != header; e = e.after)
                    if (e.value==null)
                        return true;
            } else {
                for (Entry e = header.after; e != header; e = e.after)
                    if (value.equals(e.value))
                        return true;
            }
            return false;
        }

get()方法：重写该方法，主要是多了对recordAccess方法的调用。

public V get(Object key) {
            //调用HashMap的getEntry方法
            Entry<K,V> e = (Entry<K,V>)getEntry(key);
            if (e == null)
                return null;
            //调用recordAccess方法
            e.recordAccess(this);
            return e.value;
        }

clear()方法：重写该方法，调用HashMap的clear()方法，并把头结点的前后引用指向本身

public void clear() {
            super.clear();
            header.before = header.after = header;
        }

addEntry()和createEntry()方法：creatEntry重写后，会在每次增加元素时，把Entry结点加入到双向链表的尾部。addEntry重写后，可以根据需要，在增加结点时，删除最不常访问或最早插入的结点，默认是不会删除，可以通过重写removeEldestEntry方法修改默认值。

//重写addEntry方法
        void addEntry(int hash, K key, V value, int bucketIndex) {
            createEntry(hash, key, value, bucketIndex);
            //eldest即为最不常访问或最早插入的结点
            Entry<K,V> eldest = header.after;
            //如果需要删除最不常访问或最早插入的结点，则调用HashMap的removeEntryForKey()方法
            //否则判断是否需要扩容，如果需要，进行扩容操作
            if (removeEldestEntry(eldest)) {
                removeEntryForKey(eldest.key);
            } else {
                if (size >= threshold)
                    resize(2 * table.length);
            }
        }
    
        //重写createEntry()方法
        void createEntry(int hash, K key, V value, int bucketIndex) {
            HashMap.Entry<K,V> old = table[bucketIndex];
            Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
            table[bucketIndex] = e;
            //将新增结点加入到双向链表的尾部
            e.addBefore(header);
            size++;
        }
    
        //判断是否要删除最不常访问或最早插入的结点，默认不删除
        protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
            return false;
        }

**5.迭代器**

前面已经说到LinkedHashMap的遍历是有序的，那么它的迭代器是如何保证遍历有序呢？其实很简单，HashMap的迭代器是遍历table，而LinkedHashMap只需遍历双向链表即可，因此保证了数据是有序的。

private abstract class LinkedHashIterator<T> implements Iterator<T> {
        
            //下一个结点
            Entry<K,V> nextEntry    = header.after;
            //最近返回的结点
            Entry<K,V> lastReturned = null;
            int expectedModCount = modCount;
    
            //实现了接口的hasNext方法，只要nextEntry 不等于header，证明链表没有遍历完
            public boolean hasNext() {
                return nextEntry != header;
            }
    
            //实现了接口的remove方法
            public void remove() {
                if (lastReturned == null)
                    throw new IllegalStateException();
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                LinkedHashMap.this.remove(lastReturned.key);
                lastReturned = null;
                expectedModCount = modCount;
            }
    
            Entry<K,V> nextEntry() {
                if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
                if (nextEntry == header)
                    throw new NoSuchElementException();
    
                Entry<K,V> e = lastReturned = nextEntry;
                nextEntry = e.after;
                return e;
            }
        }
    
        //key迭代器
        private class KeyIterator extends LinkedHashIterator<K> {
        
            public K next() { return nextEntry().getKey(); }
        }
    
        //value迭代器
        private class ValueIterator extends LinkedHashIterator<V> {
        
            public V next() { return nextEntry().value; }
        }
    
        //Entry迭代器
        private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
        
            public Map.Entry<K,V> next() { return nextEntry(); }
        }
    
        //分别重写了HashMap中的方法，返回对应的迭代器
        Iterator<K> newKeyIterator()   { return new KeyIterator();   }
        Iterator<V> newValueIterator() { return new ValueIterator(); }
        Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }

[Java_HashMap]: http://blog.csdn.net/Kevin_zhai/article/details/72652516