Я только что наткнулся на это заявление о java.util.HashSet и он «Этот класс не дает никаких гарантий относительно порядка итераций набора, в частности, он не гарантирует, что заказ останется постоянным «Может ли кто-нибудь объяснить заявление? Заявление Источник: click hereКак работает итерация в Hashset?
HashSet использует N ведер и сохраняет элементы на основе их хэш-код в одном из этих ведер, чтобы сделать поиск быстрее: при поиске элемента, множество вычисляет хэш элемента знать, какое ведро он нуждается для поиска, тогда он проверяет, содержит ли этот ковш этот элемент. Это делает поиск N раз быстрее, так как набор не нужно проверять другим N-1 ведра.
Для небольшого количества элементов количество ведер может быть небольшим. Но с появлением большего количества элементов ведра начнут содержать больше элементов, что означает, что поиск будет медленнее. Чтобы решить эту проблему, набор должен будет добавить больше ковшей и перестроить их элементы, чтобы использовать новые ведра.
Теперь, когда мы перебираем HashSet, мы делаем это, начиная с элементов из первого ковша, затем из второго ковша и так далее. Вы видите, что Set s, которые используют только ведра, не могут гарантировать одинаковый порядок элементов, так как ведра могут меняться между итерациями.
В Java 8 HotSpot HashMap # put был улучшен для поддержки большего количества элементов и rebucket с использованием 'TreeNode', а не связанного списка, используя' Node', чтобы избежать этой медленности при добавлении/поиске элементов. –
Правда, но я старался не сосредотачиваться на внутренних деталях на ведрах, а на общей идее отсутствия гарантии порядка элементов. – Pshemo
@brimborium Спасибо за редактирование. Мой английский очень далек от совершенства, поэтому я благодарен за ваши исправления. Я отредактировал первый абзац, так что было бы неплохо, если бы вы могли взглянуть на него еще раз :) – Pshemo
В основном это означает, что HashSet не имеет заказа. Тогда вы не должны полагаться на порядок значений в вашем коде.
Если ваш комплект содержит значения {2, 1, 3} (порядок вставки), ничто не гарантирует, что итерация по нему вернется {2, 1, 3} или {1, 2, 3}.
, если вы положите три записи и повторить их дважды, вы получите тот же порядок одновременно. –
@SashaSalauyou Да, это правда. Но это особый случай. Любой вызов в «Hashset» может изменить порядок. Таким образом, заставка предполагает, что заказ не гарантируется никогда. – brimborium
Итак, всякий раз, когда добавляется элемент, значение хэша пересчитывается, следовательно, изменяется порядок в порядке справа? исправьте меня, если я ошибаюсь – comeunglued7
Поскольку HashSet не заказывается, итератор, вероятно, по очереди проводит все ведра и шаги по содержимому каждого ковша. Это означает, что если добавлено больше предметов, чтобы балансировки были перебалансированы, порядок может измениться.
E.g. если у вас есть 1, 2, 3 и вы итерации вполне можете получить 1, 3, 2. Кроме того, если вы позже добавите 4, вы можете получить 4, 2, 3, 1 или любым другим заказом.
Предыдущий заказ будет сохранен.Тот факт, что вы добавляете новый элемент, не означает, что он будет перегружать все его элементы. Если вам трудно поверить, тогда проверьте его. –
@LuiggiMendoza - Я намеренно изменил исходный порядок, потому что добавление '4' * могло * привести к перебалансировке ведер и, следовательно, к полному изменению порядка, даже к старым элементам. – OldCurmudgeon
Rebucket происходит, когда внутренний 'HashMap' имеет много элементов и преобразует узлы в' TreeNode'. Для этого случая этого не произойдет. См. Исходный код 'HashMap # put'. –
Что такое источник? –
@YassinHajaj Javadoc. –
Это означает, что при использовании итераторов для HashSet и в этом HashSet у вас есть 3 набора, тогда в одном итерационном порядке для возвращаемых наборов будет первое, второе, третье и другое время, это может быть второе, третье, первое – DawidPi