LinkedHashMap源码解读与实现LRU缓存

待我称王封你为后i 2021-09-12 01:12 470阅读 0赞

LinkedHashMap继承HashMap  
自定义全局变量header表示头节点

private transient Entry<K,V> header;
    
        private final boolean accessOrder;

同时LinkedHashMap的自定义内部类Entry也继承了HashMap的Entry，但是新增了两个指针before和after。在哈希表的基础上又构成了双向链接列表。

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) {
                super(hash, key, value, next);
            }
    
            private void remove() {
                before.after = after;
                after.before = before;
            }
    
            private void addBefore(Entry<K,V> existingEntry) {
                after  = existingEntry;
                before = existingEntry.before;
                before.after = this;
                after.before = this;
            }
    
            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();
            }
        }

构造方法：

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

可以看到，默认调用了父类HashMap的构造方法，传入loadFactor，默认为 false，代表按照插入顺序进行迭代。可以显式设置为 true，代表以访问顺序进行迭代。

public HashMap(int initialCapacity, float loadFactor) {
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
    
            this.loadFactor = loadFactor;
            threshold = initialCapacity;
            init();
        }

可以看到最后一步构造调用了init()方法，在HashMap中方法为空。而在LinkedHashMap中重写了这个方法，进一步实现了对其元素Entry的初始化。

@Override
        void init() {
            header = new Entry<>(-1, null, null,   );
            header.before = header.after = header;
        }

在HashMap中，其Put方法如下。它的Entry.recordAccess是空方法。  
过程如下：先哈希定位到数组中哈希桶位置，然后遍历entry链表，如果hash相同并且key相同，覆盖原value，更新成新value。如果对应哈希桶中没有元素，调用addEntry()方法

public V put(K key, V value) {
            if (table == EMPTY_TABLE) {
                inflateTable(threshold);
            }
            if (key == null)
                return putForNullKey(value);
            int hash = hash(key);
            int i = indexFor(hash, table.length);
            for (Entry<K,V> e = table[i]; e != null; e = e.next) {
                Object k;
                if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                    V oldValue = e.value;
                    e.value = value;
                    e.recordAccess(this);
                    return oldValue;
                }
            }
    
            modCount++;
            addEntry(hash, key, value, i);
            return null;
        }

void addEntry(int hash, K key, V value, int bucketIndex) {
            if ((size >= threshold) && (null != table[bucketIndex])) {
                resize(2 * table.length);
                hash = (null != key) ? hash(key) : 0;
                bucketIndex = indexFor(hash, table.length);
            }
    
            createEntry(hash, key, value, bucketIndex);
        }
    
       void createEntry(int hash, K key, V value, int bucketIndex) {
            Entry<K,V> e = table[bucketIndex];
            table[bucketIndex] = new Entry<>(hash, key, value, e);
            size++;
        }

而LinkedHashMap没有重写Put方法，而是重写了父Entry.recordAccess()方法。还有addEntry(),createEntry()方法  
如果accessOrder为真，表示按照访问顺序迭代时，调用addBefore(lm.header)方法，表示将元素放到最后。（双向链表，头结点的before代表最后元素）  
注意：这里调用情况是，同一个哈希桶对应的entry链表的调整。

/**
             * This method is invoked by the superclass whenever the value
             * of a pre-existing entry is read by Map.get or modified by Map.set.
             * If the enclosing Map is access-ordered, it moves the entry
             * to the end of the list; otherwise, it does nothing.
             */
            void recordAccess(HashMap<K,V> m) {
                LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
                if (lm.accessOrder) {
                    lm.modCount++;
                    remove();
                    addBefore(lm.header);
                }
            }

重写Entry.addBefore方法，实现链表的链接

private void addBefore(Entry<K,V> existingEntry) {
                after  = existingEntry;
                before = existingEntry.before;
                before.after = this;
                after.before = this;
            }

