Delete old objects from HashMap to achieve a specific size?

Question

I have a hashmap in Java that I need to limit the size (of the order of 50,000). But I have to remove only those items that are the oldest. The timestamp of the item is stored in the field of the recording object:

Map<String, MyModel> snapshot = new  HashMap<>();

and

public class MyModel { 
    private ZonedDateTime createdAt;
    // other fields...
}

I also insert them into the map in order by this timestamp.

What would be the most efficient way to do this kind of deletion of the oldest entries? Please note that the "threshold" in time is unknown, only the desired final size of the Card.

Answer 1

HashMap "", "", .

A LinkedHashMap, , , , , removeEldestEntry:

public static void main(final String args[]) throws Exception {
    final int maxSize = 4;
    final LinkedHashMap<String, String> cache = new LinkedHashMap<String, String>() {
        @Override
        protected boolean removeEldestEntry(final Map.Entry eldest) {
            return size() > maxSize;
        }
    };

    cache.put("A", "A");
    System.out.println(cache);
    cache.put("B", "A");
    System.out.println(cache);
    cache.put("C", "A");
    System.out.println(cache);
    cache.put("D", "A");
    System.out.println(cache);
    cache.put("E", "A");
    System.out.println(cache);
    cache.put("F", "A");
    System.out.println(cache);
    cache.put("G", "A");
}

:

{A=A}
{A=A, B=A}
{A=A, B=A, C=A}
{A=A, B=A, C=A, D=A}
{B=A, C=A, D=A, E=A}
{C=A, D=A, E=A, F=A}

---

, synchronized. , , synchronized . synchronizing , , , . , "" Collections.synchronizedMap. , :

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

_{LinkedHashMap JavaDoc}

Answer 2

: HashMap . : all , ; , .

: HashMap : . , . : .

TreeSet , timestimamps.

: :

Answer 3

String , - . :

while(map.size()>50000){
    map.remove(list.get(0))
    list.remove(0);
}

, , .

, , ,

Answer 4

LruCache Android .

.

import java.util.LinkedHashMap;
import java.util.Map;

