Можно ли получить Set на базе HashMap в Java

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

Знаете ли вы, как устроен HashSet внутри, и умеете ли получить множество из произвольной Map. Для Android-разработчика следом часто спрашивают про equals и hashCode у элементов и про коллекции, экономные по памяти.

Как отвечать

Короткий ответ: да, и HashSet уже так сделан. Внутри у него поле HashMap<E, Object>, элемент кладётся ключом, а значением служит общая заглушка PRESENT, обычный new Object(). Метод add возвращает true, если put вернул null, то есть ключа раньше не было. Отсюда все свойства: уникальность по equals и hashCode, add и contains за O(1) в среднем, отсутствие порядка, допустим один null.

Способы получить Set на базе мапы:

• new HashSet<>(): готовая обёртка над HashMap. LinkedHashSet так же построен на LinkedHashMap и сохраняет порядок вставки;
• map.keySet(): представление ключей существующей мапы. Удаление из него удаляет запись из мапы, а add бросает UnsupportedOperationException;
• Collections.newSetFromMap(map): превращает любую пустую Map<E, Boolean> в Set. Так получают потокобезопасное множество на ConcurrentHashMap или множество со слабыми ссылками на WeakHashMap;
• ConcurrentHashMap.newKeySet(): короткий вариант для конкурентного случая, на Android доступен с API 24.

Для Android добавьте: на маленьких наборах ArraySet из androidx.collection занимает меньше памяти, чем HashSet, потому что не создаёт объект узла на каждый элемент, но поиск в нём бинарный, O(log n). В Kotlin mutableSetOf() возвращает LinkedHashSet, а hashSetOf() обычный HashSet.

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

Говорят, что значение во внутренней мапе это Boolean.TRUE или сам элемент. Там общий объект-заглушка: HashSet просто переиспользует готовую реализацию мапы.

Меняют поле объекта, от которого зависит hashCode, после добавления в множество. Элемент остаётся в старой корзине, contains возвращает false, а удалить его уже не получается.

Путают keySet() с копией. Это живое представление: изменения мапы сразу видны в нём и наоборот, а для независимого множества нужен new HashSet<>(map.keySet()).