重写的addEnty,createEntry方法。主要是重写createEntry方法，通过调用 e.addBefore(header)完成链表的链接。

/**
         * This override alters behavior of superclass put method. It causes newly
         * allocated entry to get inserted at the end of the linked list and
         * removes the eldest entry if appropriate.
         */
        void addEntry(int hash, K key, V value, int bucketIndex) {
            super.addEntry(hash, key, value, bucketIndex);
    
            // Remove eldest entry if instructed
            Entry<K,V> eldest = header.after;
            if (removeEldestEntry(eldest)) {
                removeEntryForKey(eldest.key);
            }
        }
    
        /**
         * This override differs from addEntry in that it doesn't resize the
         * table or remove the eldest entry.
         */
        void createEntry(int hash, K key, V value, int bucketIndex) {
            HashMap.Entry<K,V> old = table[bucketIndex];
            Entry<K,V> e = new Entry<>(hash, key, value, old);
            table[bucketIndex] = e;
            e.addBefore(header);
            size++;
        }

LinkedHashMap 重写了父类 HashMap 的 get 方法，在每一次get后调用了我们前面分析过的recordAccess方法，将元素放置到最后一个，这样就形成了一个**按访问顺序迭代**的哈希链表。由于的链表的增加、删除操作是常量级的，故并不会带来性能的损失。

public V get(Object key) {
            Entry<K,V> e = (Entry<K,V>)getEntry(key);
            if (e == null)
                return null;
            e.recordAccess(this);
            return e.value;
        }

--------------------

如何通过这种数据结构实现lru缓存？  
该哈希映射的迭代顺序就是最后访问其条目的顺序，这种映射很适合构建 LRU 缓存。LinkedHashMap 提供了 removeEldestEntry(Map.Entry<K,V> eldest) 方法。该方法可以提供在每次添加新条目时移除最旧条目的实现程序，默认返回 false，这样，此映射的行为将类似于正常映射，即永远不能移除最旧的元素。

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
            return false;
        }

LinkedHashMap在添加元素的时候会对此进行判断

void addEntry(int hash, K key, V value, int bucketIndex) {
            super.addEntry(hash, key, value, bucketIndex);
    
            // Remove eldest entry if instructed
            Entry<K,V> eldest = header.after;
            if (removeEldestEntry(eldest)) {
                removeEntryForKey(eldest.key);
            }
        }

通过重写removeEldestEntry可以实现自定义容量的linkedlist  
LRU具体实现代码如下：

public class LRUCache<K, V> {
        private static final float hashTableLoadFactor = 0.75f;
        private LinkedHashMap<K, V> map;
        private int cacheSize;
        static Logger logger = LoggerFactory.getLogger(LRUCache.class);
    
        public LRUCache(int cacheSize) {
            this.cacheSize = cacheSize;
            int hashTableCapacity = (int) Math
                    .ceil(cacheSize / hashTableLoadFactor) + 1;
            map = new LinkedHashMap<K, V>(hashTableCapacity, hashTableLoadFactor, true) {
                private static final long serialVersionUID = 1;
    
                @Override
                protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                    return size() > LRUCache.this.cacheSize;
                }
            };
        }
    
        public synchronized V get(K key) {
            return map.get(key);
        }
    
        public synchronized void put(K key, V value) {
            map.put(key, value);
        }
    
        public synchronized Collection<Map.Entry<K, V>> getAll() {
            return Lists.newArrayList(map.entrySet());
        }
    
    
        public static void main(String[] args) {
            LRUCache<String, String> c = new LRUCache<String, String>(3);
            c.put("1", "one");
            c.put("2", "two");
            c.put("3", "three");
            c.put("4", "four");
            if (c.get("2") == null) {
                throw new Error();
            }
            c.put("5", "five");
            c.put("4", "second four");
            c.get("5");
            for (Map.Entry<String, String> e : c.getAll()) {
                logger.info(e.getKey() + " : " + e.getValue());
            }
        }