Блог

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

У меня есть класс, который имеет в качестве переменной экземпляра массив того же класса. Чтобы быть более понятным, вот код:

 Class Node{
    Node arr[] = new Node[5];
}
  

Мне нужно перезаписать хэш-код для узла класса, а массив является важным, решающим фактором при определении того, являются ли два узла одинаковыми. Как я могу эффективно включить массив в вычисление хэш-кода?

—Редактировать—

Я пытаюсь проверить, совпадают ли два узла, что означает, что у них одинаковое количество дочерних элементов и что эти дочерние элементы приводят к точно таким же состояниям. Поэтому я эффективно пытаюсь сравнить поддеревья на двух узлах. Мне интересно, могу ли я использовать хеширование для выполнения этой проверки на равенство.

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

Включить http://download.oracle.com/javase/6/docs/api/java/util/Arrays.html#hashCode (java.lang.Объект[]) как часть реализации hashCode().

Я пытаюсь проверить, совпадают ли два узла, что означает, что у них одинаковое количество дочерних элементов и что эти дочерние элементы приводят к точно таким же состояниям. Поэтому я эффективно пытаюсь сравнить поддеревья на двух узлах. Мне интересно, могу ли я использовать хеширование для выполнения этой проверки на равенство.

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

Одни и те же объекты будут генерировать одинаковое значение хэша, но два разных объекта, которые не равны, также могут генерировать один и тот же хэш. Другими словами, если хэш-значения разные, вы точно знаете, что объекты разные. Вот и все.

Если вы хотите проверить равенство, вам необходимо реализовать equals . В вашем случае существует опасность, что ваш метод станет рекурсивным и спровоцирует переполнение стека. Что, если ваш объект содержит ссылку на самого себя?

Если вы хотите сгенерировать хэш, вы могли бы принять во внимание размер массива (и тот факт, что он равен null или нет), но я бы не пытался использовать значение хэша объектов в массиве из-за потенциальных бесконечных циклов. Это не идеально, но достаточно хорошо.

Существует другой радикальный метод, который также может обеспечить хороший результат. Вместо динамического вычисления хэш-значений задайте случайное значение int для каждого экземпляра объекта Node (я имею в виду один раз для всех при создании и всегда возвращать это значение). В вашем случае вы бы не рисковали бесконечными циклами, принимая хэш-значение экземпляров объекта в вашем массиве.

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

REM: Если узлы содержат другие атрибуты, то вычислите хэш для этих других атрибутов и забудьте о массиве. Начните расследование содержимого / размера массива тогда и только тогда, когда хэш идентичен между двумя объектами.

REM2: В комментариях упоминается DAG graph, что означает, что мы не столкнемся с проблемами рекурсивности. Однако этого условия недостаточно, чтобы гарантировать, что deepHashCode() будет успешным. Более того, это тоже было бы излишеством. Существует более эффективный способ решения этой проблемы.

Если хэш-метод, используемый только узлом, использует массив для вычисления хэш-значения, тогда deepHashCode() может работать. Но это было бы неэффективно. Если метод хэширования использует другие атрибуты узла, то эти атрибуты также должны быть равны.

Существует более быстрый способ сравнения узлов на предмет равенства. Пометьте каждый экземпляр узла уникальным номером. Затем, чтобы сравнить два узла, сначала сравните размер их массива. Если оно равно, то сравните узлы из каждого массива, используя их уникальный номер. Если один массив не «имеет» другого узла, то мы имеем дело не с равными узлами. Это решение намного быстрее, чем рекурсивное.

Это зависит от того, каковы ваши критерии равенства. Важен ли порядок в массиве? Если это так, вы, вероятно, захотите, чтобы хэш-код зависел от порядка узлов в массиве. Если нет, вы можете захотеть сделать что-то вроде XOR хэш-кодов всех узлов в массиве. Предположительно, некоторые значения могут быть нулевыми (так что будьте осторожны с этим).

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

У Эрика Липперта есть отличный пост в блоге о GetHashCode в .NET — совет одинаково хорошо применим и к Java.

Следует помнить об одной потенциальной проблеме — если в ваших узлах в конечном итоге возникает цикл (ссылка на узел A появляется в массиве узла B и наоборот), у вас также может возникнуть цикл при вычислении хэш-кода.

Вы можете использовать методы Arrays.hashCode() и Arrays.equals() .

Несколько моментов, которые нужно добавить к текущим ответам, если производительность вызывает какие-либо опасения.

Во-первых, вам нужно решить, имеет ли значение порядок дочерних узлов в узле. Если они этого не сделают, вы не сможете использовать хэш-код для массива. Рассмотрите возможность создания вашей функции хэш-кода вокруг функции, определенной java.util.Set . Также рассмотрите возможность использования некоторого внутреннего упорядочения для повышения производительности equals. Например, если глубина / высота поддеревьев различаются, вы можете отсортировать по глубине.

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

В-третьих, если ваши поддеревья являются глубокими, проверьте хэш-код в equals() и досрочно верните false . Да, хэш-код проверяется реализациями Map, но есть места, где код просто сравнивает два объекта с помощью equals() , и за это может быть заплачена большая цена.

Наконец, рассмотрите возможность использования Arrays.asList() (если порядок дочерних элементов имеет значение) или HashSet (если порядок не имеет значения и никакие два дочерних узла не равны) вместо простого массива. Затем equals и hashcode сводятся к делегированию вызова экземпляру контейнера… с соответствующим кэшированием хэш-кода, конечно.