Что такое HashSet и как он связан с HashMap?

HashSet под капотом — это HashMap, где ключ — элемент, а значение — заглушка (PRESENT = new Object()). add(e) вызывает map.put(e, PRESENT). Поэтому производительность такая же: O(1) add/remove/contains. Порядок не гарантирован. Для порядка вставки — LinkedHashSet, для сортировки — TreeSet. contains() работает через hashCode() + equals(). Если переопределяешь equals() без hashCode() — объект потеряется в HashSet. null допускается (один).