В чем разница между hash ()% n и n% hash ()

Question

Во многих книгах, учебных программах, учебных пособиях я видел, что хороший вариант найти правильную ячейку предмета - это вычислить номер ячейки: item.hash()%(n-1) = # of the bucket.

Но почему упоминается это определенное выражение?

Чем отличается обратный (n-1)%item.hash() = # of the bucket от него?

P.S. Я знаю, что Java HashMap использует (n - 1) & hash, я хотел бы только уловить разницу в разборе ключа между этими двумя подходами.

Answer 1

Представьте модуль оператора % как способ равномерно распределить набор чисел через , уменьшив их в меньшем диапазоне. Набор чисел, конечно же, хеш-коды клавиш ввода. Небольшой диапазон - вместимость стола.

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

Обратная операция звучит довольно странно (и бесполезно): принимая во внимание, что хэш-коды являются большими числами, а n - маленьким, n % hash будет всегда возвращать n, так что он вообще не интересен.

Java выбирает индексы через hash & (length-1), что на самом деле не является арифметически эквивалентным hash % length, но это альтернатива - и дешевле, чем формула - формула для сокращения и распределения (кредиты @Zabuza).

Answer 2

Разница между hash % n против n % hash заключается в том, что hash % n будет гораздо более распределенным, чем n % hash.

n % hash почти всегда будет эквивалентно n, потому что a % b, где b > a равно a (например, 15 % 30 = 15).

Я создал график, чтобы показать различия (красный x % n и синий n % x, где x представляет хэш).

Идея в java состоит в том, чтобы избежать операции ' дорогой ' % (мод) и вместо этого выполнить сравнительно дешевую операцию & (и). Но это работает только тогда, когда n является степенью 2. Таким образом, Java HashMap всегда использует степень 2 для количества сегментов.

Answer 3

Чем отличается обратный (n-1)% item.hash () = # сегмента от него?

В основном это не работает.

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

Но «обратная» функция этого не делает. Поэтому, если вы попытаетесь использовать его, (предполагаемые) подписки сегмента будут давать исключения, поскольку h% (n - 1)> (n - 1) или <0 для большинства значений h в диапазоне типа Java <code>int.

Поскольку @Zubuza отмечает остаток (%) и деление (/) не являются коммутативными.