Skip to content

Instantly share code, notes, and snippets.

@joelittlejohn
Last active October 4, 2023 10:50
Show Gist options
  • Save joelittlejohn/5565410 to your computer and use it in GitHub Desktop.
Save joelittlejohn/5565410 to your computer and use it in GitHub Desktop.
A passive TTL hash map, that expires and removes values if they are older than some time-to-live. I have only proved it correct, not tried it ;) [As the author of this code, I dedicate it to the public domain https://creativecommons.org/publicdomain/zero/1.0]
package com.example;
import static java.util.Collections.*;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.TimeUnit;
/**
* A hash map that expires and removes items if they are older than a given
* time-to-live.
* <p>
* The expiry is a passive process, items aren't removed until they are
* retrieved and deemed to be expired by {@link #get(Object)}. Certain operations
* do cause the cache to clear all expired values in order to provide an accurate
* result (keySet, entrySet, values, size) and these operations are therefore O(n).
*/
public class TtlHashMap<K, V> implements Map<K, V> {
private final HashMap<K, V> store = new HashMap<>();
private final HashMap<K, Long> timestamps = new HashMap<>();
private final long ttl;
public TtlHashMap(TimeUnit ttlUnit, long ttlValue) {
this.ttl = ttlUnit.toNanos(ttlValue);
}
@Override
public V get(Object key) {
V value = this.store.get(key);
if (value != null && expired(key, value)) {
store.remove(key);
timestamps.remove(key);
return null;
} else {
return value;
}
}
private boolean expired(Object key, V value) {
return (System.nanoTime() - timestamps.get(key)) > this.ttl;
}
@Override
public V put(K key, V value) {
timestamps.put(key, System.nanoTime());
return store.put(key, value);
}
@Override
public int size() {
clearExpired();
return store.size();
}
@Override
public boolean isEmpty() {
return store.isEmpty();
}
@Override
public boolean containsKey(Object key) {
return store.containsKey(key);
}
@Override
public boolean containsValue(Object value) {
return store.containsValue(value);
}
@Override
public V remove(Object key) {
timestamps.remove(key);
return store.remove(key);
}
@Override
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
this.put(e.getKey(), e.getValue());
}
}
@Override
public void clear() {
timestamps.clear();
store.clear();
}
@Override
public Set<K> keySet() {
clearExpired();
return unmodifiableSet(store.keySet());
}
@Override
public Collection<V> values() {
clearExpired();
return unmodifiableCollection(store.values());
}
@Override
public Set<java.util.Map.Entry<K, V>> entrySet() {
clearExpired();
return unmodifiableSet(store.entrySet());
}
private void clearExpired() {
Iterator<K> iterator = new ArrayList<K>(store.keySet()).iterator();
while (iterator.hasNext()) {
this.get(iterator.next());
}
}
}
@joelittlejohn
Copy link
Author

@oraclebox Nice 👍

@lyrl
Copy link

lyrl commented Mar 14, 2021

😄 good jb

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment