SelfExpiringHashMap - a Java Map which entries expire automatically after a given time; it uses a DelayQueue internally.

SelfExpiringHashMap.java

/*
 * Copyright (c) 2019 Pierantonio Cangianiello
 * 
 * MIT License
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
import java.util.Collection;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.WeakHashMap;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.DelayQueue;
import java.util.concurrent.Delayed;
import java.util.concurrent.TimeUnit;

/**
 * A HashMap which entries expires after the specified life time.
 * The life-time can be defined on a per-key basis, or using a default one, that is passed to the 
 * constructor.
 * 
 * @author Pierantonio Cangianiello
 * @param <K> the Key type
 * @param <V> the Value type
 */
public class SelfExpiringHashMap<K, V> implements SelfExpiringMap<K, V> {

    private final Map<K, V> internalMap;

    private final Map<K, ExpiringKey<K>> expiringKeys;

    /**
     * Holds the map keys using the given life time for expiration.
     */
    private final DelayQueue<ExpiringKey> delayQueue = new DelayQueue<ExpiringKey>();

    /**
     * The default max life time in milliseconds.
     */
    private final long maxLifeTimeMillis;

    public SelfExpiringHashMap() {
        internalMap = new ConcurrentHashMap<K, V>();
        expiringKeys = new WeakHashMap<K, ExpiringKey<K>>();
        this.maxLifeTimeMillis = Long.MAX_VALUE;
    }

    public SelfExpiringHashMap(long defaultMaxLifeTimeMillis) {
        internalMap = new ConcurrentHashMap<K, V>();
        expiringKeys = new WeakHashMap<K, ExpiringKey<K>>();
        this.maxLifeTimeMillis = defaultMaxLifeTimeMillis;
    }

    public SelfExpiringHashMap(long defaultMaxLifeTimeMillis, int initialCapacity) {
        internalMap = new ConcurrentHashMap<K, V>(initialCapacity);
        expiringKeys = new WeakHashMap<K, ExpiringKey<K>>(initialCapacity);
        this.maxLifeTimeMillis = defaultMaxLifeTimeMillis;
    }

