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

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

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

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

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

Точно нет.

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

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

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

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

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

Согласно javadoc:

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

И iterator метода:

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

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

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

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

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

И исправил его с помощью LinkedHashSet.

Благодаря более ранним плакатам 🙂

Нет, это не гарантировано.

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

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

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

Объекты порядка будут зависеть от конечного количества ведер 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 set = new HashSet(size, loadFactor); for(int i=0;i<=100;i+=10) set.add(i); System.out.println("new HashSet("+size+", "+loadFactor+") adding 0,10, ... 100 => "+set); } 

печать

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

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

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

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

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

  • создайте стек таким образом, чтобы getMinimum () должен быть O (1)
  • Отдел без использования '/'
  • Как сравнить два цвета для сходства / разницы
  • Перечислять коэффициенты числа непосредственно в порядке возрастания без сортировки?
  • Поиск k-го наименьшего числа из n отсортированных массивов
  • Есть ли у C какие-либо инструменты для выполнения добавления строк?
  • Создание всех комбинаций из нескольких списков
  • Выберите N случайных элементов из списка в C #
  • Java. Создайте набор параметров данного списка.
  • Связанная функция списка списков и обратные результаты
  • Как вы эффективно генерируете список K неповторяющихся целых чисел между 0 и верхней границей N
  • Давайте будем гением компьютера.