Порядок итерации HashSet

Question

Если каждый объект, добавленный в java.util.HashSet, реализует Object.equals () и Object.hashCode () детерминистическим образом, порядок итераций в HashSet гарантированно будет одинаковым для каждого идентичного набора добавленных элементов независимо порядка, в котором они были добавлены?

Бонусный вопрос: что, если порядок ввода также идентичен?

(Предполагается, что Sun JDK6 с той же инициализацией HashSet.)

Редактировать: Мой оригинальный вопрос не был ясен. Речь идет не о генеральном контракте HashSet, а о том, что реализация HashSet от Sun в JDK6 предлагает в качестве гарантий, касающихся детерминизма. Это по своей сути недетерминированный? Что влияет на порядок, используемый его итератором?

Answer 1

Абсолютно нет.

Порядок вставки напрямую влияет на порядок итераций всякий раз, когда возникает столкновение сегмента:

Когда два элемента оказываются в одном и том же сегменте, первый вставленный элемент также будет первым, возвращенным во время итерации, по крайней мере, если реализация обработки столкновений и итерации проста (а тот, что в java.util.HashMap у Sun) есть)

Answer 2

Не существует «официальной» гарантии на что-либо подобное. Я бы сказал, что это, скорее всего, верно для экземпляров той же реализации HashSet, инициализированных таким же образом. Но я видел случаи, когда порядок итераций был различным в Java 5 и 6, например.

Кроме того, он может отличаться для экземпляров одной и той же реализации HashSet, инициализированных с другим размером, из-за перефразирования. То есть если у вас есть 100 элементов и два набора, один из которых инициализирован с размером больше 100, другой - с гораздо меньшим размером, второй будет перераспределен, а его элементы повторно заполнены несколько раз при заполнении. Это может привести к тому, что элементы, сопоставленные с одним и тем же сегментом, будут добавлены (и, таким образом, повторены) в другом порядке.

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

Answer 3

Согласно документу Javadoc:

Этот класс реализует Set интерфейс, поддерживаемый хеш-таблицей (на самом деле экземпляр HashMap). Это не дает никаких гарантий относительно порядок итераций множества; в в частности, это не гарантирует, что порядок останется неизменным в течение время. [...] Итераторы, возвращаемые методом итератора этого класса, не подвержены сбоям: если набор изменяется в любое время после создания итератора

И метод iterator:

Возвращает итератор для элементов в этом наборе. Элементы возвращаются без определенного порядка.

Поэтому я не думаю, что вы можете сделать такое предположение

Answer 4

Хотел подтвердить / одобрить предыдущие комментарии. Короче говоря, Не полагайтесь на итерацию HashSet в согласованном порядке . Это может привести к ошибкам в вашей системе.

Мы только что нашли и исправили ошибку, из-за которой порядок итераций был непоследовательным в HashSet даже при:

• Идентичный порядок вставки.
• Объекты класса с допустимым методом equals () и hashCode ().

И исправил это с помощью LinkedHashSet.

Благодаря более ранним постерам:)

Answer 5

Никогда не делайте предположений о порядке итерации всего, что вы помещаете в HashSet, потому что в его контракте прямо сказано, что вы не можете рассчитывать на это каким-либо образом. Используйте LinkedHashSet , если вы хотите сохранить порядок вставки, или TreeSet , если вы хотите сохранить естественный порядок сортировки.

Answer 6

Порядок отображения объектов будет зависеть от конечного количества сегментов HashSet. Изменяя коэффициент загрузки и / или начальную емкость, вы можете изменить порядок, в котором заканчиваются элементы.

В следующем примере вы можете увидеть эти подтверждения каждый результат в различном порядке.

public static void main(String...args) throws IOException {
    printOrdersFor(8, 2);
    printOrdersFor(8, 1);
    printOrdersFor(8, 0.5f);
    printOrdersFor(32, 1f);
    printOrdersFor(64, 1f);
    printOrdersFor(128, 1f);
}

public static void printOrdersFor(int size, float loadFactor) {
    Set<Integer> set = new HashSet<Integer>(size, loadFactor);
    for(int i=0;i<=100;i+=10) set.add(i);
    System.out.println("new HashSet<Integer>("+size+", "+loadFactor+") adding 0,10, ... 100 => "+set);
}

печать

new HashSet<Integer>(8, 2.0) adding 0,10, ... 100 => [0, 50, 100, 70, 40, 10, 80, 20, 90, 60, 30]
new HashSet<Integer>(8, 1.0) adding 0,10, ... 100 => [0, 50, 100, 70, 20, 80, 10, 40, 90, 30, 60]
new HashSet<Integer>(8, 0.5) adding 0,10, ... 100 => [0, 100, 70, 40, 10, 50, 20, 80, 90, 30, 60]
new HashSet<Integer>(32, 1.0) adding 0,10, ... 100 => [0, 100, 70, 40, 10, 50, 80, 20, 90, 60, 30]
new HashSet<Integer>(64, 1.0) adding 0,10, ... 100 => [0, 70, 10, 80, 20, 90, 30, 100, 40, 50, 60]
new HashSet<Integer>(128, 1.0) adding 0,10, ... 100 => [0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100]

Answer 7

Нет, это не гарантируется.

Во-первых, разные JVM могут реализовывать алгоритм HashSet по-разному (при условии, что он соответствует спецификации HashSet), поэтому вы получите разные результаты на разных JVM.

Во-вторых, алгоритм может опираться на недетерминированные факторы при построении различных сегментов (часть алгоритма хэш-таблицы).

Answer 8

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

Этот класс реализует Set интерфейс, поддерживаемый хеш-таблицей (на самом деле экземпляр HashMap). Это не дает никаких гарантий относительно порядок итераций множества; в в частности, это не гарантирует, что порядок останется неизменным в течение время.

Самое близкое, что вы можете получить, это использовать LinkedHashSet , который поддерживает порядок вставки.

Answer 9

Я уверен, что разработчики Java хотят, чтобы вы предположили, что ответ «нет». В частности, для хеш-таблиц, почему они делают его медленнее для всех остальных, кому не нужно это свойство, чтобы гарантировать, что объекты, чьи хеш-коды конфликтуют (идентичный размер hashCode%), наблюдаются в том же порядке, независимо от того, в каком порядке они были положить в?