The rule in programming is to use the most general interface possible. But the difference between Map and SortedMap is more subtle.

  • They compile to the same bytecode [I think]
  • No additional safety is provided since the compiler can't tell any of the differences between the two
  • SortedMap does offer an extra non-compiler-checked post condition, namely that the iterator is sorted

I would prefer code to write

SortedMap<K, V> m = new TreeMap<>();

if the sorted-ness is used. But I'm not sure if this rule only makes sense when there's compiler checks.

I'm hoping for a somewhat rigorous (e.g. type-theoretical) answer, but since this pertains to a real code review I'm doing right now, how this applies in practice is definitely important. I've yet to find an effective example of why one matters, besides a readability bump that circularly depends on programmers following this theory.

  • 1
    The rule in programming is to use the most general interface possible -- [citation-needed] – Robert Harvey Feb 24 '15 at 1:44
  • 1
    You're expecting way too much from the type system. No matter how much you want to believe that types rigourously define behavior, it comes down to implementation by an ordinary human. In the case of Java interfaces, there's no pretense; the interface describes a contract, with luck that contract doesn't have too many corner cases, hopefully the people who implement classes based on that interface follow the contract without bugs, and the consumers of that interface use it in its intended manner. – kdgregory Feb 24 '15 at 11:43
  • 1
    It's not at all weird that some property of some type is not statically verifiable automagically. That's pretty much the general case. There's no guarantee that any of the methods you call actually terminates, for example. – Doval Feb 24 '15 at 13:27
  • 1
    @Doval I still don't feel that's relevant. The type system only can't protect against this because at some point a programmer has to write a valid object and it would only be possible to validate this by using an abstract class which checks instead of an interface. That would be the strictest thing to do, it's just not worth the tradeoff. But just because the type system can't do it doesn't mean you should jump for joy that you can now write bad code. The question is: is this bad code? and saying the type system doesn't answer it, IMO even though it "wants" to, doesn't answer the question. – djechlin Feb 24 '15 at 13:36
  • 2
    @djechlin It's not clear to me what you're asking. Your question title and the question body are at odds with each other. If you just want to know when to use a SortedMap, the answer is obvious: when you need the map to be sorted. But you seem dissatisfied with that, and reading between the lines it seems you're asking if there's value in relying on interfaces that have specifications that can't be statically enforced, even though any non-trivial program implicitly relies on dozens of such interfaces. It would be nice if you edited the question to really reflect what you want to know. – Doval Feb 24 '15 at 14:19

You use it when you want to guarantee that you are getting sorted data in a parameter, or when you want to assure the consumer of your method that you are providing sorted data.


If you need your data to be sorted, ask for it to be sorted by asking for the interface that matches what you need. It is likely less expensive for the method sending you the data to give it to you sorted (they get it from a database and can trivially order it, but instead tossed it in a HashMap because thats what everyone uses) than it is for you to take the Map and then add it to a SortedMap.

If you need it to be sorted, ask for it to be sorted.

Return values

This one is a bit more controversial... there are differing schools of thought here.

If you are producing sorted data by the nature of your method and don't have a reason not to, return back the interface that lets the consumers of your data work with it in the most ways without giving them a concrete implementation (that locks you down).

That 'that locks you down' is part of the controversial bit. Some people will argue that you should return the least constraining (most general) interface when possible (Map rather than SortedMap and Collection rather than Set or List).

I'd go with return the most useful thing for the consumers.

I will put the caveat here that if this is something that will always be sorted, its one thing... if someone might want to subclass it later and not have it be sorted... thats another story. So you need to consider this as part of designing for extension. If it isn't going to be extended ever you get one answer from this deliberation... if it may be extended, there's another possible answer.

why is this bit above a mess and people say things about it in code review?

Well, Liskov substitution principle points out that this would make it harder to subclass later. Method parameters cannot be strengthened by a subtype and return values cannot be relaxed.

By returning a SortedMap one cannot make a later subclass of the class return a weaker type. Furthermore, if you decide to return a weaker type later for some reason it makes it a major refactoring (changing all of the SortedMaps out there to Maps and possibly changing the calls that make use of that interface into code that has to deal with the weaker type).

Your internals

It really doesn't matter what you are doing inside your own code. Use a sorted map whenever you've got sorted data and want it in a sorted order. Especially if you are doing put calls on it at various times and want it to remain in sorted order.

