Java time expiring List/Set?

Question

I've been looking around for a Java list, set, or something similar that has entries expire after a given time period, but I have yet to find one. I've found Guava's CacheBuilder, which would be almost perfect for my use, but that it is a map rather than a List or Set. Is there already something out there like this, or will I have to make one if I want to use it?

Brisbane

I'm having a hard time seeing a use case as well. Typically when you want to cache things, you need a key to retrieve what's being cached, hence why every cache implementation works with the Map interface (or something similar). – Zaslow

you can still iterate over the Set – Burns

I'm making an anti-repeat message plugin for a chatroom where users talk. I use a map to link the user to a list of messages that I check the new message against. I want to only store 5 messages in any one user's list(already completed), and have any stored messages that are over x units of time old expire. – Brisbane

Another use case is to get the number of requests received in a server in the past 1 hour – Mycenae

Answer 1

To use CacheBuilder to get a time expired list, you could put your objects in the map as keys and some dummy object as values.

Churchwell

Or use your objects as key and value. Just take care not to create a new object for each dummy, as that would be waste. – Reneta

Answer 2

You could decorate a collection implementation to do that. Something like this:

public class ExpirableArrayList<E> extends ArrayList<E> {

    private final Date creation = new Date();

    private final long timeToLiveInMs;

    public ExpirableArrayList(long timeToLiveInMs, int initialCapacity) {
        super(initialCapacity);
        this.timeToLiveInMs = timeToLiveInMs;
    }

    public ExpirableArrayList(long timeToLiveInMs) {
        this.timeToLiveInMs = timeToLiveInMs;
    }

    public ExpirableArrayList(long timeToLiveInMs, Collection<? extends E> c) {
        super(c);
        this.timeToLiveInMs = timeToLiveInMs;
    }

    private void expire() {
        if (System.currentTimeMillis() - creation.getTime() > timeToLiveInMs) {
            clear();
        }
    }

    @Override
    public int size() {
        expire();
        return super.size();
    }

    @Override
    public boolean isEmpty() {
        expire();
        return super.isEmpty();
    }

    @Override
    public boolean contains(Object o) {
        expire();
        return super.contains(o);
    }

    @Override
    public Iterator<E> iterator() {
        expire();
        return super.iterator();
    }

    @Override
    public Object[] toArray() {
        expire();
        return super.toArray();
    }

    @Override
    public <T> T[] toArray(T[] a) {
        expire();
        return super.toArray(a);
    }

    @Override
    public boolean add(E e) {
        expire();
        return super.add(e);
    }

    @Override
    public boolean remove(Object o) {
        expire();
        return super.remove(o);
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        expire();
        return super.contains(c);
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        expire();
        return super.addAll(c);
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> c) {
        expire();
        return super.addAll(index, c);
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        expire();
        return super.removeAll(c);
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        expire();
        return super.retainAll(c);
    }

    @Override
    public E get(int index) {
        expire();
        return super.get(index);
    }

    @Override
    public E set(int index, E element) {
        expire();
        return super.set(index, element);
    }

    @Override
    public E remove(int index) {
        expire();
        return super.remove(index);
    }

    @Override
    public int indexOf(Object o) {
        expire();
        return indexOf(o);
    }

    @Override
    public int lastIndexOf(Object o) {
        expire();
        return lastIndexOf(o);
    }

    @Override
    public ListIterator<E> listIterator() {
        expire();
        return listIterator();
    }

    @Override
    public ListIterator<E> listIterator(int index) {
        expire();
        return listIterator();
    }

    @Override
    public List<E> subList(int fromIndex, int toIndex) {
        expire();
        return subList(fromIndex, toIndex);
    }
}

Favorite

I don't think this is the intention. Each entry should have its own timestamp. – Gabor

So you should use a map. – Favorite

No. It's like a set where the entry is no longer present once the time has passed. Of course, you can get the same behaviour with a guava cache map where the value is some dummy value like the key itself or boolean. – Gabor

Answer 3

The missing piece here is the function Collections#newSetFromMap. This is exactly what you need to use Guava's CacheBuilder with all its features. For instance, to create a set whose objects expire after a minute, you could use:

Set<String> set = Collections.newSetFromMap(CacheBuilder.newBuilder().expireAfterWrite(Duration.ofMinutes(1)).<String, Boolean>build().asMap());

You need to use Boolean as the dummy value type here, as Collections#newSetFromMap expects a Map<E, Boolean>.

Contingent

Answer 4

Since the Java HashSet implementation uses internally a HashMap, it should be really easy to copy/modify the code so that it uses Guavas CacheBuilder.

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;
...

In other words, just implement your SetWithExpiration as a CacheBuilder map from key to key. This will lose no more efficiency than the Java HashSet implementation loses by using an underlying HashMap.

Burns

Not so simple. Re-inventing the HashSet class is a bad idea, and you can't just "make HashSet use a CacheBuilder instead" – Listless

yes, the clean code solution would be to extend AbstractSet and use internally a Map which is passed by dependecy injection. – Burns