Основы Java: анализ hashCode

Java задняя часть JVM алгоритм

Все классы в Java наследуются от класса Object, который имеет собственный метод, возвращающий hashCode.

public native int hashCode();

Роль hashCode и некоторые требования, которым он должен соответствовать, четко объяснены в комментариях к документации.

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

Требовать:

  1. Один и тот же объект Java на протяжении всего жизненного цикла программы. Хэш-код, возвращаемый этим объектом, должен быть таким же.
  2. При использовании метода equals, если два объекта оцениваются как равные, возвращаемый хэш-код должен быть одинаковым.
  3. При использовании метода equals, если два объекта оцениваются как разные, возвращаемый хэш-код должен быть другим.

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

Реализация в строке

Класс String также наследуется от класса Object, который переопределяет метод hashCode().

/** Cache the hash code for the string */
private int hash; // Default to 0

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

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

Цикл for вычисляет hashCode по следующей формуле: s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1].

Причины использовать 31

31 — простое число, также известное как простое число. Простые числа — это натуральные числа больше 1, которые делятся только на 1 и на себя.

Есть несколько причин для выбора 31:

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

  • 31 (2

Я полагаю, что многие студенты могут понять второй пункт, а теперь объясните первый пункт.

Перечислим простые числа в пределах 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.

Выберите три маленьких, средних и больших простых числа из простых чисел выше: 2, 31 и 97. Каждый член аналитической формулы s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] представляет собой число, умноженное на простое число квадратный срок . Итак, давайте вычислим каждое простое число в степени n и выберем n = 5. Тогда результат следующий:

простое число результат
2 2^5 = 32
31 31^5 = 28,629,151
97 97^5 = 8,587,340,257

Можно видеть, что значение hashCode, вычисленное по простому числу 2, является относительно небольшим значением, в то время как значение hashCode, рассчитанное по простому числу 97, является относительно большим значением, а 31 — относительно умеренным.

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

Для получения более подробной информации взгляните на этот вопрос в stackoverflow:Why does Java's hashCode() in String use 31 as a multiplier?

Алгоритм проектирования hashCode

В соответствии с пунктом 9 книги Effective Java, Second Edition, для классов, которые мы пишем сами, нам необходимо переопределить метод hashCode при переопределении метода equals. Причина была указана ранее.

Итак, как спроектировать алгоритм hashCode, алгоритм разработан в книге:

  1. Сохраните некоторое ненулевое постоянное значение, например 17, в переменной типа int с именем result.
  2. Для каждого поля в объекте выполните следующие действия:
    • Вычислите хеш-значение c типа int для поля:
      • Если поле имеет логический тип, оценивает (f?1:0)
      • Если поле имеет тип byte, char, short или int, вычисляет (int)f
      • Если поле имеет тип long, вычислить (int)(f^(f>>>32))
      • Если поле имеет тип float, вычисляет Float.floatToIntBits(f)
      • Если поле имеет тип double, вычислите Double.doubleToLongBits(f) и повторите третий шаг.
      • Если поле является ссылкой на объект и метод equals класса сравнивает поле, рекурсивно вызывая метод equals, он также рекурсивно вызывает hashCode для поля и возвращает 0, если поле имеет значение null.
      • Если поле представляет собой массив, обработайте каждый элемент как отдельное поле, рекурсивно примените приведенные выше правила и используйте метод Arrays.hashCode, если важен каждый элемент в поле массива.
    • Объедините хэш-код c, рассчитанный на шаге 2.1 выше, в результат по формуле результат = 31 * результат + с.
  3. вернуть результат

Ссылаться на

Популярная наука: почему метод String hashCode выбирает число 31 в качестве множителя

Why does Java's hashCode() in String use 31 as a multiplier?

«Эффективная Java»

Категории