Написание методов hashCode для гетерогенных ключей

Question

У меня есть Java HashMap, чьими ключами являются экземпляры java.lang.Object, то есть: ключи имеют разные типы. Значения хэш-кода двух ключевых объектов разных типов, вероятно, будут одинаковыми, если они содержат одинаковые значения переменных.

Чтобы улучшить производительность метода get для моего HashMap, я склонен смешивать имя типа Java с методами hashCode моих ключевых объектов. Я не видел примеров этого в другом месте, и поэтому моя эта мощная тревожная тревога исчезла. Считаете ли вы, что смешивание типа с hashCode - хорошая идея? Должен ли я смешивать имя класса или хэш-код соответствующего объекта класса?

Answer 1

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

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

Как и Джона, производительность хэш-карты улучшается за счет уменьшения коллизий. Смешивание в имени типа так же увеличивает вероятность столкновений, как и их уменьшение. Чтобы сохранить хешмап в максимальном состоянии, вы хотите, чтобы вероятность того, что какой-либо конкретный хэш-код будет примерно такой же, как и любая другая, в области допустимых значений ключа. Таким образом, вероятность хэш-кода 10 должна быть примерно такой же, как вероятность 100 или любого другого числа. Таким образом, ведра таблиц хэш-таблицы заполняются равномерно (по всей вероятности). поэтому не имеет значения, есть ли у вас объект типа A или типа B. просто распределение вероятностей хэш-кодов всех возникающих значений ключа.

Answer 2

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

Прежде чем вы беспокоитесь об этом слишком много, вы действительно измерили, насколько часто вы находитесь действительно получать столкновений с реальными данными? Это определенно проблема, или вы просто обеспокоены тем, что это может быть проблема может?

Answer 3

лет спустя ...

Помимо того, что это преждевременная оптимизация, это не плохая идея, и накладные расходы ничтожны. Рекомендация Чоя в отношении профиля сначала, безусловно, хороша в целом, но иногда простая оптимизация занимает гораздо меньше времени, чем профилирование. Это похоже на такой случай.

Я бы использовал другой множитель, как уже было предложено, и смешать в getClass().getHashCode().

^{Или, может быть getClass().getName().getHashCode() она остается последовательной через JVM вызовы, которые могут быть полезны, если вы хотите, воспроизводимый HashMap итерационного порядка для облегчения отладки. Обратите внимание, что вы никогда не должны полагаться на такую ​​воспроизводимость и что существует немало вещей, разрушающих ее.}