Delete oldest objects from HashMap to reach certain size?

Question

I have a hashmap in Java that I need to limit in size (order of 50000). But I should delete only items that are the oldest. The timestamp of the item is stored in the entry object's field:

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 that timestamp.

What would be the most effective way to accomplish this kind of deletion of oldest entries? Note that "threshold" in time is not known, only the desired final size of the Map.

Answer 1

HashMap has no "oldest", it has no "first", it has no order.

A LinkedHashMap on the other hand is designed for exactly this, it maintains a doubly linked list between the entries so keep them in insertion order, it also provides a removeEldestEntry method:

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

Output:

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

---

Large Health Warning

Note that this implementation is not synchronized. If multiple threads access a linked hash map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be "wrapped" using the Collections.synchronizedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:

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

_{LinkedHashMap JavaDoc}

Answer 2

It may be easiest just to add the String objects to a list whenever you put something in the map. Then you could do:

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

This works because you don't actually care about the time, just the order.

A queue would be better than a list in this regard as you don't need anything other than accessing and removing the first element