JDK9 рандомизация на неизменяемых множествах и картах

Считывая этот вопрос и ответ, данный Юджином, я обнаружил, что неизменяемые множества и карты JDK9 будут ввести источник случайности, который повлияет на их обход. Это означает, что порядок итераций действительно будет случайным, по крайней мере, среди разных прогонов JVM.

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

Я знаю, что сегодня, с JDK 8, если у меня есть a HashSet и делаю это (взято из связанного ответа):

Set<String> wordSet = new HashSet<>(Arrays.asList("just", "a", "test"));

System.out.println(wordSet);

for (int i = 0; i < 100; i++) {
    wordSet.add("" + i);
}

for (int i = 0; i < 100; i++) {
    wordSet.remove("" + i);
}

System.out.println(wordSet);

Затем порядок итераций элементов изменится, и два выхода будут отличаться. Это связано с тем, что добавление и удаление 100 элементов в набор изменяет внутреннюю емкость элементов HashSet и повторяет элементы. И это совершенно правильное поведение. Я не спрашиваю об этом здесь.

Однако с JDK9, если я это сделаю:

Set<String> set = Set.of("just", "a", "test");
System.out.println(set);

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

До сих пор я нашел этот отличный видеоролик

Ответы

Ответ 1

Ну, оказывается, есть еще одна причина для рандомизированного порядка итерации. Это не большой секрет или что-то еще. Я думал, что объяснил это в этом разговоре, но, возможно, нет. Я, вероятно, упомянул об этом в списках рассылки OpenJDK или, возможно, во внутренних дискуссиях.

В любом случае другой причиной рандомизированного порядка итераций является сохранение гибкости для будущих изменений в реализации.

Это, оказывается, большая сделка, чем думают многие. Исторически HashSet и HashMap никогда не указывали конкретный порядок итераций. Однако время от времени реализация должна была меняться, улучшать производительность или исправлять ошибки. Любое изменение порядка итераций порождало большое количество вкладок от пользователей. На протяжении многих лет было много сопротивления, созданного для изменения порядка итераций, и это затрудняло техническое обслуживание HashMap.

Чтобы понять, почему это проблема, рассмотрите спектр различных политик для управления стабильностью итерационного порядка:

  • Укажите порядок итераций и придерживайтесь его.

  • Оставьте порядок итераций неопределенным, но неявно сохраните порядок итераций.

  • Оставьте порядок итераций неопределенным, но измените порядок итераций как можно меньше.

  • Часто меняйте порядок итераций, например, в релизах обновлений.

  • Изменить порядок итераций чаще, например, с одного запуска JVM на следующий.

  • Часто меняйте порядок итераций еще больше, например, с одной итерации на следующую.

Когда коллекции были введены в JDK 1.2, HashMap порядок итерации был неуказан. Стабильный порядок итераций был обеспечен LinkedHashMap с несколько более высокой стоимостью. Если вам не нужен стабильный порядок итераций, вам не придется платить за это. Это исключало №1 и №2.

Для следующих нескольких выпусков мы попытались сохранить стабильный порядок итераций, хотя спецификация позволила ему измениться. Никто не любит, когда код ломается, и довольно неприятно говорить клиенту, что его код сломан, потому что он зависит от порядка итерации.

Итак, мы закончили с политикой № 3, сохраняя порядок итераций как можно более стабильным, хотя время от времени оно менялось. Например, мы внедрили альтернативное хеширование в JDK 7u6 (обзор кода для JDK-7118743) и древовидные вставки в JDK 8 (JEP 180), и оба изменили порядок итерации HashMap в некоторых случаях. Заказ также изменился пару раз в более ранних версиях. Кто-то сделал некоторую археологию и обнаружил, что порядок итераций изменился в среднем на один раз на один выпуск JDK.

Это был худший из всех возможных миров. Основные выпуски происходили только раз в пару лет. Когда кто-то вышел, все коды сломались. Было бы много плакать и скрежещать зубы, люди исправляли бы свой код, и мы обещали никогда, никогда не менять порядок итераций. Пройдут пару лет, и будет написан новый код, который непреднамеренно зависел от порядка итераций. Затем мы выпустили еще один крупный релиз, который изменил порядок итераций, и это снова сломало бы код. И цикл начнется заново.

Я хотел избежать повторения этого цикла для новых коллекций. Вместо того, чтобы поддерживать порядок итераций как можно более стабильным, я проводил политику ее изменения как можно чаще. Первоначально порядок изменялся на каждой итерации, но это накладывало некоторые накладные расходы. В конце концов мы остановились на одном вызове JVM. Стоимость - это 32-разрядная операция XOR для настольного зонда, которая, как мне кажется, довольно дешевая.

В определенной степени это касается кода приложения "ужесточения". Если изменение итерационного порядка нарушает код, тогда более частое нарушение этого кода вызывает у него сопротивление такого рода поломки. Конечно, код не становится сильнее сам по себе; для этого требуется больше усилий для разработчиков. И люди вполне резонно жалуются на необходимость выполнения этой дополнительной работы.

Но "ужесточение" кода приложения в некотором смысле является второстепенным по отношению к другой цели - сохранить свободу для изменения реализации. Сохранение порядка итераций HashMap затрудняло сохранение. Рандомизированный порядок итераций в новых коллекциях означает, что нам не нужно беспокоиться о сохранении порядка итераций при их изменении, поэтому их легче поддерживать и улучшать.

Например, текущая реализация (Java 9, pre-GA, июль 2017 года) имеет три реализации на основе полей Set (Set0, Set1 и Set2) и реализация на основе массива (SetN), который использует простое замкнутое хеширование с линейной схемой зондирования. В будущем нам может понадобиться добавить реализацию Set3, которая содержит три элемента в трех полях. Или, возможно, мы захотим изменить политику разрешения конфликтов SetN от линейного зондирования до более сложного. Мы можем полностью реструктурировать реализацию, даже в небольших выпусках, если нам не нужно иметь дело с сохранением порядка итераций.

Таким образом, компромисс заключается в том, что разработчикам приложений приходится делать больше работы, чтобы убедиться, что их код сопротивляется поломке от изменения порядка итерации. Скорее всего, они будут работать в какой-то момент с HashMap. Благодаря этому больше возможностей для JDK обеспечить улучшенную производительность и эффективность использования пространства, от чего каждый может извлечь выгоду.

Ответ 2

Эта цитата и ваши мысли вокруг уже делают сильный аргумент в пользу этого. Итак, что еще вам нужно?

Другими словами: один из "отцов" Java заявляет, что их мотивация "случайного выбора карты/набора" заключается в том, чтобы "обучать" программистов Java не ожидать или даже полагаться на какой-либо особый порядок. Поэтому ответ (вероятно, усугубляется) - сомневайтесь в ваших ожиданиях.

Ответственные люди рассказали вам о своих мыслях, чтобы сделать это. Нет оснований предполагать, что они "скрывают" другую мотивацию для этого проектного решения.

Напротив: можно было бы найти аргументы против расходов дополнительных усилий для достижения такого количества случайности - JVM, вероятно, проводит довольно много дополнительных циклов процессора - просто для достижения неопределенного поведения (что-то, что мы обычно старайтесь избегать любой ценой).