TimeMap.java

import java.util.*;

public class TimeMap<TKey extends Comparable<TKey>, TValue> {
    public static void main(String[] args) {
        TimeMap<Integer, Integer> map = new TimeMap<>();

        map.set(1, 1, 0);
        map.set(1, 2, 2);
        map.remove(1, 3);
        map.set(2, 100, 0);

        System.out.println("map.get(1, -1) = " + map.get(1, -1));     // null
        System.out.println("map.get(1,  0) = " + map.get(1,  0));	    // 1
        System.out.println("map.get(1,  1) = " + map.get(1,  1));	    // 1
        System.out.println("map.get(1,  2) = " + map.get(1,  2));	    // 2
        System.out.println("map.get(1,  3) = " + map.get(1,  3));	    // null
    }

    private class TimeKey {
        private final TKey key;
        private final long validFrom;

        TimeKey(TKey key, long validFrom) {
            this.key = key;
            this.validFrom = validFrom;
        }
    }

    private final NavigableMap<TimeKey, TValue> tree = new TreeMap<>(
            Comparator.<TimeKey, TKey>comparing(t -> t.key).
                    thenComparing(t -> t.validFrom));

    public void set(TKey key, TValue value, long time) {
        tree.put(new TimeKey(key, time), value);
    }

    public TValue get(TKey key, long time) {
        TimeKey lookup = new TimeKey(key, time);
        Map.Entry<TimeKey, TValue> entry = tree.floorEntry(lookup);

        // Only return value if we found the key
        return entry != null && Objects.equals(key, entry.getKey().key) ?
                entry.getValue() : null;
    }

    public void remove(TKey key, long time) {
        set(key, null, time);
    }
}