Как устроен HashSet внутри?
HashSet — это HashMap: элементы — ключи, значение — общий объект-заглушка. LinkedHashSet построен на LinkedHashMap, TreeSet — на TreeMap.
- Уникальность — через hashCode и equals ключей
- Порядок обхода не определён
- add возвращает false, если элемент уже был
А ещё Отсюда все свойства и ловушки — как у ключей HashMap
Подробно
Тот же приём применён и к остальным: LinkedHashSet построен на LinkedHashMap, TreeSet — на TreeMap. Отсюда сразу следуют все свойства множества: уникальность обеспечивается тем же механизмом, что и уникальность ключей карты, то есть парой hashCode и equals; порядок обхода HashSet не определён; добавление и проверка наличия работают в среднем за константу. Именно поэтому объект без корректных hashCode и equals в множестве ведёт себя непредсказуемо — он попадает не в тот бакет и не находится.
Что хотят услышать
- Устройство через HashMap.
- Следствия для уникальности и порядка.
Частые ошибки
- Считать, что множество хранит элементы упорядоченно.
- Класть в HashSet объекты без переопределённых hashCode и equals.
Проверьте себя
Один верный вариант. Подумайте, потом откройте ответ.
Показать варианты и ответ
- ✓Обёртка над HashMap: элементы — ключи, значение — общая заглушка
- ✗Это связный список, где при каждом добавлении проверяется equals со всеми элементами
- ✗Это отсортированный массив с двоичным поиском
- ✗Это красно-чёрное дерево, как и TreeSet
Что спросят дальше
- Какой объект выступает значением-заглушкой и почему он один на все элементы?
- Чем уникальность в TreeSet отличается от уникальности в HashSet?
Разбор темы
- Set: HashSet, LinkedHashSet, TreeSet
Почему Set построен поверх Map, три реализации и их гарантии порядка, роль equals/hashCode.
Связанные вопросы
Разбор собеседования с sotto
После собеседования sotto разбирает разговор: оценка, каждый вопрос — хорошо, частично или слабо, чего не хватило в ответе и над чем поработать к следующему разу. Первые 30 минут бесплатно.