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