В чем разница между SortedMap и LinkedHashMap

SortedMap (например, TreeMap) автоматически сортирует элементы по ключам на основе их естественного порядка или компаратора. Порядок итерации гарантированно соответствует сортировке.

LinkedHashMap сохраняет порядок вставки элементов (или порядок доступа, если используется режим accessOrder). Сортировки по ключам нет.

Пример:

// SortedMap (TreeMap)
SortedMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "C");
treeMap.put(1, "A");
// {1=A, 3=C} - автоматическая сортировка

// LinkedHashMap
LinkedHashMap<Integer, String> linkedMap = new LinkedHashMap<>();
linkedMap.put(3, "C");
linkedMap.put(1, "A");
// {3=C, 1=A} - порядок вставки сохранён

Выбор зависит от задачи: нужна сортировка - SortedMap, важен порядок добавления - LinkedHashMap.