Как связаны HashMap и HashSet?

# Связь между HashMap и HashSet

Краткий ответ

HashSet — это обёртка над HashMap. HashSet использует HashMap внутри для хранения элементов, где ключом является сам элемент, а значением — фиксированный объект-заполнитель.

Архитектура HashSet

Посмотрим на исходный код HashSet в Java:

public class HashSet<E> extends AbstractSet<E> {
    private HashMap<E, Object> map;  // HashMap под капотом!
    
    // Фиксированный объект используется как значение для всех ключей
    private static final Object PRESENT = new Object();
    
    public HashSet() {
        map = new HashMap<>();
    }
    
    @Override
    public boolean add(E e) {
        // Добавляем элемент как ключ, PRESENT как значение
        return map.put(e, PRESENT) == null;
    }
    
    @Override
    public boolean contains(Object o) {
        // Проверяем наличие ключа в HashMap
        return map.containsKey(o);
    }
    
    @Override
    public boolean remove(Object o) {
        // Удаляем по ключу
        return map.remove(o) == PRESENT;
    }
    
    @Override
    public Iterator<E> iterator() {
        // Итератор по ключам HashMap
        return map.keySet().iterator();
    }
}

Визуальное представление

╔═══════════════════════════════════════════════════════╗
║ HashSet (интерфейс)                                   ║
║  add(E element)                                       ║
║  remove(Object o)                                     ║
║  contains(Object o)                                   ║
╠═══════════════════════════════════════════════════════╣
║ HashMap (реализация)                                  ║
│                                                       │
│  Key              │  Value                            │
│  ─────────────────┼────────────                       │
│  "apple"         │  PRESENT                           │
│  "banana"        │  PRESENT                           │
│  "cherry"        │  PRESENT                           │
│                  │                                    │
╚═══════════════════════════════════════════════════════╝

Практические примеры

1. Добавление элемента

Set<String> set = new HashSet<>();
set.add("apple");  // Внутри: map.put("apple", PRESENT)
set.add("banana"); // Внутри: map.put("banana", PRESENT)

// set теперь содержит: {"apple", "banana"}

2. Проверка наличия

set.contains("apple");  // Внутри: map.containsKey("apple") → true
set.contains("orange"); // Внутри: map.containsKey("orange") → false

3. Удаление

set.remove("apple");  // Внутри: map.remove("apple") удаляет запись

Сравнение характеристик

Почему HashSet использует HashMap?

1. Переиспользование существующей реализации

// Нет смысла заново писать логику хеширования,
// если HashMap уже её реализует
HashSet заимствует мощь HashMap, убирая лишнее (значения)

2. Одинаковая производительность

Так как HashSet на основе HashMap, они имеют одинаковую сложность:

• add(E) → O(1) — put в HashMap
• remove(Object) → O(1) — remove из HashMap
• contains(Object) → O(1) — containsKey из HashMap
• size() → O(1) — размер HashMap

3. Согласованное поведение

Set<Integer> set = new HashSet<>();
set.add(1);
set.add(2);
set.add(1);  // Второе добавление 1 игнорируется

System.out.println(set.size());  // 2, не 3
System.out.println(set);         // [1, 2]

LinkedHashSet — расширение HashSet

Есть ещё LinkedHashSet, который сохраняет порядок вставки:

public class LinkedHashSet<E> extends HashSet<E> {
    private LinkedHashMap<E, Object> map;  // LinkedHashMap вместо HashMap!
    // Сохраняет порядок вставки
}

Set<String> set = new LinkedHashSet<>();
set.add("apple");
set.add("banana");
set.add("cherry");

for (String fruit : set) {
    System.out.println(fruit);
}
// Вывод:
// apple (первый добавленный)
// banana
// cherry

Различия в использовании

HashMap — когда нужны пары

Map<String, Integer> ages = new HashMap<>();
ages.put("Иван", 25);
ages.put("Мария", 30);
ages.put("Петр", 25);  // Значение может повторяться

for (String name : ages.keySet()) {
    System.out.println(name + ": " + ages.get(name));
}
// Иван: 25
// Мария: 30
// Петр: 25

HashSet — когда нужны уникальные значения

Set<Integer> uniqueAges = new HashSet<>(ages.values());
System.out.println(uniqueAges);  // [25, 30] — дубликат 25 удалён

Важный момент: hashCode() и equals()

Для корректной работы HashSet (и HashMap) нужно правильно реализовать hashCode() и equals():

public class Person {
    private String name;
    private int age;
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age && Objects.equals(name, person.name);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

// Теперь HashSet корректно определяет дубликаты
Set<Person> people = new HashSet<>();
people.add(new Person("Иван", 25));
people.add(new Person("Иван", 25));  // Дубликат не добавится
System.out.println(people.size());   // 1

Заключение

HashSet — это адаптер HashMap, который скрывает значения (использует фиксированный PRESENT объект) и выставляет только операции работы с уникальными элементами. Это отличный пример паттерна Adapter в объектно-ориентированном программировании, где существующий класс переиспользуется с минимальными изменениями для новой цели.