Shrink LinkedHashMap in Java

How can you shrink a LinkedHashMap? I overrode the removeEldestEntry method, but this method is only called once when a new value is inse开发者_如何学Pythonrted. So there is no change of making the map smaller this way.

The LinkedHashMap only gives my a normal Iterator and doesn't have any removeLast or listIterator method, so how can you find the last, say 1000, entries and remove them?

The only way I can think of is iterating through that whole thing. But that can take ages...

Creating a new map every time I want to remove only a few elements will also destroy the memory.

Maybe remove the first values of the Iterator and then reinserted them, when the maxSize was reduced in the removeEldestEntry method. Then the reinserting would kick out the oldest values. This is very ugly code... Any better ideas?

EDIT: Sry the iteration order is oldest to youngest. So it's easy

The iterator will iterate from oldest to youngest for LinekdHashMap. You if you want to shrink the LinkedHashMap to a size you can use the following.

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

This should take about 20 ns per entry removed.

LRU cache Implementation which uses LinkedHashMap(access ordered). This also performs shrink and expand on the fly via a return value from the caller's notification callback registered/subscribed to this class's events.

Code is pretty well commented to detail the implementation.

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

Testing class which uses this LRU Cache implementation:

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