⌨️ Внутреннее устройство 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 Rocks | #java #hashset #hashmap