Почему HashMap использует длину минус 1 для расчета индекса?

Question

Я анализирую исходный код HashMap в jdk7 , и я обнаружил, что когда мы вызываем put() метод для добавления элементов, он будет использовать indexFor() для рассчитать индекс и сохранить элемент в массиве, метод указан ниже:

Теперь мне интересно, почему он использует h & (length-1) для получения индекса? Используется ли для получения большего индекса случайного массива? Можем ли мы использовать length или length-2 (если существует) вместо этого?

Может кто-нибудь помочь мне понять это? Заранее спасибо!

static int indexFor(int h, int length) {
    // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
    return h & (length-1);
}

Answer 1

Используется ли он для получения большего индекса случайного массива?

Нет

Можем ли мы вместо этого использовать length или length-2 (если существует)?

Нет

Это всего лишь математический трюк.Чтобы сопоставить ваш хэш с диапазоном [0, L), вы вычисляете hash % L.Деление может быть дорогостоящим, поэтому разработчики решили воспользоваться тем, как числа хранятся в двоичном виде.Это работает только для степеней двух, потому что установлен только один бит, вычитание одного устанавливает все менее значимые биты и сбрасывает исходный бит.Двоичное-И-это для нашего хэша имеет тот же результат, что и вычисление по модулю, каждый бит, который является более значимым, чем мы можем обработать, просто сбрасывается.