Устройство HashMap / HashSet / TreeMap

Устройство HashMap / HashSet / TreeMap

Устройство HashMap в Java

HashMap — это реализация интерфейса Map на основе хеш-таблицы, которая хранит пары «ключ-значение» и обеспечивает среднюю сложность операций O(1) для put(), get() и remove().

Внутренняя структура

• Массив бакетов(корзин)
  • HashMap использует массив Node<K,V>[] table, где каждый элемент (бакет) — это:
  • Связный список (до Java 8).
  • Красно-чёрное дерево (с Java 8, если список становится слишком длинным).
• Узел (Node) Каждый элемент хранится в виде узла:

  static class Node<K,V> {
    final int hash;    // Хеш ключа
    final K key;       // Ключ
    V value;           // Значение
    Node<K,V> next;    // Ссылка на следующий узел (для коллизий)
  }
  

Принцип работы

• Добавление элемента (put(key, value))
  • Вычисление хеша ключа
  • Сначала вызывается key.hashCode()
  • Затем применяется дополнительное хеширование для уменьшения коллизий

      static final int hash(Object key) {
      int h;
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
      }
    

  • Определение индекса бакета
    • Индекс = hash & (table.length - 1)
    • Например, для table.length = 16: hash % 16 (но работает быстрее через битовые операции)
  • Обработка коллизий
    • Если бакет пуст — создаётся новый узел
    • Если в бакете уже есть узлы:
      • Ключи совпадают (по equals()) — значение перезаписывается
      • Ключи разные — узел добавляется в конец списка (или в дерево)
• Получение значения (get(key))
  • Вычисляется хеш ключа и индекс бакета
  • Если в бакете один узел — возвращается его значение
  • Если в бакете список/дерево — ищется узел с совпадающим ключом (через equals())

---

Разрешение коллизий

• Связные списки (до Java 8)
  • При коллизии узлы связываются в односвязный список
  • В худшем случае (все ключи попали в один бакет) сложность операций O(n)
• Деревья (с Java 8)
  • Если список в бакете достигает длины 8, он преобразуется в красно-чёрное дерево (сложность O(log n))
  • Если размер дерева уменьшается до 6, оно снова превращается в список
• Почему именно 8 и 6?
  • Статистика коллизий:
    • Вероятность того, что в один бакет попадёт 8 элементов, крайне мала (менее 0.000006% при хорошем хешировании).
    • Если это происходит — вероятно, хеш-функция работает плохо, и дерево (O(log n)) эффективнее списка (O(n)).
  • Компромисс между памятью и скоростью:
    • Дерево требует больше памяти, но обеспечивает гарантированную производительность в худших случаях.

---

Динамическое расширение (Rehashing)

• Параметры роста
  • Начальная ёмкость (capacity): 16 (по умолчанию).
  • Коэффициент загрузки (loadFactor): 0.75 (по умолчанию).
  • Например, при capacity = 16 расширение произойдёт при 16 * 0.75 = 12 элементах.
• Процесс расширения
  • Создаётся новый массив в 2 раза больше (например, 16 → 32).
  • Все элементы пересчитываются и перераспределяются по новым бакетам.
  • Индекс в новом массиве: hash & (newCapacity - 1). Зачем loadFactor = 0.75?
  • Компромисс между памятью (меньше расширений) и производительностью (меньше коллизий).

---

Важные особенности

• Порядок элементов не гарантируется (может меняться при rehashing).
• Допускает один null-ключ и множество null-значений.
• Не потокобезопасна (для многопоточности используйте ConcurrentHashMap).

---

Итог

• Бакеты — массив, где каждый элемент может быть списком или деревом.
• Коллизии — разрешаются через списки (O(n)) или деревья (O(log n)).
• loadFactor — определяет, когда HashMap увеличится (по умолчанию 0.75).
• Rehashing — удвоение размера при достижении порога.

Коллизии в HashMap, когда превращается в красно-чёрное дерево?

В HashMap (начиная с Java 8) при возникновении коллизий используется два подхода для их разрешения:

1. Связный список (для малого числа коллизий).
2. Красно-чёрное дерево (для избежания деградации производительности при большом числе коллизий).

Когда HashMap преобразует список в дерево?

1. При достижении порога в 8 элементов в одном бакете
   • Если в одном бакете накапливается 8 или более узлов (Node), HashMap автоматически преобразует связный список в красно-чёрное дерево (TreeNode).
   • Это происходит только при выполнении дополнительного условия:

      if (binCount >= TREEIFY_THRESHOLD - 1) // TREEIFY_THRESHOLD = 8
      treeifyBin(tab, hash);
     

   • Но! Дерево создаётся только если общий размер table ≥ MIN_TREEIFY_CAPACITY (по умолчанию 64).
     • Если table.length < 64, вместо преобразования в дерево HashMap просто увеличит размер таблицы (rehashing).
