О целочисленном умножении, переполнении и потере информации

Question

Я читаю главу 3 Effective Java Джошуа Блоха.В Элемент 8: Всегда переопределять hashCode, когда вы переопределяете равный , автор использует следующий шаг объединения в своей функции хеширования:

result = 37 * result + c;

Затем он объясняет, почему было выбрано 37 (выделение добавлено):

Множитель 37 был выбран, потому что это нечетное простое число. Если бы оно было четным и умножение было переполнено, информация была бы потеряна, потому что умножение на два эквивалентно сдвигу. Преимущества использования простого числа менее очевидны, но для этой цели традиционно используют простые числа.

Мой вопрос: почему имеет значение, что коэффициент объединения (37) равен нечетно ?Не приведет ли переполнение умножения к потере информации независимо от того, был ли коэффициент нечетным или четным?

Answer 1

Рассмотрим, что происходит, когда положительное значение многократно умножается на два в представлении base-2 - все установленные биты в конечном итоге идут с конца, оставляя вас с нулем.

Четный множитель приведет к хеш-кодам с меньшим разнесением.

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

Answer 2

Цель хэш-кода - иметь случайные биты, основанные на входе (особенно младшие биты, так как они часто используются чаще)

При умножении на 2 младший бит может быть только 0, чего не хватает случайности. Если вы умножаете на нечетное число, младший бит может быть нечетным или четным.

---

Похожий вопрос: что вы получаете здесь

public static void main(String... args) {
    System.out.println(factorial(66));
}

public static long factorial(int n) {
    long product = 1;
    for (; n > 1; n--)
        product *= n;
    return product;
}

печать

0

Каждое второе число является четным, а каждое четвертое кратным 4 и т. Д.

Answer 3

Решение заключается в теории чисел и наименьшем общем знаменателе вашего множителя и вашего числа по модулю.

Пример может помочь. Допустим, вместо 32 бит у вас есть только 2 бита для представления числа. Итак, вы получили 4 номера (классы). 0, 1, 2 и 3

Переполнение в ЦП аналогично операции по модулю

Class - x2 - mod 4 - x2 - mod 4

0       0      0     0     0

1       2      2     4     0

2       4      0     0     0

3       6      2     4     0

После 2 операций у вас остался только 1 возможный номер (класс). Итак, вы «потеряли» информацию.

Class - x3 - mod 4 - x3 - mod 4 ...

0       0      0     0     0

1       3      3     9     1

2       6      2     6     2

3       9      1     3     3

Это может продолжаться вечно, и у вас все еще есть 4 класса. Таким образом, вы не теряете информацию.

Ключ в том, что LCD вашего умножителя и вашего класса по модулю равен 1. Это справедливо для всех нечетных чисел, потому что ваше число по модулю в настоящее время всегда равно 2. Они не должны быть простыми числами и не должны быть 37 конкретно. Но потеря информации - это всего лишь один из критериев выбора 37 других критериев: распределение значений и т. Д.

Answer 4

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

Поскольку модуль для двоичной арифметики всегда является степенью двойки, любое нечетное число относительно простое и будет достаточным.Однако если бы вы взяли модуль, отличный от переполнения, простое число продолжало бы обеспечивать разнообразие (при условии, что вы не выбрали одно и то же простое число ...).

Answer 5

Нематематическая простая версия того, почему ...

Простые числа используются для хеширования, чтобы сохранить разнесение.

Возможно, разнесение является более важным из-за реализаций Set и Map.Эти реализации используют последние биты хэш-номеров объектов для индексации внутренних массивов записей.

Например, в HashMap с внутренней таблицей (массивом) для записей размером 8 он будет использовать последние 3 бита хеш-номеров для адресациизапись таблицы.

    static int indexFor(int h, int length) {
        return h & (length-1);
    }

На самом деле это не так, но если объект Integer будет иметь

    hash = 4 * number;

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

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