Можно ли с помощью hashCode возвращать разные значения между разными запусками?

Question

Я пытаюсь узнать полную историю hashCode. В большинстве реализаций hashCode является полностью детерминированным, как в StringUTF16 классе:

public static int hashCode(byte[] value) {
    int h = 0;
    int length = value.length >> 1;
    for (int i = 0; i < length; i++) {
        h = 31 * h + getChar(value, i);
    }
    return h;
}

Я думаю, что такая реализация не велика: легко создавать примеры с одинаковым hashCode. Например, пользователь системы может отправить в точности слова с одинаковыми hashCode для атаки DOS. Он не работает с String, так как он реализует Comparable (а HashMap - взломанный беспорядок), но не поможет с классами, которые не реализуют Comparable.

Кажется, что лучший подход использует случайный фактор (вместо 31), так что пользователь не знает, как создавать плохие примеры (и у него также есть некоторые теоретические свойства), например:

class ImmutableArray{
    // Note static keyword. It guarantees that for the same run all objects use the same x.
    private static final int x = generateRandomPrime();

    int[] values;

    public int hashCode() {
        int res = 5;
        for (int v : values) {
            res = res * x + v;
        }
        return res;
    }

    ...

}

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

Answer 1

НЕ требуется, чтобы hashCode давал одинаковые значения в разных JVM.Например, класс HashMap не сохраняет значения hashCode ключей карты при сериализации.Вместо этого значения hashCode пересчитываются при десериализации карты.

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

Но если вы реализуете ленивый hashCode расчет, вам потребуется , чтобы объявить поле, в котором вы его хранитекак transient.В противном случае значение hashCode в экземпляре с удаленным ключом не будет == значением hashCode, вычисленным для другого экземпляра, который "равен" ключу.(Другими словами, контракт хэш-кода / равно не работает!) Это приведет к ошибке поиска.

Если вы сделаете это правильно, не должно быть проблем с сериализацией HashMap.Например, вы можете использовать подход String::hashCode и использовать ноль в качестве кэшированного значения hashCode, что означает «код должен быть рассчитан» для метода hashCode().

^{(ЕслиВаш ключевой класс не имеет поля для хранения кэшированного значения hashCode, проблема с сохранением этого значения не возникает.)}

---

Еще одна вещь, на которую следует обратить внимание: модификация класса ключей для реализации Comparable будет еще одной защитой от атак на DOS.В вашем примере класса реализация метода compareTo проста.Обратите внимание, что порядок, который вы реализуете, не должен быть семантически значимым.Он просто должен быть стабильным и последовательным.

Answer 2

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

Хотя с помощью «хитрости» отражения вы могли бы потенциально изменить значение и вывести всю систему из колеи (подумайте setAccessible и флаги модификаторов).

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