Переопределение hashCode в Java для конкретного случая

Question

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

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

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

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

- Правка -

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

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

Answer 1

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

Answer 2

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

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

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

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

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

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

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

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

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

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

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

Answer 3

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

Answer 4

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

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

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

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

Answer 5

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

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

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

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

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