Что вызывает слегка непредсказуемый порядок итератора () для классов java.util.HashSet и HashMap.keySet ()? - PullRequest
9 голосов
/ 11 декабря 2010

Шесть лет назад я несколько дней горел, пытаясь отыскать, где моя совершенно детерминированная структура реагировала случайным образом. После тщательной погони за всем фреймворком, который гарантировал, что все они использовали один и тот же экземпляр Random, я продолжал гоняться за одним пошаговым кодом. Это был многократно повторяющийся итеративный код. Хуже того, проклятый эффект проявится только после того, как будет выполнено огромное количество итераций. И после +6 часов я наконец пришел в себя, когда обнаружил в javadoc строку для HashSet.iterator (), указывающую, что он не гарантирует порядок, в котором он будет возвращать элементы. Затем я просмотрел всю свою кодовую базу и заменил все экземпляры HashSet на LinkedHashSet. И ничтожно, мои рамки возникли прямо в детерминированной жизни! ARGH!

Я только что испытал этот же эффект FREAKIN, опять же (по крайней мере, на этот раз это было всего 3 часа). По какой-то причине я пропустил небольшую деталь, что HashMap ведет себя так же, как и его keySet ().

Вот SO тема на эту тему, хотя обсуждение никогда не отвечает на мой вопрос: Порядок итерации HashSet

Итак, мне любопытно, почему это может произойти. Учитывая оба раза, у меня было огромное однопоточное Java-приложение, сканирующее точно одно и то же пространство создания и вставки с одинаковыми параметрами JVM (несколько запусков из одного пакетного файла) на одном и том же компьютере, на котором почти ничего не работало, что могло бы нарушить JVM такой, что HashSet и HashMap, после огромного числа итераций, будут вести себя непредсказуемо (не противоречиво, как в javadoc говорится, что они не зависят от порядка)?

Есть ли какие-либо идеи относительно этого из исходного кода (реализация этих классов в java.util) или из ваших знаний о JVM (возможно, некоторые GC влияют на то, где внутренние классы java получают ненулевую память при выделении внутренних пространств памяти)?

Ответы [ 4 ]

9 голосов
/ 12 декабря 2010

Короткий ответ

Есть компромисс.Если вам нужен амортизированный доступ к элементам с постоянным временем O (1) , на сегодняшний день методы основаны на рандомизированной схеме, такой как хеширование.Если вы хотите упорядоченный доступ к элементам, лучший компромисс между проектами дает вам только производительность O (ln (n)) .Для вашего случая, возможно, это не имеет значения, но разница между постоянным временем и логарифмическим временем имеет очень большое значение, начиная даже с относительно небольших структур.

Так что да, вы можете посмотреть на код и внимательно изучить его, но это сводится к довольно практическому теоретическому факту.Сейчас самое время стереть пыль с этой копии Cormen (или Googly Bookiness here ), которая поддерживает наклонный угол фундамента вашего дома, и взгляните на главы 11 (Хеш-таблицы) и 13 (Красно-черные деревья).Они проинформируют вас о реализации JDK HashMap и TreeMap соответственно.

Длинный ответ

Вы не хотите, чтобы Map или Set возвращали упорядоченные списки ключей / участников.Это не то, для чего они.Структуры Maps и Sets упорядочены не так, как базовые математические концепции, и они обеспечивают разную производительность.Целью этих структур данных (как указывает @thejh) является эффективное амортизированное время insert, contains и get, а не поддержание порядка.Вы можете посмотреть, как поддерживается хешированная структура данных, чтобы узнать, каковы компромиссы.Взгляните на записи Википедии в Хеш-функциях и Хеш-таблицы (по иронии судьбы, обратите внимание, что запись в вики для "неупорядоченной карты" перенаправляет на последнюю) или на информатику / структуры данныхtext.

Помните: не полагайтесь на свойства ADT (и, в частности, коллекций), такие как упорядоченность, неизменяемость, безопасность потоков или что-либо еще, если только вы внимательно не посмотрите, что такое контракт.Обратите внимание, что для Map Javadoc четко говорит:

Порядок карты определяется как порядок, в котором итераторы в представлениях коллекции карты возвращают свои элементы.Некоторые реализации карт, такие как класс TreeMap, дают определенные гарантии относительно их порядка;другие, например класс HashMap, этого не делают.

И Set.iterator() имеет аналогичные значения:

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

