Что быстрее работает: HashMap или HashSet в Java

Что проверяют

Знаете ли вы, что HashSet внутри это HashMap, и заметите ли, что вопрос поставлен некорректно. Сравниваются коллекции с разными контрактами, и хороший ответ начинается с того, что выбирать между ними по скорости нечего.

Как отвечать

HashSet хранит элементы в поле типа HashMap и кладёт их ключами, а значением идёт один общий объект-заглушка на все элементы. Операции делегируются напрямую: add это put с заглушкой, contains это containsKey, remove это удаление ключа со сравнением возвращённого значения. Значит асимптотика одинаковая: в среднем константа на вставку, поиск и удаление, а при массовых коллизиях бакет с некоторого порога превращается в дерево, и худший случай становится логарифмическим вместо линейного.

Практическая разница сводится к лишнему уровню делегирования, который JIT в горячем коде обычно встраивает, и к тому, что памяти HashSet не экономит: узел в таблице создаётся тот же самый, просто со ссылкой на общую заглушку.

Вывод, который и хотят услышать: выбирают не по скорости, а по задаче. Нужен только факт наличия элемента, берут HashSet, нужна связка ключа со значением, берут HashMap. А сильнее любого выбора на скорость влияет качество hashCode и согласованный с ним equals.

Где спотыкаются

Говорят, что HashSet быстрее, потому что «хранит только значения, а не пары». Внутри там ровно та же таблица с теми же узлами, экономии нет ни по времени, ни по памяти.

Второе: называют значением-заглушкой Boolean.TRUE. На деле это приватный статический Object, созданный один раз. Мелочь, но она ровно про то, заглядывали ли вы в исходники, а вопрос задают именно за этим.

Третье: произносят константное время как гарантию. Оно среднее и держится только на приличном распределении хэшей. Отдельно стоит упомянуть мутацию ключа после вставки: изменили поле, участвующее в hashCode, и объект остался в старом бакете, а искаться будет в новом, то есть пропал из коллекции навсегда.