Hash Set

Когда нужно хранить только факт наличия

HashSet хранит уникальные значения без отдельного связанного значения. Главный вопрос, на который он отвечает: «есть ли этот элемент в множестве?». Добавление, проверка и удаление в среднем занимают O(1).

Если добавить один и тот же элемент несколько раз, в множестве всё равно останется одна логическая запись. Метод add() возвращает true, если элемент действительно был добавлен, и false, если он уже присутствовал.

Поиск повторяющегося значения

static boolean hasDuplicate(int[] numbers) {
    Set<Integer> seen = new HashSet<>();

    for (int value : numbers) {
        if (!seen.add(value)) {
            return true;
        }
    }

    return false;
}

Каждое значение добавляется в seen только при первом появлении. Если add() вернул false, значит такое значение уже встречалось, и повтор найден сразу — без отдельного прохода по предыдущим элементам.

При ожидаемой стоимости операций O(1) весь алгоритм работает за O(n) и использует до O(n) дополнительной памяти. Прямое сравнение каждого элемента со всеми последующими потребовало бы O(n²) времени.

Set или Map

Выбор обычно простой. Если нужно хранить только сами уникальные значения и проверять их наличие — используй Set. Если каждому ключу нужно сопоставить дополнительную информацию — используй Map. Не стоит хранить фиктивные значения в Map только ради проверки принадлежности, когда Set выражает задачу точнее.