And if you want a full Map implementation, just have FiveMinuteMap delegate other calls to the backing map as well.
You need proper synchronization, which is what the ConcurrentHashMap will do for you. If you need a TreeMap as backing mechanism you need to take care of synchronization (also while iterating) yourself.
I'd make one improvement over that class though - make the interval instance fields. That allows you to use the same class for 10 minutes, 1 hour, etc:
Rob, notice that V get(K key) is not implementing the get method from interface Map - in that interface, the key is unfortunately of type Object (because of backward compatibility reasons with pre-generics Java). If you'd want to implement the Map interface, it would have to be: