Итеративный порядок HashSet
Если каждый объект, добавленный к java.util. HashSet реализует Object.equals () и Object.hashCode () детерминированным способом, итеративный порядок по HashSet, который, как гарантируют, будет идентичен для каждого идентичного набора добавленных элементов, независимо от порядка, в котором они были добавлены?
Вопрос о премии: что, если порядок вставки идентичен также?
(Принятие Sun JDK6 с той же инициализацией HashSet.)
Править: Мой исходный вопрос не был ясен. Это не об общем контракте HashSet, но что реализация Sun HashSet в JDK6 предлагает как гарантии относительно детерминизма. Это по сути недетерминировано? Что влияет на порядок, используемый его Итератором?
7 ответов
Абсолютно нет.
Порядок вставки напрямую влияет на порядок итерации всякий раз, когда возникает коллизия корзины:
Когда два элемента попадают в одну и ту же корзину, первый из вставленных элементов также будет первым, возвращенным во время итерации, по крайней мере, если реализация обработки столкновений и итераций проста (а в Sun java.util.HashMap )
Я уверен, что разработчики Java хотят, чтобы вы приняли ответ «нет». В частности, для хэш-таблиц, почему они должны делать его медленнее для всех, кому не нужно это свойство, чтобы гарантировать, что объекты, чьи хэши конфликтуют (идентичный размер hashCode%), наблюдаются в одном и том же порядке независимо от порядка, в котором они были вставить?
Такое предположение невозможно сделал. В документации javadoc говорится, что:
Этот класс реализует интерфейс Set , поддерживаемый хеш-таблицей (фактически экземпляром HashMap). не дает никаких гарантий относительно порядка итерации набора ; в частности, это не гарантирует, что порядок останется постоянным в течение времени.
Лучше всего использовать LinkedHashSet , который поддерживает порядок вставки.
Нет никакой "официальной" гарантии на что-либо подобное. Я бы сказал, что это, скорее всего, верно для экземпляров одной и той же реализации HashSet, инициализированных таким же образом. Но я видел случаи, когда порядок итераций различается, например, между Java 5 и 6.
Кроме того, он может отличаться для экземпляров одной и той же реализации HashSet, инициализированных с другим размером, из-за повторного хеширования. Т.е. если у вас есть 100 элементов и два набора, один инициализирован с размером больше 100, другой - с гораздо меньшим размером, второй будет перераспределен, и его элементы будут перефразированы несколько раз при заполнении. Это может привести к добавлению (и, таким образом, повторения) элементов, отображаемых в один и тот же сегмент, в другом порядке.
В Java4 и более поздних версиях у вас есть LinkedHashSet , который гарантирует, что порядок итерации будет тем же порядком, в котором были вставлены его элементы.
Согласно javadoc:
Этот класс реализует интерфейс Set , поддерживаемый хеш-таблицей (фактически экземпляром HashMap). не дает никаких гарантий относительно порядка итерации набора ; в частности, это не гарантирует, что порядок останется постоянным в течение времени. [...] Итераторы, возвращаемые методом итератора этого класса, работают без сбоев: если набор изменяется в любое время после создания итератора
И метода iterator :
Возвращает итератор по элементам в этом наборе. Элементы возвращаются в произвольном порядке.
Поэтому я не думаю, что вы можете сделать такое предположение.
Никогда не делайте предположений о порядке итерации всего, что вы помещаете в HashSet, потому что в его контракте прямо говорится, что вы не можете на это рассчитывать. Используйте LinkedHashSet , если вы хотите сохранить порядок вставки, или TreeSet , если хотите сохранить естественный порядок сортировки.
Нет, это не гарантируется.
Во-первых, разные JVM могут по-разному реализовывать алгоритм HashSet (при условии, что он соответствует спецификации HashSet), поэтому вы получите разные результаты на разных JVM.
Во-вторых, алгоритм может полагаться на недетерминированные факторы при построении различных сегментов (часть алгоритма хеш-таблицы).