There are two aspects to this question that I felt were too closely related to ask as separate questions.

1. Why doesn't SortedMap implement Iterable<Map.Entry<K,V>>?

If you need to perform an action on every key-value pair in a map, iterating over the entrySet() seems like the way to go. So why not provide a direct iterator() method on SortedMap? Unless you are worried about iteration order being inconsistent in a HashMap. Which leads me to:

2. Does implementing Iterable imply a stable ordering?

Iterating over an ordered collection (List, SortedMap, SortedSet) is a great way to reliably implement equals() (see Note 1) and do other things that have to produce the same result every time. Iterating over an unsorted set or map could yield different ordering if you call it multiple times, so is unsuitable for these purposes. Especially if you are comparing HashSets or HashMaps - two of them could contain the same objects, but the order of their iterators would be different.

I guess there are 2 aspects to those questions:

1. What are the historical reasons for these design decisions?

2. If doing it again today, are there correct answers to these questions? Maybe OrderedIterable should extend Iterable to guarantee order?

Notes:

1. I had originally suggested that you needed a reliable ordering to implement hashCode(), but if you sum all the hashcodes, it turns out that you don't need a reliable ordering if you use addition because A. addition is associative, so that a + b = b + a and B. even with overflow, addition is still associative so that a + Integer.MAX_VALUE = Integer.MAX_VALUE + a. This would be true of any associative hashing algorithm. You do still need a reliable ordering to implement equals() so that you can compare the first item of one to the first item of the other, etc.

P.S.

This question is about the interfaces Iterable, Set, SortedSet, Map, and SortedMap. It's fine to bring up other interfaces as examples, but I do not think the Collection interface is relevant to this question. It's quirky and has the potential to be a distraction.