Сжатие LinkedHashMap в Java

Question

Как вы можете уменьшить LinkedHashMap? Я преодолел removeEldestEntry метод, но этот метод вызывается только один раз, когда вставляется новое значение. Таким образом, нет изменений в уменьшении карты таким образом.

LinkedHashMap только дает мой нормальный Iterator и не имеет removeLast или же listIterator метод, так как вы можете найти последние, скажем 1000, записи и удалить их?

Единственный способ, которым я могу придумать, - это повторять все это. Но это может занять целую вечность...

Создание новой карты каждый раз, когда я хочу удалить только несколько элементов, также разрушит память.

Может быть, удалить первые значения Iterator а затем снова вставил их, когда maxSize был уменьшен в removeEldestEntry метод. Тогда переустановка выкинет самые старые значения. Это очень уродливый код... Есть идеи получше?

РЕДАКТИРОВАТЬ: Sry порядок итераций самый старый для самого младшего. Так легко

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 нс на каждую удаленную запись.

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 Cache:

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