image.png

修复描述 https://github.com/lets-blade/blade/pull/382

package com.blade.kit;

import java.util.*;

/**
 * @author darren
 * @date 2019/10/16 13:39
 */
public class LRUSet<E> extends AbstractSet<E>{
    private transient    HashMap<E, Object> map;
    private static final Object             PRESENT = new Object();

    public LRUSet(int capacity) {
        this.map = new LinkedHashMap<E, Object>(Math.min(32,capacity), .75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
               // 这个capacity，准确说应该是initialCapacity，值不会改变了。理论上这个LRUSet最多扩容一次
                return size() > capacity;
            }
        };
    }

    @Override
    public int size() {
        return map.size();
    }

    @Override
    public boolean isEmpty() {
        return map.isEmpty();
    }

    @Override
    public boolean contains(Object o) {
       // 只要map的value存在值就是不为空
        return map.get(o) == PRESENT;
    }

    @Override
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

    @Override
    public boolean add(E e) {
       // map的put方法会返回原来的value，如果原来为null那么就添加成功，如果原来已经有了value，那么就是false。所有的put，也都是放一个空对象Object
        return map.put(e, PRESENT) == null;
    }

    @Override
    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }

    @Override
    public void clear() {
        map.clear();
    }
}

代码修改 https://github.com/lets-blade/blade/pull/382/files

从作者描述的观点来看，修复确实很严谨。后续使用java collection的时候都应该注意这些边界值。极大或者极小值得处理。

本次修复的重点看LinkedHashMap中的removeEldestEntry()这个方法

    /**
     * Returns <tt>true</tt> if this map should remove its eldest entry.
     * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after
     * inserting a new entry into the map.  It provides the implementor
     * with the opportunity to remove the eldest entry each time a new one
     * is added.  This is useful if the map represents a cache: it allows
     * the map to reduce memory consumption by deleting stale entries.
     *
     * <p>Sample use: this override will allow the map to grow up to 100
     * entries and then delete the eldest entry each time a new entry is
     * added, maintaining a steady state of 100 entries.
     * <pre>
     *     private static final int MAX_ENTRIES = 100;
     *
     *     protected boolean removeEldestEntry(Map.Entry eldest) {
     *        return size() &gt; MAX_ENTRIES;
     *     }
     * </pre>
     *
     * <p>This method typically does not modify the map in any way,
     * instead allowing the map to modify itself as directed by its
     * return value.  It <i>is</i> permitted for this method to modify
     * the map directly, but if it does so, it <i>must</i> return
     * <tt>false</tt> (indicating that the map should not attempt any
     * further modification).  The effects of returning <tt>true</tt>
     * after modifying the map from within this method are unspecified.
     *
     * <p>This implementation merely returns <tt>false</tt> (so that this
     * map acts like a normal map - the eldest element is never removed).
     *
     * @param    eldest The least recently inserted entry in the map, or if
     *           this is an access-ordered map, the least recently accessed
     *           entry.  This is the entry that will be removed it this
     *           method returns <tt>true</tt>.  If the map was empty prior
     *           to the <tt>put</tt> or <tt>putAll</tt> invocation resulting
     *           in this invocation, this will be the entry that was just
     *           inserted; in other words, if the map contains a single
     *           entry, the eldest entry is also the newest.
     * @return   <tt>true</tt> if the eldest entry should be removed
     *           from the map; <tt>false</tt> if it should be retained.
     */
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

利用上述这个方法，完成了一个LRU的实现。

LinkedHashMap不需要扩容（这个提问有误），那么为啥需要loadFactor负载因子呢？
答：LinkedHashMap是继承HashMap的，底层的逻辑是一样的，只是增加了前后的对象存储，所以也需要扩容，此外应该上面LRUSet的指定了loadFactor，为了满足HashMap的需求。

    /**
     * Constructs an empty <tt>LinkedHashMap</tt> instance with the
     * specified initial capacity, load factor and ordering mode.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @param  accessOrder     the ordering mode - <tt>true</tt> for
     *         access-order, <tt>false</tt> for insertion-order
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

不常见的一种for循环使用方式

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

LRU拓展：https://zhuanlan.zhihu.com/p/52196637