2. При удалении элементов дерево может снова стать списком
   • Если количество узлов в дереве уменьшается до 6 (UNTREEIFY_THRESHOLD = 6), оно преобразуется обратно в связный список.

Когда дерево не поможет?

• Если хеш-функция всегда возвращает одно значение (как в примере выше), все элементы попадут в один бакет, и дерево лишь смягчит проблему (O(log n) вместо O(n)).
• Решение:
  • Использовать ключи с хорошим hashCode().
  • Увеличить capacity HashMap.

---

Вывод

• → Список → Дерево: При 8+ элементах в бакете (и table.length ≥ 64).
• → Дерево → Список: При ≤6 элементах.
• Цель: Предотвратить деградацию производительности до O(n) при атаках коллизиями.

Можно ли класть null в HashMap / HashSet / TreeMap, какие ограничения?

HashMap

• Ключи: Допускается один null-ключ.
• При попытке добавить второй null-ключ, значение перезапишется.
• Значения: Можно хранить любое количество null-значений.
• null-ключ всегда попадает в бакет 0 (поскольку hashCode() для null равен 0).

HashSet

• Элементы: Может содержать один null-элемент, так как HashSet внутри использует HashMap (где элементы — это ключи).
• Повторный null игнорируется (как в HashMap).

TreeMap

• Ключи: Не допускает null-ключи (выбрасывает NullPointerException).
  • Причина: TreeMap использует сравнение ключей (через Comparable или Comparator), а null нельзя сравнивать.
• Значения: Можно хранить null-значения.

TreeSet

• Элементы: Не поддерживает null, так как внутри использует TreeMap
• Причина: Аналогично TreeMap — требует сравнения элементов.

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

• Если нужны null-значения:
  • Используйте HashMap или HashSet.
• Если нужна сортировка:
  • TreeMap/TreeSet не подойдут для null-ключей.
  • Альтернатива: ConcurrentSkipListMap (но тоже не поддерживает null).

---

Разница HashMap / TreeMap / LinkedHashMap (поиск, упорядоченность, сложность)

HashMap Особенности:

• Не гарантирует порядок элементов (может меняться при рехешировании).
• Разрешает один null-ключ и множество null-значений.
• Основана на хеш-таблице с бакетами (списки/деревья при коллизиях).

Сложность операций:

Операция	Средний случай	Худший случай
put()	O(1)	O(n) или O(log n)*
get()	O(1)	O(n) или O(log n)*
remove()	O(1)	O(n) или O(log n)*

• В Java 8 при коллизиях список превращается в дерево (O(log n)).

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

• Нужна максимальная скорость доступа.
• Порядок элементов не важен.

TreeMap

Особенности:

• Хранит ключи в отсортированном порядке (по умолчанию — натуральный порядок или Comparator).
• Не поддерживает null-ключи (т.к. требует сравнения).
• Основана на красно-чёрном дереве.

Сложность операций:

Операция	Сложность
put()	O(log n)
get()	O(log n)
remove()	O(log n)

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

• Нужен отсортированный порядок ключей.
• Требуются операции типа firstKey(), lastKey(), subMap().

LinkedHashMap

Особенности:

• Сохраняет порядок добавления элементов (или порядок доступа, если accessOrder=true).
• Разрешает один null-ключ и множество null-значений.
• Основана на хеш-таблице + двусвязный список для порядка.

Сложность операций:

Операция	Сложность
put()	O(1)
get()	O(1)
remove()	O(1)

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

• Нужен порядок добавления (например, LRU-кэш).
• Требуется предсказуемая итерация (как в ArrayList).

---

Вывод

• Если нужна скорость → HashMap.
• Если нужна сортировка → TreeMap.
• Если важен порядок добавления → LinkedHashMap.

Различия HashSet, LinkedHashSet, TreeSet (уникальность, порядок вставки/хранения)

HashSet

Особенности:

• Не гарантирует порядок элементов (может меняться при рехешировании).
• Основан на HashMap (элементы хранятся как ключи, значения — фиктивные).
• Разрешает один null-элемент.
• Сложность операций:
• add(), remove(), contains() — в среднем O(1) (в худшем случае — O(n) или O(log n) при коллизиях).

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

• Нужна максимальная скорость операций.
• Порядок элементов не важен.

LinkedHashSet

Особенности:

• Сохраняет порядок добавления элементов (итерация происходит в порядке вставки).
• Основан на LinkedHashMap (хеш-таблица + двусвязный список для порядка).
• Разрешает один null-элемент.
• Сложность операций:
• add(), remove(), contains() — O(1).

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

• Нужен предсказуемый порядок итерации (как в списке).
• Пример: LRU-кэш, история посещений.

TreeSet

Особенности:

• Хранит элементы в отсортированном порядке (по умолчанию — натуральный порядок или Comparator).
• Основан на TreeMap (красно-чёрное дерево).
• Не поддерживает null-элементы (требует сравнения).
• Сложность операций:
• add(), remove(), contains() — O(log n).

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