Если вы хотите упорядочить их представление, используйте один из следующих подходов:

  • Если это просто Set, может быть, вы действительно хотите SortedSet, например TreeSet
  • Используйте TreeMap, который допускает либо естественное упорядочение ключей, либо конкретное упорядочение с помощью Comparator
  • Абстрагируйте вашу структуру данных, которая в любом случае, вероятно, относится к конкретному приложению, если вы хотите именно такое поведение, и поддерживайте обаSortedSet клавиш, а также Map, которые будут работать лучше в амортизированном времени.
  • Получите Map.keySet() (или просто Set, в которой вы заинтересованы) и поместите его в SortedSet, например, TreeSet, либо с использованием естественного порядка, либо определенного Comparator.
  • Выполните итерацию по Map.Entry<K,V>, используя Map.entrySet().iterator(), после его сортировки.Например, for (final Map.Entry<K,V> entry : new TreeSet(map.entrySet())) { } для эффективного доступа к ключам и значениям.
  • Если вы делаете это только один раз и некоторое время, вы можете просто получить массив значений из вашей структуры и использовать Arrays.sort(), который имеет другой профиль производительности (пространство и время).

Ссылки на источник

Если вы хотите посмотреть на источник для j.u.HashSet и j.u.HashMap , они доступны на GrepCode. Обратите внимание, что HashSet - это просто сахар для HashMap. Почему не всегда использовать отсортированные версии? Ну, как я упоминал выше, производительность отличается, и это имеет значение в некоторых приложениях. См. связанный вопрос SO здесь . Вы также можете увидеть некоторые конкретные цифры производительности внизу здесь (Я не внимательно изучил, чтобы убедиться, что они точные, но они подтверждают мою точку зрения, поэтому я беспечно передам ссылку.: -)

4 голосов
/ 12 декабря 2010

Я уже делал это раньше, когда порядок не был важен , но влиял на результаты.

Многопоточная природа Java означает, что на повторные запуски с одинаковыми входными данными могут влиять небольшие временные различия (например) того, сколько времени занимает выделение нового блока памяти, что иногда может потребовать разбиения Диск предыдущее содержимое, а в других случаях это не нужно. Некоторые другие потоки, не использующие эту страницу, могут продолжаться, и вы можете получить другой порядок создания объектов, если учитывать объекты System.

Это может повлиять на результат Object.hashCode() для эквивалентного объекта в различных прогонах JVM.

Для меня я решил добавить небольшие накладные расходы на использование LinkedHashMap, чтобы иметь возможность воспроизводить результаты тестов, которые я проводил.

3 голосов
/ 12 декабря 2010

http://download.oracle.com/javase/1.4.2/docs/api/java/lang/Object.html#hashCode() говорит:

Насколько это практически целесообразно, метод hashCode, определенный классом Object, возвращает разные целые числа для разных объектов.(Это обычно реализуется путем преобразования внутреннего адреса объекта в целое число, но этот метод реализации не требуется языком программирования JavaTM.)

Так, может быть, внутренний адрес изменяется?

Это также означает, что вы могли бы исправить это, не отказываясь от скорости, написав свой собственный метод hashCode() для всего, что должно действовать как ключ.

1 голос
/ 12 декабря 2010

Вы НИКОГДА не должны зависеть от порядка хэш-карты.

Если вам нужна карта с детерминированным порядком, я предлагаю вам использовать SortedMap / SortedSet, например TreeMap / TreeSet, или использовать LinkedHashMap / LinkedHashSet. Я использую последнее часто, не потому, что программе нужен порядок, а потому, что ее легче читать журналы / отлаживать состояние карты. т.е. когда вы добавляете ключ, он каждый раз заканчивается до конца.

Вы можете создать два HashMap / HashSet с одинаковыми элементами, но получать разные заказы в зависимости от емкости коллекции. Тонкие различия в том, как работает ваш код, могут привести к другому итоговому размеру корзины и, следовательно, к другому порядку.

, например

public static void main(String... args) throws IOException {
    printInts(new HashSet<Integer>(8,2));
    printInts(new HashSet<Integer>(16,1));
    printInts(new HashSet<Integer>(32,1));
    printInts(new HashSet<Integer>(64,1));
}

private static void printInts(HashSet<Integer> integers) {
    integers.addAll(Arrays.asList(0,10,20,30,40,50,60,70,80,90,100));
    System.out.println(integers);
}

печать

[0, 50, 100, 70, 40, 10, 80, 20, 90, 60, 30]
[0, 50, 100, 70, 80, 20, 40, 10, 90, 60, 30]
[0, 100, 70, 40, 10, 50, 80, 20, 90, 60, 30]
[0, 70, 10, 80, 20, 90, 30, 100, 40, 50, 60]

Здесь у вас есть HashSet (s) с одинаковыми значениями, добавленными в том же порядке, что приводит к различным порядкам итераторов. Возможно, вы не играете с конструктором, но ваше приложение может косвенно вызывать другой размер корзины.

...