Java-коллекции, поддерживающие порядок вставки

Question

Почему некоторые структуры данных коллекции не поддерживают порядок вставки?Что особенного достигнуто по сравнению с поддержанием порядка вставки?Получим ли мы что-нибудь, если не будем поддерживать порядок?

Answer 1

Производительность. Если вы хотите исходный порядок вставки, есть классы LinkedXXX, которые поддерживают дополнительный связанный список в порядке вставки. В большинстве случаев вам все равно, поэтому вы используете HashXXX, или вы хотите естественный порядок, поэтому вы используете TreeXXX. В каком из этих случаев вы должны оплачивать дополнительную стоимость связанного списка?

Answer 2

Коллекции не поддерживают порядок вставки. Некоторые просто по умолчанию добавляют новое значение в конце. Поддержание порядка вставки полезно только в том случае, если вы устанавливаете приоритеты для объектов или используете его для сортировки объектов каким-либо образом.

Что касается того, почему некоторые коллекции поддерживают его по умолчанию, а другие нет, это в основном вызвано реализацией и лишь иногда является частью определения коллекций.

• Списки поддерживают порядок вставки, поскольку простое добавление новой записи в конце или в начале является самой быстрой реализацией метода add (Object).

• Наборы Реализации HashSet и TreeSet не поддерживают порядок вставки, поскольку объекты сортируются для быстрого поиска, и для поддержания порядка вставки потребуется дополнительная память. Это приводит к увеличению производительности, так как порядок вставки почти никогда не интересен для Sets.

• ArrayDeque может использоваться квитанция для простых очередей и стеков, поэтому вы хотите иметь поведение «первым пришел первым - первым» или «первым вышел последним», оба требуют, чтобы ArrayDeque поддерживает порядок вставки. В этом случае порядок ввода поддерживается как центральная часть договора о классах.

Answer 3

• Порядок вставки по сути не поддерживается в хеш-таблицах - именно так они и работают (прочитайте связанную статью, чтобы понять детали).Можно добавить логику для поддержания порядка вставки (как в LinkedHashMap), но для этого требуется больше кода, а во время выполнения - больше памяти и больше времени.Потери производительности, как правило, незначительны, но могут быть.
• Для TreeSet/Map основной причиной их использования является естественный порядок итераций и другие функциональные возможности, добавленные в интерфейс SortedSet/Map.

Answer 4

Когда вы используете HashSet (или HashMap), данные хранятся в «корзинах» на основе хеша вашего объекта.Таким образом, к вашим данным будет проще получить доступ, потому что вам не нужно искать эти конкретные данные во всем наборе, вам просто нужно смотреть в правильное ведро.

Таким образом, вы можете повысить производительность в определенных точках.

У каждой реализации Collection есть своя особенность, чтобы ее было проще использовать в определенных условиях.Каждая из этих особенностей имеет свою стоимость.Поэтому, если он вам действительно не нужен (например, порядок вставки), лучше использовать реализацию, которая его не предлагает и лучше соответствует вашим требованиям.

Answer 5

Зависит от того, что вам нужно для успешной реализации.Порядок вставки, как правило, не интересен, поэтому нет необходимости поддерживать его, чтобы можно было изменить порядок, чтобы повысить производительность.

Для карт обычно используются HashMap и TreeMap.Используя хэш-коды, записи можно помещать в небольшие группы, в которых можно легко выполнять поиск. TreeMap поддерживает отсортированный порядок вставленных записей за счет более медленного поиска, но легче сортировать, чем HashMap.

Answer 6

некоторые коллекции не поддерживают порядок из-за того, что они вычисляют хэш-код содержимого и соответственно сохраняют его в соответствующем сегменте.

Answer 7

Хорошо ... так что эти посты старые по сравнению с нынешними, но порядок вставки необходим в зависимости от ваших потребностей или требований приложения, поэтому просто используйте правильный тип коллекции.В большинстве случаев это не нужно, но в ситуации, когда вам нужно использовать объекты в порядке их хранения, я вижу определенную необходимость.Я думаю, что порядок имеет значение, когда вы создаете, например, мастера или движок потоков или что-то в этом роде, где вам нужно переходить из состояния в состояние или что-то в этом роде.В этом смысле вы можете считывать данные из списка, не отслеживая, что вам нужно дальше, или просматривать список, чтобы найти то, что вы хотите.Это действительно помогает с производительностью в этом смысле.Неважно, иначе эти коллекции не имели бы особого смысла.

Answer 8

В разделе «Поваренная книга Java O'Reilly» есть раздел «Избежание желания сортировать». Вопрос, который вы должны задать, на самом деле противоположен вашему первоначальному вопросу ... «Получаем ли мы что-то, сортируя?» Требуется много усилий, чтобы отсортировать и поддерживать этот порядок. Конечно, сортировка проста, но в большинстве программ она обычно не масштабируется. Если вы собираетесь обрабатывать тысячи или десятки тысяч запросов (insrt, del, get и т. Д.) В секунду, независимо от того, используете ли вы отсортированную или несортированную структуру данных, это будет серьезно иметь значение.

Answer 9

Почему необходимо поддерживать порядок вставки?Если вы используете HashMap, вы можете получить запись по key.Это не значит, что он не предоставляет классы, которые делают то, что вы хотите.

Answer 10

Я не могу ссылаться на ссылку, но по своей конструкции реализации List и Set интерфейса Collection в основном расширяемы Array s. Так как Collections по умолчанию предлагает методы для динамического добавления и удаления элементов в любой точке, чего нет у Array, порядок вставки может не сохраняться. Таким образом, поскольку существует больше методов для манипулирования контентом, существует необходимость в специальных реализациях, которые сохраняют порядок.

Другим моментом является производительность, поскольку наиболее эффективная Collection может не соответствовать той, которая сохраняет порядок вставки. Однако я не уверен, как именно Collections управляет их контентом для повышения производительности.

Итак, короче говоря, две основные причины, по которым я могу придумать, почему существуют реализации, поддерживающие порядок Collection:

1. Архитектура класса
2. Производительность