• Нужен отсортированный набор.
• Требуются операции типа first(), last(), subSet().

Сравнительная таблица

| Характеристика | HashSet | LinkedHashSet | TreeSet | | ——————— | ——————- | —————— | ——————– | | Уникальность | Да | Да | Да | | Порядок элементов | Не гарантирован | Порядок добавления | Сортировка | | Поддержка null | Да (один) | Да (один) | Нет | | Сложность операций | O(1) (в среднем) | O(1) | O(log n) | | Внутренняя реализация | HashMap | LinkedHashMap | TreeMap | | Использование | Универсальный выбор | Сохранение порядка | Сортированные данные |

---

Ключевые выводы

• Для скорости → HashSet.
• Для порядка вставки → LinkedHashSet.
• Для сортировки → TreeSet.

Пример выбора:

• Кэш URL-адресов → LinkedHashSet (чтобы помнить порядок посещения).
• Словарь уникальных слов → HashSet (если порядок не важен).
• Рейтинг игроков → TreeSet (автоматическая сортировка по очкам).

---

TreeMap и TreeSet: необходимость Comparable / Comparator

TreeMap и TreeSet в Java хранят элементы в отсортированном порядке, поэтому для их работы требуется механизм сравнения ключей (для TreeMap) или элементов (для TreeSet). Это можно обеспечить двумя способами:

1. Реализация интерфейса Comparable (естественный порядок).
2. Передача Comparator (кастомный порядок).

Если ни один из этих вариантов не используется, при добавлении элементов возникнет ClassCastException.

Использование Comparable (естественный порядок)

Класс ключей/элементов должен реализовывать интерфейс Comparable<T> и переопределять метод compareTo() Пример для TreeSet

  class Person implements Comparable<Person> {
      String name;
      int age;

      @Override
      public int compareTo(Person other) {
          return this.name.compareTo(other.name); // Сортировка по имени
      }
  }

  public class Main {
      public static void main(String[] args) {
          TreeSet<Person> set = new TreeSet<>();
          set.add(new Person("Alice", 25));
          set.add(new Person("Bob", 30));
          // Элементы автоматически сортируются по имени.
      }
  }

Пример для TreeMap

  TreeMap<Person, String> map = new TreeMap<>();
  map.put(new Person("Alice", 25), "Engineer");
  // Ключи сортируются по `compareTo()`.

Использование Comparator (кастомный порядок)

Если класс не реализует Comparable, или нужен особый порядок сортировки, можно передать Comparator в конструктор. Пример: сортировка по возрасту

  Comparator<Person> ageComparator = (p1, p2) -> Integer.compare(p1.age, p2.age);

  TreeSet<Person> set = new TreeSet<>(ageComparator);
  set.add(new Person("Alice", 25));
  set.add(new Person("Bob", 30));
  // Элементы сортируются по возрасту.

Пример: обратный порядок строк

  TreeMap<String, Integer> map = new TreeMap<>(Comparator.reverseOrder());
  map.put("Banana", 2);
  map.put("Apple", 1);
  // {"Banana"=2, "Apple"=1} (обратная сортировка).

Что будет, если не указать Comparable или Comparator?

При добавлении элемента, который не реализует Comparable и для которого не задан Comparator, возникнет ClassCastException:

  TreeSet<Person> set = new TreeSet<>(); // Ошибка, если Person не Comparable
  set.add(new Person("Alice", 25)); // ClassCastException

Важные нюансы

null-значения

• TreeMap и TreeSet не поддерживают null-ключи (но null-значения в TreeMap допустимы).
• Причина: сравнение null с другими элементами невозможно.

Согласованность equals() и compareTo()

• Если класс реализует Comparable, рекомендуется, чтобы compareTo() был согласован с equals():

  a.compareTo(b) == 0 ⇔ a.equals(b)
  

• Иначе поведение коллекций может быть некорректным (например, в TreeSet дубликаты определяются через compareTo(), а не equals()).

Производительность

• Операции add(), remove(), contains() в TreeSet/TreeMap работают за O(log n) (т.к. основаны на красно-чёрном дереве).

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

Ситуация	Способ сравнения
Класс имеет естественный порядок	Реализовать Comparable
Нужна кастомная сортировка	Передать Comparator
Нельзя изменить класс	Только Comparator
Требуется сортировка по нескольким полям	Comparator.comparing().thenComparing()

Comparator<Person> complexComparator = Comparator
    .comparing(Person::getAge)
    .thenComparing(Person::getName);

TreeSet<Person> set = new TreeSet<>(complexComparator);

Итог

• TreeMap/TreeSet требуют Comparable или Comparator для определения порядка элементов.
• Без них — ClassCastException.
• null-ключи запрещены.
• Для сложной сортировки используйте цепочки Comparator.