Now, you might be tempted to use a LinkedHashMap instead if you get all the sorted data in one go, insert it in sorted order, and then only do remove calls against it if you do any modifications. It's not wrong, and it has some advantages (O(1) lookups rather than O(log n) lookups). But, its rather inflexible only providing the get and put and none of the other fun method calls that SortedMap can give you.

Btw, NavigableMap

Actually, SortedMap doesn't give you that much more over Map. But there is something else...

SortedMap has been replaced by NavigableMap since Java 1.6 (the two standard classes that implement SortedMap also implement NavigableMap). NavigableMap has all sorts of fun method calls that are often quite useful.

  • It's an internal case which is why it's so hard to point to a practical matter. I forgot what LSP is called so that's really helpful. – djechlin Feb 24 '15 at 2:47
  • @djechlin Internal development poses its own challenges with the messy refactoring if you need to relax the return type rather than just releasing a 2.0 version that has a breaking API change (thats 'easy' to do). So, thats the practical reason not to, but on the other hand if you need it, or want to be reminded of its functionality as a sorted (or navigable) structure, its useful to return back that so you get the 'foo. control-space, ohh ceilingEntry thats would be useful here rather than coding it myself...' – user40980 Feb 24 '15 at 2:55
  • Oh, I mean it's a private member variable. It's hard to come up with a plausible thought experiment where it matters, especially given unit test coverage on the sortedness. – djechlin Feb 24 '15 at 3:02
  • @djechlin ahh, so even more internal then. Well, use the method that makes it the most useful (NavigableMap) if it is to be sorted at all. The only thing inspections that fuss about the types of private fields are ones that point out you are using the concrete type when an interface exists. – user40980 Feb 24 '15 at 3:04
  • Re: Return values, the most flexible approach is to let the caller provide the collection for you to fill. Any choice you make will be wrong for someone, and subclassing should generally be avoided. It's also a lot easier on the caller to pass you an empty collection than to subclass your class just to change the collection you decided to instantiate. – Doval Feb 24 '15 at 17:38

While it is true that in programming it is a good idea to always

"use the most general interface possible"

it is even more true that

"everything should be as simple as possible --but not simpler".

So, if your code only needs to work with a Map, then your code should be given a Map and nothing more specific than that. This way, your code will work when either a Map or a SortedMap is passed to it, and the code which uses your code will be able to pass it whichever best suits its own needs.

However, if your code needs to work with a SortedMap, then you cannot somehow work around that and continue using a Map under the false pretense of keeping things simple; your code will, of course, need to be given a SortedMap. This will happen if your code needs to make use of any methods which are specific to SortedMap (do not exist in Map) i.e. comparator(), subMap(), headMap(), tailMap(), firstKey(), and lastKey().

The above was fairly self-explanatory, so I suspect that the reason why you are asking the question is because you have misunderstood what SortedMap is. So, here are a few notes about your question:

They compile to the same bytecode [I think]

SortedMap is an interface without any default methods, it does not really compile into bytecode. The .class file of that interface contains nothing but function declarations. Now, some of the methods declared by SortedMap are also declared by Map, and the reason why these declarations were duplicated in SortedMap was probably to add new documentation to them, but many methods of SortedMap do not exist in Map.

(Useful reading: What is the difference between declaration and definition in Java?)

No additional safety is provided since the compiler can't tell any of the differences between the two

Huh? This does not make any sense. I am not sure what you are thinking, but whatever it is, it is probably wrong.

SortedMap does offer an extra non-compiler-checked post condition, namely that the iterator is sorted

SortedMap begins with a doc comment which is about 4 kilobytes long, explaining what it is and how it differs from Map. I am not sure it is a good idea to summarize this as "does offer an extra non-compiler-checked post condition". Perhaps you should read the documentation.

  • Your first example is a case of "Use the most general type/interface possible": Map is more general than SortedMap; hence, if you just need a Map, use a Map. No need to invoke the second principle about simplicity :) – Andres F. Feb 24 '15 at 13:53
  • @AndresF. the principle about simplicity needs to be invoked to show that if you need a SortedMap, then you have to use a SortedMap, there is no way around it. It is the "--but not simpler" clause that matters. I will amend the answer to emphasize that. – Mike Nakis Feb 24 '15 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.