Java 中的 LinkedHashMap 收缩

Question

如何缩小LinkedHashMap？我重写了 removeEldestEntry 方法，但该方法仅在插入新值时调用一次。因此，以这种方式缩小地图并没有改变。

LinkedHashMap 只给了我一个普通的 Iterator 并且没有任何 removeLast 或 listIterator 方法，那么如何才能您找到最后的（例如 1000 个）条目并将其删除吗？

我能想到的唯一方法就是迭代整个事情。但这可能需要很长时间......

每次我只想删除一些元素时创建一个新地图也会破坏内存。

当 removeEldestEntry 方法中的 maxSize 减小时，可能会删除 Iterator 的第一个值，然后重新插入它们。然后重新插入会剔除最旧的值。这是非常丑陋的代码......还有更好的想法吗？

编辑：抱歉，迭代顺序是从最旧到最年轻的。所以这很容易

Answer 1

迭代器将从最旧的到最年轻的 LinekdHashMap 进行迭代。如果您想将 LinkedHashMap 缩小到可以使用以下内容的大小。

Map<K,V> lhm =
int desiredSize = 
for(Iterator iter = lhm.keySet().iterator();iter.hasNext()) {
   if(lhm.size() <= desiredSize) break;
   iter.next();     //required else IllegalStateException since current=null 
   iter.remove();
}

每个删除条目大约需要 20 ns。

Answer 2

LRU缓存使用LinkedHashMap（访问有序）实现。这还通过注册/订阅此类事件的调用者通知回调的返回值来动态执行收缩和扩展。

代码有很好的注释来详细说明实现。

package com.javaTutorialProject;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int maxEntries;
    private static final int DEFAULT_INITIAL_CAPACITY = 10;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;

    private ArrayList<LRUCacheOverflowNotify> subscribers = new ArrayList<>();

    public LRUCache(LRUCacheOverflowNotify subscriber,int initialCapacity,
                    float loadFactor,
                    int maxEntries) {
        super(initialCapacity, loadFactor, true);
        this.maxEntries = maxEntries;
        subscribe(subscriber);
    }

    public LRUCache(LRUCacheOverflowNotify subscriber, int initialCapacity,
                    int maxEntries) {
        this(subscriber, initialCapacity, DEFAULT_LOAD_FACTOR, maxEntries);
    }

    public LRUCache(LRUCacheOverflowNotify subscriber, int maxEntries) {
        this(subscriber, DEFAULT_INITIAL_CAPACITY, maxEntries);
    }

    // not very useful constructor
    public LRUCache(LRUCacheOverflowNotify subscriber, Map<? extends K, ? extends V> m,
                    int maxEntries) {
        this(subscriber, m.size(), maxEntries);
        putAll(m);
    }

    private void subscribe(LRUCacheOverflowNotify subscriber){
        if(subscriber != null) subscribers.add(subscriber);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry Head) {
        if(size() > maxEntries){                                                        // if overflow (we handle it)
            int savedMaxEntries = maxEntries, newMaxEntries;                            // get lowestMin/highestMax entries from all subscribers
            for(LRUCacheOverflowNotify subscriber: subscribers){                                // notify all subscribers
                newMaxEntries = subscriber.onNotifyHeadRemoval(Head);                   // receive opinion (shrink/expand/re-use)
                if(newMaxEntries > maxEntries && newMaxEntries > savedMaxEntries) {     // if new > max and new > last max expand
                    savedMaxEntries = newMaxEntries;                                    // save it
                    continue;
                }
                if(newMaxEntries < maxEntries && newMaxEntries < savedMaxEntries) {     // if new < max and new < last min shrink
                    savedMaxEntries = newMaxEntries;    // Head will be removed by      // save it
                }
            }

            if(savedMaxEntries > 0 && savedMaxEntries < maxEntries) {                   // if 0 < saved < max Shrink, reqSize-1(we already added 1)
                Iterator<K> iterator = this.keySet().iterator();                        // initialize iterator
                try {
                    while ((this.size() - 1) >= savedMaxEntries && iterator.hasNext()) {// if size >= shrinked_size and have next() try remove
                        iterator.next();                                                // prime it for iterator(else IllegalStateException)
                        iterator.remove();                                              // remove LRU element from LinkedHashMap
                    }
                }catch (IllegalStateException e){
                    e.printStackTrace();                                                // record Error stackTrace
                }
                maxEntries = this.size();                                               // re-initialize maxEntries count
                return false;                                                           // don't flush Head(LRU)
            }
            if(savedMaxEntries > maxEntries){                                           // if saved > max Expand,
                maxEntries = savedMaxEntries;                                           // max = saved
                return false;                                                           // don't flush Head(LRU)
            }
            return true;                                                                // if saved == max || saved < 0 , flush LRU entry (Head)
        }
        return false;
    }

    public interface LRUCacheOverflowNotify{
        int onNotifyHeadRemoval(Map.Entry Head);
    }
}

使用此 LRU 缓存实现的测试类：

package com.javaTutorialProject;

import java.util.Map;
import java.util.Random;

public class TestLRUCache implements LRUCache.LRUCacheOverflowNotify {
    static int size = 7;
    static int count = 0;
    public static void main(String[] args) {
        LRUCache<Integer,String> linkedHashMap = new LRUCache<Integer, String>(new TestLRUCache(), 5,0.75f, size);
        for(int i = 1; i < 35; i++){
            linkedHashMap.put(i,String.valueOf(i));
            System.out.println("Last inserted item: " + i);
            System.out.println("LRU Cache size: " + linkedHashMap.size());
            System.out.println("LRU Cache current: "+ linkedHashMap);
            // random access(to check LRU implementation)
            System.out.println("Last accessed item: " + linkedHashMap.get(new Random(System.currentTimeMillis()).nextInt(i)));
        }
    }

    @Override
    public int onNotifyHeadRemoval(Map.Entry Head) {
        System.out.println("Count: " + ++count);
        if(count==2) size -=2;
        if(count==5) size +=2;
        if(count==10) size -= 2;
        if(count==15) size += 2;
        if(count==20) size -= 2;

        return size;
    }
}