⌨️ Внутреннее устройство HashSet

Тут разработчики не стали мудрствовать лукаво и просто использовали экземпляр HashMap внутри HashSet. Каждый элемент HashSet хранится как ключ в этой хэш-таблице, а значение для каждого ключа установлено в фиксированное значение PRESENT, что является специальным объектом (обычно new Object()).

При добавлении элемента, у него вычисляется хэш-код, определяется соответствующий бакет, и элемент добавляется в этот бакет, если он еще не присутствует (проверяется с помощью метода equals()).

При удалении вычисляется хэш-код элемента, определяется бакет, и элемент удаляется, если он присутствует в этом бакете.

Упрощённый код класса HashSet:

public class HashSet<E> implements Set<E>, Cloneable, java.io.Serializable {
    // Внутренний экземпляр HashMap
    private transient HashMap<E, Object> map;

    // Специальный константный объект, используемый в качестве значения для всех ключей
    private static final Object PRESENT = new Object();

    public HashSet() {
        map = new HashMap<>();
    }

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }

    public boolean remove(Object o) {
        return map.remove(o) == null;
    }

    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    // Другие методы...
}

#java #hashset #hashmap

⌨️ В чём разница между TreeSet и HashSet?

TreeSet и HashSet — это два класса, реализующих интерфейс Set, но они имеют разные внутренние механизмы и свойства.

Структура данных

✔️ HashSet использует хеш-таблицу для хранения элементов. Это позволяет быстро добавлять, удалять и искать элементы, не обеспечивая никакого порядка их хранения.

✔️ TreeSet использует красно-черное дерево (Red-Black Tree), что позволяет хранить элементы в отсортированном порядке (естественном порядке элементов или порядке, определённом компаратором).


Порядок элементов

✔️ HashSet не гарантирует какого-либо порядка элементов. Порядок может быть случайным, и он не сохраняется при добавлении/удалении элементов.

✔️ TreeSet хранит элементы в отсортированном порядке. Если элементы реализуют интерфейс Comparable, то сортировка будет основана на их естественном порядке (например, для чисел — по возрастанию). Также можно задать пользовательский порядок с помощью объекта Comparator.


Скорость операций

✔️ HashSet обеспечивает O(1) для операций добавления, удаления и поиска (в среднем, если хеш-функция работает эффективно и коллизий мало).

✔️ TreeSet обеспечивает O(log n) для операций добавления, удаления и поиска из-за использования сбалансированного дерева.


Поддержка дополнительных операций

✔️ HashSet не поддерживает дополнительные методы для работы с диапазонами или порядком элементов.

✔️ TreeSet предоставляет такие методы, как subSet(), headSet(), tailSet(), которые позволяют работать с диапазонами элементов в отсортированном множестве.


Null-значения

✔️ HashSet может хранить одно null значение.

✔️ TreeSet не позволяет хранить null значения, так как при добавлении null неясно, как его сравнивать с другими элементами.


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

✔️ Используйте HashSet, если вам не важен порядок элементов и вам нужна максимальная производительность.

✔️ Используйте TreeSet, если нужно поддерживать элементы в отсортированном порядке.

#java #HashSet #TreeSet

🔍 Разница между TreeSet и HashSet

Оба класса реализуют Set, но у них разные свойства:

• HashSet – хранит элементы в случайном порядке, обеспечивает быстрые операции add() и remove().
• TreeSet – хранит элементы в отсортированном порядке, но работает медленнее.

✔️ Пример:

Set<Integer> hashSet = new HashSet<>(Set.of(3, 1, 2)); // [3, 1, 2] (порядок может быть разным)
Set<Integer> treeSet = new TreeSet<>(Set.of(3, 1, 2)); // [1, 2, 3] (отсортировано)

💡 Совет: Используйте HashSet для быстрого доступа и TreeSet, если важен порядок элементов.

#java #treeset #hashset #collections