В чем разница между HashMap, LinkedHashMap и TreeMap

HashMap — неупорядоченная реализация Map, основанная на хеш-таблице. Обеспечивает O(1) для put() и get(), но порядок элементов не гарантируется.

LinkedHashMap — сохраняет порядок вставки (или порядок доступа, если accessOrder=true). Наследует HashMap, добавляя двусвязный список. Производительность чуть ниже HashMap.

TreeMap — реализация на основе красно-черного дерева. Элементы сортируются по ключам (естественный порядок или Comparator). O(log n) для операций.

Пример:

Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("z", 3);
hashMap.put("a", 1);  // Порядок: может быть {a=1, z=3} или {z=3, a=1}

Map<String, Integer> linkedMap = new LinkedHashMap<>();
linkedMap.put("z", 3);
linkedMap.put("a", 1);  // Порядок: {z=3, a=1}

Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("z", 3);
treeMap.put("a", 1);  // Порядок: {a=1, z=3} (сортировка по ключу)