It looks like the closet the Collection framework lets you get to this would be writing a custom interator that used the
headMap method, but the performance of that wouldn't be near as good as it would be if SortedMap has a getSortedEntrySet() method and SortedSet returned a ListIterator instead of just an Iterator.
If linear-time forward and reverse iteration for a large Map are important to you, look for an open source Red-Black Tree implementation on the web. Even if it doesn't already support reverse interation, you shouldn't have any trouble figuring out how to implement it.