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