Какую реализацию Set использовать, если нужен порядок элементов
Что проверяют
Уточните ли вы, какой именно порядок нужен, и знаете ли цену каждого варианта.
Как отвечать
Первым делом уточните вопрос: порядок вставки или порядок сортировки. Это разные задачи и разные реализации.
Порядок вставки это LinkedHashSet. Внутри та же хеш-таблица, что и у обычного множества, плюс двусвязный список, связывающий элементы в порядке добавления. Отсюда:
- все операции остаются в среднем за постоянное время, как у обычного множества;
- обход идёт в порядке добавления и работает даже быстрее, потому что не приходится проходить пустые корзины;
- плата это дополнительная память на две ссылки у каждого элемента.
Порядок сортировки это TreeSet, реализованный красно-чёрным деревом:
- операции за логарифм, а не за постоянное время;
- элементы обязаны быть сравнимыми либо нужен компаратор;
- взамен доступны навигационные операции: первый и последний элемент, ближайший больший и меньший, подмножество по диапазону, обратный порядок;
- важная тонкость: равенство здесь определяется сравнением, а не методом равенства. Компаратор, считающий два разных объекта одинаковыми, приведёт к тому, что второй просто не добавится.
Обычное множество на хеш-таблице порядка не гарантирует вовсе, и полагаться на наблюдаемый порядок нельзя: он зависит от хешей и меняется при перестроении таблицы.
Правило выбора простое: нужен порядок добавления, берите вариант со связным списком, потому что он почти ничего не стоит. Нужна сортировка, берите дерево и осознанно платите логарифмом.
Для конкурентного случая с сортировкой существует множество на списках с пропусками, где операции тоже логарифмические, но без глобальной блокировки.
Где спотыкаются
Полагаются на порядок обхода обычного множества.
Берут дерево там, где нужен просто порядок вставки.
Задают компаратор, несогласованный с равенством, и теряют элементы.
Не знают, что связный вариант почти не проигрывает по скорости.