HashMap vs TreeMap: отличия, сложность операций, когда использовать?

HashMap vs TreeMap:

• HashMap:

  • Основан на хеш-таблице.
  • Операции вставки, удаления, поиска — в среднем O(1).
  • Не гарантирует порядок элементов.
  • Позволяет использовать null в качестве ключа.

• TreeMap:

  • Основан на красно-чёрном дереве (самобалансирующееся дерево).
  • Операции вставки, удаления, поиска — O(log n).
  • Хранит элементы в отсортированном порядке по ключу.
  • Не позволяет null в качестве ключа (выбросит NullPointerException).

Когда использовать:

• Если важна быстрая произвольная выборка и порядок не важен — HashMap.
• Если нужен отсортированный порядок ключей, или требуется навигация по диапазонам (например, subMap, headMap) — TreeMap.

Пример использования TreeMap для хранения итерируемого отсортированного словаря:

TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "three");
treeMap.put(1, "one");
treeMap.put(2, "two");

for (Map.Entry<Integer, String> entry : treeMap.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}
// Вывод будет в порядке ключей: 1, 2, 3