Как я могу хэшировать составные классы? - PullRequest
2 голосов
/ 28 марта 2011

Позвольте Abstract быть абстрактным классом и A1,A2,...,An конкретными классами, которые наследуются от Abstact.Каждый из Ai имеет список Abstract и предопределенный, известный во время компиляции набор примитивных типов, давайте предположим, что у нас есть для них функция hush, и в структуре нет «петель»каждый конкретный элемент.

Два элемента e1 и e2 идентичны, если они имеют одинаковые значения для предопределенных примитивов, и если для каждого Abstract в e1 существует Abstract в e2, такой что e1 ие2 идентичны.(другими словами, порядок не важен).

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

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

PS Я пишу на Java, и я предполагаю (исправьте меня, если я ошибаюсь) встроенную hash() не будет достаточно хорош для этой проблемы.
РЕДАКТИРОВАТЬ:
списки и примитивы фиксируются после создания, но неизвестны во время компиляции.

Ответы [ 2 ]

2 голосов
/ 28 марта 2011

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

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

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

1 голос
/ 28 марта 2011

Используйте утилиты Google Guava ... Objects.hashCode () отлично.Кроме того, источники доступны, и они решили проблему, о которой вы говорите, поэтому вы можете взглянуть на их решение.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...