Что такое HashSet?

📚 Что такое HashSet в Java

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

🔍 Основные характеристики HashSet:

• Уникальность элементов: Не позволяет хранить дубликаты. При попытке добавить существующий элемент новый не добавляется.
• Отсутствие порядка: Элементы не упорядочены (но с Java 8 есть незначительные внутренние оптимизации).
• Разрешение null: Можно добавить один null.
• Несинхронизированность: Не потокобезопасен (для многопоточности используйте Collections.synchronizedSet() или ConcurrentHashMap).
• Высокая производительность: Операции add(), remove(), contains() работают за константное время при хорошей хэш-функции.

🏗️ Внутреннее устройство:

HashSet использует HashMap для хранения элементов, где:

• Ключи HashMap — это элементы HashSet
• Значения HashMap — это заглушка PRESENT (объект-константа)

// Упрощенное представление внутренней реализации
public class HashSet<E> {
    private transient HashMap<E, Object> map;
    private static final Object PRESENT = new Object();
    
    public boolean add(E e) {
        return map.put(e, PRESENT) == null; // Возвращает true, если элемент новый
    }
}

📝 Пример использования:

import java.util.HashSet;

public class HashSetExample {
    public static void main(String[] args) {
        HashSet<String> programmingLanguages = new HashSet<>();
        
        // Добавление элементов
        programmingLanguages.add("Java");
        programmingLanguages.add("Kotlin");
        programmingLanguages.add("Java"); // Не добавится — дубликат
        
        System.out.println(programmingLanguages); // [Java, Kotlin] (порядок может быть другим)
        
        // Проверка наличия элемента
        boolean hasKotlin = programmingLanguages.contains("Kotlin"); // true
        
        // Удаление элемента
        programmingLanguages.remove("Java");
        
        // Итерация по элементам
        for (String language : programmingLanguages) {
            System.out.println(language);
        }
    }
}

⚠️ Важные особенности:

1. Качество hashCode(): Для пользовательских классов обязательно корректно переопределять hashCode() и equals(). Плохая хэш-функция приводит к вырождению в связанный список и падению производительности до O(n).

public class Person {
    private String name;
    private int age;
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age); // Правильная реализация
    }
    
    @Override
    public boolean equals(Object obj) {
        // Реализация equals
    }
}

1. Емкость и фактор загрузки: При создании можно задать начальную емкость и load factor (по умолчанию 0.75). При превышении емкость * load factor происходит рехэширование.

HashSet<Integer> numbers = new HashSet<>(100, 0.8f);

📊 Сравнение с другими коллекциями:

• vs ArrayList: HashSet быстрее для поиска (contains()), но не сохраняет порядок
• vs TreeSet: HashSet быстрее (O(1) vs O(log n)), но TreeSet хранит отсортированные элементы
• vs LinkedHashSet: LinkedHashSet сохраняет порядок вставки, но немного медленнее

🎯 Практическое применение в Android:

• Удаление дубликатов из списка
• Кэширование проверенных данных
• Хранение уникальных идентификаторов
• Проверка существования элемента без перебора коллекции

// Пример на Kotlin для Android
val uniqueUserIds = HashSet<String>().apply {
    addAll(apiResponse.users.map { it.id })
    // Автоматически удаляет дубликаты ID
}

Итог: HashSet — оптимальный выбор, когда нужна коллекция уникальных элементов с быстрым доступом, а порядок не важен. Критически важно обеспечивать хорошие hashCode() и equals() для пользовательских объектов, чтобы сохранять производительность на уровне O(1).