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