Почему хэш-код Java не поддерживает универсальное хеширование?

Question

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

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

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

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

Мой вопрос: есть ли причина, по которой Java решила проектировать hashCode, не рассматривая возможностьхеширования объектов с несколькими хеш-функциями? Я понимаю, что многие хорошие схемы хеширования, такие как цепочечное хеширование или квадратичное зондирование, не требуют этого, но кажется, что решение затрудняет использование определенных классов алгоритмов на объектах Java.

Answer 1

Простота .Java позволяет дизайнерам классов предоставлять свои собственные hashCode, что, как вы упоминаете, достаточно для "обычных" хеш-таблиц и может быть достаточно сложным для понимания.

Кроме того, когдаJava Collections API был разработан, и общие хеш-таблицы в стандартной библиотеке уже были достаточно смелыми.С никогда не было их.В C ++ они были в STL как hash_set и hash_map, но они не вошли в стандарт.Только теперь, в C ++ 0x, хеш-таблицы снова рассматриваются для стандартизации.

Answer 2

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

Вот идея о том, что делать:

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