“Programming to an interface” does not mean “use the most abstracted version possible”. In that case everyone would just use Object.

What it means is that you should define your program against the lowest possible abstraction without losing functionality. If you require a TreeMap then you will need to define a contract using a TreeMap.

If you still want to use an interface you could use

NavigableMap <X, Y> map = new TreeMap<X, Y>();

it is not necessary to always use an interface but there is often a point where you want to take a more general view that allows you to replace the implementation (perhaps for testing) and this is easy if all references to the object are abstracted as the interface type.

The point behind coding to an interface rather than an implementation is to avoid the leaking of implementation details which would otherwise constrain your program.

Consider the situation where the original version of your code used a HashMap and exposed that.

private HashMap foo = new HashMap();
public HashMap getFoo() { return foo; }  // This is bad, don't do this.

This means that any change to getFoo() is a breaking API change and would make people using it unhappy. If all that you are guaranteeing is that foo is a Map, you should return that instead.

private Map foo = new HashMap();
public Map getFoo() { return foo; }

This gives you the flexibility to change how things work inside your code. You realize that foo actually needs to be a Map that returns back things in a particular order.

private NavigableMap foo = new TreeMap();
public Map getFoo() { return foo; }
private void doBar() { ... foo.lastEntry(); ... }

And that doesn’t break anything for the rest of the code.

You can later strengthen the contract the class gives without breaking anything either.

private NavigableMap foo = new TreeMap();
public NavigableMap getFoo() { return foo; }
private void doBar() { ... foo.lastEntry(); ... }

This delves into the Liskov substitution principle

Substitutability is a principle in object-oriented programming. It states that, in a computer program, if S is a subtype of T, then objects of type T may be replaced with objects of type S (i.e., objects of type S may substitute objects of type T) without altering any of the desirable properties of that program (correctness, task performed, etc.).

Since NavigableMap is a subtype of Map, this substitution can be done without altering the program.

Exposing the implementation types makes it difficult to change how the program works internally when a change needs to be made. This is a painful process and many times creates ugly workarounds that only serve to inflict more pain on the coder later (I’m looking at you previous coder who kept shuffling data between a LinkedHashMap and a TreeMap for some reason – trust me, whenever I see your name in svn blame I worry).

You would still want to avoid leaking implementation types. For example, you may wish to implement ConcurrentSkipListMap instead because of some performance characteristics or you just like the java.util.concurrent.ConcurrentSkipListMap rather than java.util.TreeMap in the import statements or whatever.

Agreeing with the other answers that you should use the most generic class (or interface) of which you actually need something, in this case TreeMap (or like someone suggested NavigableMap). But I would like to add that this is most certainly better than casting to it everywhere, which would be a much bigger smell in any case. See https://stackoverflow.com/questions/4167304/why-should-casting-be-avoided for some reasons.

It’s about communicating your intent of how the object should be used. For example, if your method expects a Map object with a predictable iteration order:

private Map<String, String> processOrderedMap(LinkedHashMap<String, String> input) {
    // ...
}

Then, if you absolutely need to tell callers of the above method that it too returns a Map object with a predictable iteration order, because there is such an expectation for some reason:

private LinkedHashMap<String,String> processOrderedMap(LinkedHashMap<String,String> input) {
    // ...
}

Of course, callers may still treat the return object as a Map as such, but that’s beyond the scope of your method:

private Map<String, String> output = processOrderedMap(input);

Taking a step back

The general advice of coding to an interface is (generally) applicable, because usually it’s the interface that provides the guarantee what the object should be able to perform, aka the contract. Many beginners start with HashMap<K, V> map = new HashMap<>() and they are advised to declare that as a Map, because a HashMap doesn’t offer anything more than what a Map is supposed to do. From this, they will then be able to understand (hopefully) why their methods should take in a Map instead of a HashMap, and this lets them realize the inheritance feature in OOP.

To quote just one line from the Wikipedia entry of everyone’s favorite principle related to this topic:

It is a semantic rather than merely syntactic relation because it intends to guarantee semantic interoperability of types in a hierarchy…

In other words, using a Map declaration isn’t because it makes sense ‘syntactically’, but rather invocations on the object should only care that it is a type of Map.

Cleaner code

I find that this allows me to write cleaner code at times too, especially when it comes to unit testing. Creating a HashMap with a single read-only test entry takes more than a line (excluding the use of double-brace initialization), when I can easily replace that with Collections.singletonMap().