Java中的收缩LinkedHashMap

Question

如何缩小LinkedHashMap？我覆盖了removeEldestEntry方法，但是当插入新值时，该方法仅被调用一次。因此，以这种方式缩小地图没有变化。

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

我唯一能想到的就是遍历整个过程。但这可能需要一段时间...

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

[如果删除Iterator方法中的maxSize，则可以删除removeEldestEntry的第一个值，然后重新插入它们。然后重新插入将淘汰最旧的值。这是非常丑陋的代码...还有更好的主意吗？

编辑：抱歉，迭代顺序从最早到最小。这样很简单

Answer 1

迭代器将从LinekdHashMap的最旧的迭代到最年轻的。如果您想将LinkedHashMap缩小到一个大小，则可以使用以下代码。

Map<K,V> lhm =
int desiredSize = 
for(Iterator iter = lhm.keySet().iterator();iter.hasNext()) {
   if(lhm.size() <= desiredSize) break;
   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<LRUCacheNotify> subscribers = new ArrayList<>();

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

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

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

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

    private void subscribe(LRUCacheNotify 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(LRUCacheNotify 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 LRUCacheNotify{
        int onNotifyHeadRemoval(Map.Entry Head);
    }
}

使用此LRU Cache实现的测试类：

package com.javaTutorialProject;

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

public class TestLRUCache implements LRUCache.LRUCacheNotify {
    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;
    }
}