    public SelfExpiringHashMap(long defaultMaxLifeTimeMillis, int initialCapacity, float loadFactor) {
        internalMap = new ConcurrentHashMap<K, V>(initialCapacity, loadFactor);
        expiringKeys = new WeakHashMap<K, ExpiringKey<K>>(initialCapacity, loadFactor);
        this.maxLifeTimeMillis = defaultMaxLifeTimeMillis;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public int size() {
        cleanup();
        return internalMap.size();
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean isEmpty() {
        cleanup();
        return internalMap.isEmpty();
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean containsKey(Object key) {
        cleanup();
        return internalMap.containsKey((K) key);
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean containsValue(Object value) {
        cleanup();
        return internalMap.containsValue((V) value);
    }

    @Override
    public V get(Object key) {
        cleanup();
        renewKey((K) key);
        return internalMap.get((K) key);
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public V put(K key, V value) {
        return this.put(key, value, maxLifeTimeMillis);
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public V put(K key, V value, long lifeTimeMillis) {
        cleanup();
        ExpiringKey delayedKey = new ExpiringKey(key, lifeTimeMillis);
        ExpiringKey oldKey = expiringKeys.put((K) key, delayedKey);
        if(oldKey != null) {
            expireKey(oldKey);
            expiringKeys.put((K) key, delayedKey);
        }
        delayQueue.offer(delayedKey);
        return internalMap.put(key, value);
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public V remove(Object key) {
        V removedValue = internalMap.remove((K) key);
        expireKey(expiringKeys.remove((K) key));
        return removedValue;
    }

    /**
     * Not supported.
     */
    @Override
    public void putAll(Map<? extends K, ? extends V> m) {
        throw new UnsupportedOperationException();
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean renewKey(K key) {
        ExpiringKey<K> delayedKey = expiringKeys.get((K) key);
        if (delayedKey != null) {
            delayedKey.renew();
            return true;
        }
        return false;
    }

    private void expireKey(ExpiringKey<K> delayedKey) {
        if (delayedKey != null) {
            delayedKey.expire();
            cleanup();
        }
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public void clear() {
        delayQueue.clear();
        expiringKeys.clear();
        internalMap.clear();
    }

    /**
     * Not supported.
     */
    @Override
    public Set<K> keySet() {
        throw new UnsupportedOperationException();
    }

    /**
     * Not supported.
     */
    @Override
    public Collection<V> values() {
        throw new UnsupportedOperationException();
    }

    /**
     * Not supported.
     */
    @Override
    public Set<Entry<K, V>> entrySet() {
        throw new UnsupportedOperationException();
    }

    private void cleanup() {
        ExpiringKey<K> delayedKey = delayQueue.poll();
        while (delayedKey != null) {
            internalMap.remove(delayedKey.getKey());
            expiringKeys.remove(delayedKey.getKey());
            delayedKey = delayQueue.poll();
        }
    }

    private class ExpiringKey<K> implements Delayed {

        private long startTime = System.currentTimeMillis();
        private final long maxLifeTimeMillis;
        private final K key;

        public ExpiringKey(K key, long maxLifeTimeMillis) {
            this.maxLifeTimeMillis = maxLifeTimeMillis;
            this.key = key;
        }

        public K getKey() {
            return key;
        }

        /**
         * {@inheritDoc}
         */
        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (getClass() != obj.getClass()) {
                return false;
            }
            final ExpiringKey<K> other = (ExpiringKey<K>) obj;
            if (this.key != other.key && (this.key == null || !this.key.equals(other.key))) {
                return false;
            }
            return true;
        }

        /**
         * {@inheritDoc}
         */
        @Override
        public int hashCode() {
            int hash = 7;
            hash = 31 * hash + (this.key != null ? this.key.hashCode() : 0);
            return hash;
        }

        /**
         * {@inheritDoc}
         */
        @Override
        public long getDelay(TimeUnit unit) {
            return unit.convert(getDelayMillis(), TimeUnit.MILLISECONDS);
        }

        private long getDelayMillis() {
            return (startTime + maxLifeTimeMillis) - System.currentTimeMillis();
        }

        public void renew() {
            startTime = System.currentTimeMillis();
        }

        public void expire() {
            startTime = Long.MIN_VALUE;
        }

        /**
         * {@inheritDoc}
         */
        @Override
        public int compareTo(Delayed that) {
            return Long.compare(this.getDelayMillis(), ((ExpiringKey) that).getDelayMillis());
        }
    }
}

SelfExpiringHashMapTests.java

/*
 * Copyright (c) 2019 Pierantonio Cangianiello
 * 
 * MIT License
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
import it.pcan.util.map.SelfExpiringHashMap;
import it.pcan.util.map.SelfExpiringMap;
import static org.junit.Assert.*;
import org.junit.Test;

/**
 *
 * @author Pierantonio Cangianiello
 */
public class SelfExpiringHashMapTests {

    private final static int SLEEP_MULTIPLIER = 80;

    @Test
    public void basicGetTest() throws InterruptedException {
        SelfExpiringMap<String, String> map = new SelfExpiringHashMap<String, String>();
        map.put("a", "b", 2 * SLEEP_MULTIPLIER);
        Thread.sleep(1 * SLEEP_MULTIPLIER);
        assertEquals("b", map.get("a"));
    }

    @Test
    public void basicExpireTest() throws InterruptedException {
        SelfExpiringMap<String, String> map = new SelfExpiringHashMap<String, String>();
        map.put("a", "b", 2 * SLEEP_MULTIPLIER);
        Thread.sleep(3 * SLEEP_MULTIPLIER);
        assertNull(map.get("a"));
    }

    @Test
    public void basicRenewTest() throws InterruptedException {
        SelfExpiringMap<String, String> map = new SelfExpiringHashMap<String, String>();
        map.put("a", "b", 3 * SLEEP_MULTIPLIER);
        Thread.sleep(2 * SLEEP_MULTIPLIER);
        map.renewKey("a");
        Thread.sleep(2 * SLEEP_MULTIPLIER);
        assertEquals("b", map.get("a"));
    }

    @Test
    public void getRenewTest() throws InterruptedException {
        SelfExpiringMap<String, String> map = new SelfExpiringHashMap<String, String>();
        map.put("a", "b", 3 * SLEEP_MULTIPLIER);
        Thread.sleep(2 * SLEEP_MULTIPLIER);
        assertEquals("b", map.get("a"));
        Thread.sleep(2 * SLEEP_MULTIPLIER);
        assertEquals("b", map.get("a"));
    }

    @Test
    public void multiplePutThenRemoveTest() throws InterruptedException {
        SelfExpiringMap<String, String> map = new SelfExpiringHashMap<String, String>();
        map.put("a", "b", 2 * SLEEP_MULTIPLIER);
        Thread.sleep(1 * SLEEP_MULTIPLIER);
        map.put("a", "c", 2 * SLEEP_MULTIPLIER);
        Thread.sleep(1 * SLEEP_MULTIPLIER);
        map.put("a", "d", 400 * SLEEP_MULTIPLIER);
        Thread.sleep(2 * SLEEP_MULTIPLIER);
        assertEquals("d", map.remove("a"));
    }

    @Test
    public void multiplePutThenGetTest() throws InterruptedException {
        SelfExpiringMap<String, String> map = new SelfExpiringHashMap<String, String>();
        map.put("a", "b", 2 * SLEEP_MULTIPLIER);
        Thread.sleep(1 * SLEEP_MULTIPLIER);
        map.put("a", "c", 2 * SLEEP_MULTIPLIER);
        Thread.sleep(1 * SLEEP_MULTIPLIER);
        map.put("a", "d", 400 * SLEEP_MULTIPLIER);
        Thread.sleep(2 * SLEEP_MULTIPLIER);
        assertEquals("d", map.get("a"));
    }
    
    @Test
    public void insertionOrderTest() throws InterruptedException {
        SelfExpiringMap<String, Integer> map = new SelfExpiringHashMap<String, Integer>(30000);
        map.put("123456", 999);
        assertEquals(map.get("123456"), Integer.valueOf(999));
        map.put("123456", 123);
        map.put("777456", 333);
        assertEquals(map.get("123456"), Integer.valueOf(123));
        assertEquals(map.get("777456"), Integer.valueOf(333));
        map.put("777456", 123);
        map.put("123456", 321);
        assertEquals(map.get("123456"), Integer.valueOf(321));
        assertEquals(map.get("777456"), Integer.valueOf(123));
    }

}

SelfExpiringMap.java

/*
 * Copyright (c) 2019 Pierantonio Cangianiello
 * 
 * MIT License
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

import java.util.Map;

/**
 *
 * @author Pierantonio Cangianiello
 * @param <K> the Key type
 * @param <V> the Value type
 */
public interface SelfExpiringMap<K, V> extends Map<K, V> {

    /**
     * Renews the specified key, setting the life time to the initial value.
     *
     * @param key
     * @return true if the key is found, false otherwise
     */
    public boolean renewKey(K key);

    /**
     * Associates the given key to the given value in this map, with the specified life
     * times in milliseconds.
     *
     * @param key
     * @param value
     * @param lifeTimeMillis
     * @return a previously associated object for the given key (if exists).
     */
    public V put(K key, V value, long lifeTimeMillis);
        
}

Hi @dehad. At the moment, this implementation is not available on Maven, but you can copy the source code in your project. Please, just keep the copyright & license notice in the top comment. Thanks for your interest.

Code:
SelfExpiringHashMap selfExpiringHashMap = new SelfExpiringHashMap(300*1000);
selfExpiringHashMap.put(new Pair("123", "456"), 999);
System.out.println(selfExpiringHashMap);
selfExpiringHashMap.put(new Pair("123", "456"), 123);
selfExpiringHashMap.put(new Pair("777", "456"), 333);
System.out.println(selfExpiringHashMap);
selfExpiringHashMap.put(new Pair("777", "456"), 123);
selfExpiringHashMap.put(new Pair("123", "456"), 321);
System.out.println(selfExpiringHashMap);
Output:
SelfExpiringHashMap{internalMap={123=456=999}}
SelfExpiringHashMap{internalMap={123=456=123, 777=456=333}}
SelfExpiringHashMap{internalMap={123=456=321}}
Seems buggy. Now I use org.apache.commons.collections4.map.PassiveExpiringMap instead.

Hi @VladimirKhizmatulin, thanks for reporting this issue. I fixed it (it was a wrong time setting on key expiration). I updated the tests too. Beware that PassiveExpiringMap does a full map scan when it removes expired entries; my ExpiringEntriesMap, instead, just iterates the expired keys because it uses a DelayQueue.

Hello Pierantonio, would you please elaborate on the usage of the WeakHashMap. Aren't there concurrency concerns, as its not thread-safe? What is the expected benefit?

Hi Pierantonio, thanks for making your codes available. Just want to double-check. Look like get() will renew the key, yes? Per test case

    @Test
    public void getRenewTest() throws InterruptedException {
        SelfExpiringMap<String, String> map = new SelfExpiringHashMap<String, String>();
        map.put("a", "b", 3 * SLEEP_MULTIPLIER);
        Thread.sleep(2 * SLEEP_MULTIPLIER);
        Assert.assertEquals("b", map.get("a"));
        Thread.sleep(2 * SLEEP_MULTIPLIER);
        Assert.assertEquals("b", map.get("a"));
    }

For my use case, I prefer not to "renew" on each get. Is there any possible side effect if I just skip the renewKey() call in get()?

    private boolean renewKeyOnGet = false;

    @Override
    public V get(Object key) {
        cleanup();
        if (renewKeyOnGet) {
            renewKey((K) key);
        }
        return internalMap.get((K) key);
    }

Hello Pierantonio, would you please elaborate on the usage of the WeakHashMap. Aren't there concurrency concerns, as its not thread-safe? What is the expected benefit?

This class has not been tested in a multithreading environment. However, you may use a synchronizer wrapper like Collections.synchronizedMap(). The main benefit of this implementation is the absence of a backing thread that cleans up the map, since I use a DelayQueue here.

Hi Pierantonio, thanks for making your codes available. Just want to double-check. Look like get() will renew the key, yes?

Hi, thank you for your interest 😃
Yes, at the moment the Expiring Map works like a standard "cache", but if you need more control you may add the renewKeyOnGet boolean, of course. I don't think there are unwanted side effects, but I suggest to write some additional unit tests.

i have one used the selfexpiring hash map. it is very buggy . use this https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/map/PassiveExpiringMap.html

i have one used the selfexpiring hash map. it is very buggy . use this https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/map/PassiveExpiringMap.html

Hi @prasanthmp500. Thank you for your comment. I would just ask you two things:

1. You have been pretty vague by saying "it is very buggy". Could you report your failed test case(s), please?
2. Did you know that Apache PassiveExpiringMap always does a full map scan for each operation? It's very, very inefficient for the medium usage (except when building a toy use-case). This implementation uses an high-efficient priority queue based on entries delay.

Said that, please note that SelfExpiringHashMap has been in a true production environment for many years, till now without any issue.

There is a bug in renewKey(K key)
In the if (delayedKey != null) condition, the following 2 lines are required to move the renewed element to the end of the queue.
delayedKey.renew();
delayQueue.remove(delayedKey); // added
delayQueue.add(delayedKey); // added

There is a bug in renewKey(K key)
In the if (delayedKey != null) condition, the following 2 lines are required to move the renewed element to the end of the queue.
delayedKey.renew();
delayQueue.remove(delayedKey); // added
delayQueue.add(delayedKey); // added

Can you explain why this is needed?

i have one used the selfexpiring hash map. it is very buggy . use this https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/map/PassiveExpiringMap.html

Hi @prasanthmp500. Thank you for your comment. I would just ask you two things:

1. You have been pretty vague by saying "it is very buggy". Could you report your failed test case(s), please?
2. Did you know that Apache PassiveExpiringMap always does a full map scan for each operation? It's very, very inefficient for the medium usage (except when building a toy use-case). This implementation uses an high-efficient priority queue based on entries delay.

Said that, please note that PassiveExpiringMap has been in a true production environment for many years, till now without any issue.

I am considering using your gist, thank you!

Can I use it importing it as a library?

Can I use it importing it as a library?

@ignaciorecuerda currently this class is not part of any library, you can copy the source code directly in your project; just keep the included license information comments.
Thank you for your interest.

Thank you @pcan

Hi,
While testing out this code, I came across a test case that was not giving me the expected result. I noticed that if the first element is renewed, the second element even if expired, will not be removed from the map. If the order of initial insert are swapped, the test case passes. I had to either remove the renew method, which was called from the get method or remove the element and re-insert it to the map in a synchronized method to ensure all the keys expire in the cleanup method as expected. Is this the correct way to do this?

@Test
public void multiplePutTillExpireTest() throws InterruptedException {
    SelfExpiringMap<String, String> map = new SelfExpiringHashMap<>(60000);
    map.put("Test1.txt", "c");
    map.put("Test2.txt", "b");
    Thread.sleep(50*1000);
    if(map.containsKey("Test1.txt"))
        map.get("Test1.txt");
    Thread.sleep(40*1000);
    assertFalse(map.containsKey("Test2.txt"));

}

Hi @prameeshas, this issue seems related to the DelayQueue internals, since it lacks an efficient mechanism for key renewal. I'm going to fix the implementation in order to make your test case pass. Thank you for reporting this issue.

Hi @pcan, the current implementation seems to leak elements in the DelayQueue when removing them from the map before they expire. After e.g. invoking:

map.put("foo", 1);
map.remove("foo");

the SelfExpiringHashMap seems to be empty at first glance, but the DelayQueue still holds an ExpiringKey instance for the key "foo". The issue seems to come from the change to set startTime = Long.MIN_VALUE when expire() is called for this key and the subsequent calculation of getDelay(). Polling the queue fails then. After making ExpiringKey available to this small test by declaring it public static you can see that an expired key (what remove is essentially doing) cannot be polled from the queue:

@Test
void testDelay() {
    final DelayQueue<ExpiringKey<String>> queue = new DelayQueue<>();
    final ExpiringKey<String> key = new ExpiringKey<>("foo", 1000);
    queue.add(key);
    key.expire();
    assertNotNull(queue.poll());
}

hi @fdummert, basically this triggers the same issue of the one reported by prameeshas. I still haven't got time to fix this, but basically I will move the implementation to a RB-tree instead of a priority-queue based (as current DelayQueue implementation relies on).

Hi @pcan , why SelfExpiringHashMap.values() method throw UnsupportedOperationException? Is there any specific reason? What if it is implemented like below

@OverRide
public Collection values() {
cleanup();
return internalMap.values();
}

Hi @pcan , why method get(Object key) need to renewKey() again?