​java.util.Set: сравнение реализаций.

Set - интерфейс для коллекций из уникальных элементов. В стандартной библиотеке java 6 реализаций:
HashSet, TreeSet, LinkedHashSet, CopyOnWriteArraySet, ConcurrentSkipListSet и EnumSet.
В этой статье рассмотрим и сравним первые три из них.

Детали реализации:
1️⃣ TreeSet базируется на TreeMap, а он - на основе красно-чёрного дерева. Элементы коллекции должны реализовать интерфейс Comparable, либо экземпляр Comparable нужно передать в конструкторе, потому что compareTo - основной метод для вставки и поиска элементов.
✅ Отсортированные значения.
✅ Быстрая ребалансировка.
✅ Можно искать по ближайшему ключу - доступны функции lower(e), floor(e), ceiling(e), higher(e).

2️⃣ HashSet внутри себя содержит HashMap. Он реализован так:
Есть массив корневых элементов - их ещё называют бакетами. Размер массива по умолчанию 16.
Если нужно добавить элемент в коллекцию, то сначала вычисляется его хэш. Далее ищется индекс корневого элемента - остаток от деления хэша на размер массива. Если по этому индексу ничего нет, корнем становится новый элемент. Если есть - добавляется в структуру под ним.
В java 7 этой структурой был список, с java 8 - бинарное дерево.
Эффективность HashSet зависит от равномерности распределения хэшей. В энтерпрайз приложениях хэш вычисляется по набору полей, и равномерность часто не достигается. Поэтому на практике HashSet не всегда является оптимальной структурой данных. Если известно примерное количество элементов, можно задать loadFactor и capacity в конструкторе.
✅ Возможность оптимизации.
✅ Быстрый поиск.
❌ Значения не отсортированы.
❌ Долгая перестройка при увеличении размера коллекции.

3️⃣ LinkedHashSet расширяет класс HashSet. Помимо основной структуры новые элемент также добавляются в двусвязный список.
✅ Значения отсортированы по порядку вставки.
✅ Возможность оптимизации.

Знание деталей реализации даёт простые правила выбора:
1️⃣ Частый поиск - выбираем TreeSet.
2️⃣ Порядок не важен - HashSet.
3️⃣ Порядок вставки важен - LinkedHashSet.

Мы проверили, насколько велика разница между реализациями:
1️⃣ Добавить в Set миллион чётных чисел.
2️⃣ Вставить миллион нечётных.
3️⃣ Найти миллион случайных.
Запустили несколько раз для HashSet, TreeSet, LinkedHashSet, а также для HashSet и LinkedHashSet с заранее заданной ёмкостью в 2 миллиона. Проверили на java 7 и 11.
В качестве типов данных использовали Integer(идеальное распределение хэшей) и класс с несколькими полями (неравномерное распределение).

Результаты на картинке внизу поста. Тест не претендует на точность, но теперь можно добавить ещё несколько рекомендаций:
✅ В новых версиях java все операции всех реализаций работают на 5-20% быстрее.
✅ Выбор реализации имеет значение.
✅ Знаете будущий размер коллекции - передавайте его в конструкторе.
✅ Для чисел лучше использовать HashSet.
✅ Для экземпляров классов всё неоднозначно, имеет смысл попробовать разные варианты.