Какая структура данных Java представляет собой упорядоченную коллекцию, предоставляет постоянное время функции contains метод HashSet и обеспечивает постоянный поиск по времени по индексу, как метод ArrayList get? Является ли Java API такой? Я рассматривал использование TreeSet, но в соответствии с документами Java эти операции - O (log n).Java Ordered Hashable Collection
Использование LinkedHashSet. Это таблица Hash и реализация связанного списка интерфейса Set с предсказуемым порядком итерации.
Вы увидите до сложности O (n) для вставки или проверки существования элемента в хэш-наборе. Однако в большинстве случаев вы не видите столкновений, и поэтому в большинстве случаев это будет O (1).
Поддерживает ли LinkedHashSet индексирование? – Aroto
Устанавливаемый интерфейс не имеет прямых методов, таких как indexOf() или get(). Вам нужно проанализировать всю коллекцию, чтобы найти элемент. indexOf() и get() внутренне делают то же самое. – FallAndLearn
OP запрашивает поиск элементов по постоянному времени * по индексу *. Хотя 'LinkedHashSet' предлагает поиск по постоянному времени, это только ключ, а не индекс. –
Стандартная библиотека Java не предлагает такой класс, но вы можете реализовать свои собственные без особых проблем. Это было бы более или менее двойственное от LinkedHashSet: a List (возможно, обертывание ArrayList), которое поддерживает внутреннюю обработку HashSet для обработки постоянного времени.
В API коллекций есть классы, предназначенные для упрощения реализации классов сбора уроков ; в этом случае я бы посмотрел на реализацию конкретного подкласса AbstractList.
Update: С другой стороны, если ваша идея заключается в том, что экземпляры автоматически сохраняют свои элементы в порядке, и/или что они запрещают повторяющиеся элементы, то, что вы говорите не List вообще , В этом случае вы хотели бы рассмотреть вопрос о внедрении конкретного подкласса AbstractSet, который добавит индексированные методы поиска. Вы все равно можете обернуть HashSet и ArrayList, но вам нужно потратить некоторое усилие, чтобы сохранить список, упорядоченный по вставке элементов.
Возможно ли ['LinekdHashSet'] (https://docs.oracle.com/javase/8/docs/api/java/util/LinkedHashSet.html)? – Mureinik
Вам нужна постоянная вставка? Если это так, это не сработает, поскольку подобная структура данных позволит вам выполнить сортировку в O (n) времени. – user2357112
Когда вы говорите «приказано», вы имеете в виду упорядоченный заказ, или вы имеете в виду какой-то другой порядок, например, порядок вставки? – user2357112