В Java HashSet и TreeSet — это две реализации интерфейса Set, но работают они принципиально по-разному. Главное их отличие — структура хранения данных, порядок элементов, время доступа и требования к элементам. Оба набора обеспечивают уникальность элементов, но реализованы на базе разных структур данных: HashSet — через хеш-таблицу, а TreeSet — через сбалансированное бинарное дерево поиска (конкретно, красно-чёрное дерево).

🔹 HashSet

🔧 Внутреннее устройство

HashSet реализован на основе HashMap, где каждый добавляемый элемент хранится как ключ, а значением является константа-заглушка PRESENT. Фактически:

private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();

Когда вы вызываете hashSet.add(e), он вызывает map.put(e, PRESENT). Поскольку HashMap использует хеш-функцию, скорость операций зависит от качества хеширования и размеров таблицы.

⚙️ Как хранятся данные

• Данные хранятся в массиве бакетов (Node<K,V>[] table) внутри HashMap.

• Каждый бакет — это либо связанный список, либо красно-чёрное дерево (с Java 8), если число коллизий в бакете превышает 8.

• Элемент добавляется по индексу hash(key) % capacity, и если в этом месте уже есть другие элементы с таким же хешем, происходит линейное сравнение по equals().

📈 Время выполнения операций

Худший случай возможен при плохом хешировании (много коллизий).

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

• Не сохраняет порядок вставки.

• Можно использовать любые объекты, если они правильно реализуют hashCode() и equals().

• Быстрее TreeSet при больших объёмах данных (в среднем).

🔸 TreeSet

🔧 Внутреннее устройство

TreeSet построен на базе TreeMap, а точнее — красно-чёрного дерева, что является видом сбалансированного бинарного дерева поиска (BBST).

private transient NavigableMap<E,Object> m;

Каждый элемент добавляется в TreeMap как ключ, а значением снова выступает PRESENT. Элементы упорядочены по естественному порядку (через Comparable) или с использованием предоставленного Comparator.

⚙️ Как хранятся данные

• Данные хранятся в красно-чёрном дереве, где каждый узел — это пара (ключ, значение).

• Все элементы хранятся в отсортированном порядке.

• Дерево автоматически балансируется после вставки/удаления, обеспечивая логарифмическое время доступа.

📈 Время выполнения операций

Хуже, чем у HashSet, но стабильнее.

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

• Элементы всегда упорядочены.

• Использует либо Comparable, либо Comparator.

• Не допускает null-элементов (в отличие от HashSet, который допускает один null).

• Может использовать методы, специфичные для NavigableSet и SortedSet, например: first(), last(), ceiling(), floor(), subSet(), headSet(), tailSet().

⚖️ Сравнение HashSet и TreeSet

🧠 Пример

Set&lt;String&gt; hashSet = new HashSet<>();
hashSet.add("banana");
hashSet.add("apple");
hashSet.add("cherry");
System.out.println(hashSet); // Порядок непредсказуем
Set&lt;String&gt; treeSet = new TreeSet<>();
treeSet.add("banana");
treeSet.add("apple");
treeSet.add("cherry");
System.out.println(treeSet); // \[apple, banana, cherry\]

🧪 Влияние реализации на поведение

Сравнение по equals() vs compareTo()

• HashSet определяет уникальность по equals() и hashCode().

• TreeSet определяет уникальность по compareTo() или Comparator.compare():

  • Если compareTo() возвращает 0, элемент считается уже существующим — даже если equals() вернёт false.

  • Это может привести к ситуации, когда TreeSet "поглотит" элемент, несмотря на то, что по equals это другой объект.

Пример:

class Animal {
String name;
Animal(String name) { this.name = name; }
public boolean equals(Object o) { return false; } // неправильная реализация
public int hashCode() { return 1; }
public String toString() { return name; }
}
Set&lt;Animal&gt; hs = new HashSet<>();
hs.add(new Animal("Cat"));
hs.add(new Animal("Cat"));
System.out.println(hs.size()); // 2 — equals всегда false
Set&lt;Animal&gt; ts = new TreeSet&lt;>(Comparator.comparing(a -&gt; a.name));
ts.add(new Animal("Cat"));
ts.add(new Animal("Cat"));
System.out.println(ts.size()); // 1 — compare() возвращает 0, элемент считается дубликатом

📚 Использование на практике

• Используйте HashSet, если:

  • Вам не нужен порядок элементов.

  • Важна скорость доступа, добавления и удаления.

  • Вы работаете с большими объёмами данных.

• Используйте TreeSet, если:

  • Важен сортированный порядок.

  • Нужно извлекать минимальные/максимальные значения.

  • Требуется работа с подмножествами (subSet, headSet, tailSet).

  • Вы хотите гарантированную O(log n) сложность операций независимо от хеш-функции.

💡 Особенности Java 8+

• HashMap (и соответственно HashSet) используют балансированные деревья (TreeNodes) внутри бакетов, если число элементов в одном бакете превышает 8 (и размер таблицы ≥ 64). Это делает операции более стабильными в случае плохого хеширования.

• TreeSet автоматически обеспечивает сортировку — нет необходимости вызывать Collections.sort().

🧭 Заключение по внутреннему хранению

• HashSet: использует хеш-таблицу, ключи распределяются по массиву бакетов с возможными коллизиями, управляемыми списками или деревьями.

• TreeSet: использует красно-чёрное дерево, поддерживающее сортировку и логарифмическое время операций, где каждый элемент — это узел дерева с указателями на потомков и родителя, с балансировкой после каждой вставки/удаления.