public class RemoveOldHashMap<K, V> {
    private final LinkedHashMap<K, V> map;
    /** Size of this cache in units. Not necessarily the number of elements. */
    private int size;
    private int maxSize;
    private int putCount;
    private int createCount;
    private int evictionCount;
    private int hitCount;
    private int missCount;
    /**
     * @param maxSize for caches that do not override {@link #sizeOf}, this is
     *     the maximum number of entries in the cache. For all other caches,
     *     this is the maximum sum of the sizes of the entries in this cache.
     */
    public RemoveOldHashMap(int maxSize) {
        if (maxSize <= 0) {
            throw new IllegalArgumentException("maxSize <= 0");
        }
        this.maxSize = maxSize;
        this.map = new LinkedHashMap<K, V>(0, 0.75f, false); // false for "interaction order"
    }
    /**
     * Returns the value for {@code key} if it exists in the cache or can be
     * created by {@code #create}. If a value was returned, it is moved to the
     * head of the queue. This returns null if a value is not cached and cannot
     * be created.
     */
    public synchronized final V get(K key) {
        if (key == null) {
            throw new NullPointerException("key == null");
        }

        for (K k : map.keySet()) {
            System.out.println("k = " + k);
        }

        V result = map.get(key);

        for (K k : map.keySet()) {
            System.out.println("k = " + k);
        }

        if (result != null) {
            hitCount++;
            return result;
        }
        missCount++;
        // TODO: release the lock while calling this potentially slow user code
        result = create(key);
        if (result != null) {
            createCount++;
            size += safeSizeOf(key, result);
            map.put(key, result);
            trimToSize(maxSize);
        }
        return result;
    }
    /**
     * Caches {@code value} for {@code key}. The value is moved to the head of
     * the queue.
     *
     * @return the previous value mapped by {@code key}. Although that entry is
     *     no longer cached, it has not been passed to {@link #entryEvicted}.
     */
    public synchronized final V put(K key, V value) {
        if (key == null || value == null) {
            throw new NullPointerException("key == null || value == null");
        }
        putCount++;
        size += safeSizeOf(key, value);
        V previous = map.put(key, value);
        if (previous != null) {
            size -= safeSizeOf(key, previous);
        }
        trimToSize(maxSize);
        return previous;
    }
    private void trimToSize(int maxSize) {
        while (size > maxSize && !map.isEmpty()) {
            Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
            if (toEvict == null) {
                break; // map is empty; if size is not 0 then throw an error below
            }
            K key = toEvict.getKey();
            V value = toEvict.getValue();
            map.remove(key);
            size -= safeSizeOf(key, value);
            evictionCount++;
            // TODO: release the lock while calling this potentially slow user code
            entryEvicted(key, value);
        }
        if (size < 0 || (map.isEmpty() && size != 0)) {
            throw new IllegalStateException(getClass().getName()
                    + ".sizeOf() is reporting inconsistent results!");
        }
    }
    /**
     * Removes the entry for {@code key} if it exists.
     *
     * @return the previous value mapped by {@code key}. Although that entry is
     *     no longer cached, it has not been passed to {@link #entryEvicted}.
     */
    public synchronized final V remove(K key) {
        if (key == null) {
            throw new NullPointerException("key == null");
        }
        V previous = map.remove(key);
        if (previous != null) {
            size -= safeSizeOf(key, previous);
        }
        return previous;
    }
    /**
     * Called for entries that have reached the tail of the least recently used
     * queue and are be removed. The default implementation does nothing.
     */
    protected void entryEvicted(K key, V value) {}
    /**
     * Called after a cache miss to compute a value for the corresponding key.
     * Returns the computed value or null if no value can be computed. The
     * default implementation returns null.
     */
    protected V create(K key) {
        return null;
    }
    private int safeSizeOf(K key, V value) {
        int result = sizeOf(key, value);
        if (result < 0) {
            throw new IllegalStateException("Negative size: " + key + "=" + value);
        }
        return result;
    }
    /**
     * Returns the size of the entry for {@code key} and {@code value} in
     * user-defined units.  The default implementation returns 1 so that size
     * is the number of entries and max size is the maximum number of entries.
     *
     * <p>An entry size must not change while it is in the cache.
     */
    protected int sizeOf(K key, V value) {
        return 1;
    }
    /**
     * Clear the cache, calling {@link #entryEvicted} on each removed entry.
     */
    public synchronized final void evictAll() {
        trimToSize(-1); // -1 will evict 0-sized elements
    }
    /**
     * For caches that do not override {@link #sizeOf}, this returns the number
     * of entries in the cache. For all other caches, this returns the sum of
     * the sizes of the entries in this cache.
     */
    public synchronized final int size() {
        return size;
    }
    /**
     * For caches that do not override {@link #sizeOf}, this returns the maximum
     * number of entries in the cache. For all other caches, this returns the
     * maximum sum of the sizes of the entries in this cache.
     */
    public synchronized final int maxSize() {
        return maxSize;
    }
    /**
     * Returns the number of times {@link #get} returned a value.
     */
    public synchronized final int hitCount() {
        return hitCount;
    }
    /**
     * Returns the number of times {@link #get} returned null or required a new
     * value to be created.
     */
    public synchronized final int missCount() {
        return missCount;
    }
    /**
     * Returns the number of times {@link #create(Object)} returned a value.
     */
    public synchronized final int createCount() {
        return createCount;
    }
    /**
     * Returns the number of times {@link #put} was called.
     */
    public synchronized final int putCount() {
        return putCount;
    }
    /**
     * Returns the number of values that have been evicted.
     */
    public synchronized final int evictionCount() {
        return evictionCount;
    }
    /**
     * Returns a copy of the current contents of the cache, ordered from least
     * recently accessed to most recently accessed.
     */
    public synchronized final Map<K, V> snapshot() {
        return new LinkedHashMap<K, V>(map);
    }
    @Override public synchronized final String toString() {
        int accesses = hitCount + missCount;
        int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0;
        return String.format("LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]",
                maxSize, hitCount, missCount, hitPercent);
    }
}

String Integer. - 2 , .

RemoveOldHashMap<Integer, String> hash = new RemoveOldHashMap<Integer, String>(2 /* here is max value that the internal counter reaches */ ) {
    // Override to tell how your object is measured
    @Override
    protected int sizeOf(Integer key, String value) {
        return 1; // the size of your object
    }
};

: LruCache