Математические принципы философии HashMap

Java исходный код
Математические принципы философии HashMap

Сегодня я поговорил с группой друзей о точках знаний HashMap, что очень приятно. Однако из-за боязни обобщений его трудно четко изложить в нескольких словах. К счастью, даже Зай, состав Юнчжи.
В этой статье не будет объясняться структура данных HashMap. Просто объясните математические принципы, используемые в HashMap.

tableSizeFor

Обычно первая проблема, с которой сталкиваются, это tableSizeFor().

Позвольте мне объяснить, что делает эта часть кода: вычисляет первую степень n числа 2, которая больше или равна cap. Уведомление:

  • Прежде чем шапка будет участвовать в расчете, нужно сначала -1
  • Понять правила работы >>>, |

Приблизительный смысл его алгоритма состоит в том, чтобы сначала беззнаковый сдвиг вправо m бит, а затем выполнить операцию | над результатом, полученным с исходным значением. Например, если установить cap=19, то n=18, двоичное представление равно 10010, а беззнаковый сдвиг вправо равен 1001 после 1 бита. Если это 16 бит, это выражается как: 0000 0000 0001 0010, а затем с исходным значением 0000 0000 0000 1001 и результатом является: 0000 0000 0001 1011 Следующие раунды могут быть выведены и так далее.
Подробный процесс расчета выглядит следующим образом:

Результат приведенного выше расчета — 11111, что соответствует 31 в десятичном виде.

return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

n Используя операции сдвига и или, проблема аккуратно упрощается. Обратите внимание, что здесь есть деталь шапка-1, зачем это делать. Предполагая, что x = 2 ^ n, если мы не обработаем результат 2 * 2 ^ n, это не соответствует требованиям. Первое значение, большее или равное x, должно быть самим x. Если не верите мне, можете проверить.

hash

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

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : 
    // 我们看最后一行作用
    (h = key.hashCode()) ^ (h >>> 16);
}

JDK объяснил это соответствующим образом.

Computes key.hashCode() and spreads (XORs) higher bits of hash

Дословный перевод:Вычислить key.hashCode() и расширить старшие биты хеша
Необходимо задуматься: почему приходится тратить много времени на выполнение операции сдвига XOR после получения hashCode ключа. Предположим, мы не возмущаемся, какой эффект это может иметь? Мы знаем, что определение позиции элемента в массиве в HashMap достигается операцией &.

if ((p = tab[i = (n - 1) & hash]) == null)

Когда hashCode ключа достаточно велик, а емкость текущего HashMap недостаточно велика, обнаружили ли вы, что важное решение о местонахождении ключа на самом деле остается за несколькими последними.
Предположим, что текущая емкость равна 16, тогда (n - 1) = 15, что фактически равно 1111 в двоичном формате. Независимо от того, сколько битов в хеше, я могу просто дополнить 0, если этого недостаточно. В это время возникла очень неловкая ситуация. Мне все равно, сколько цифр вашего хэш-кода, просто выполните операцию со мной 1111, за исключением того, что последние четыре цифры всегда равны 0. То есть в хеше вроде бы достаточно цифр, но на самом деле играет роль только последняя часть.Таким образом, два хэша должны быть согласованы только в нижней позиции, и независимо от того, насколько отличается верхняя позиция, они должны быть расположены в одном и том же месте в конце..
Это, очевидно, результат, который автор исходного кода не хочет видеть. На самом деле старшие биты участвуют здесь в операции, чтобы разрушить младшие биты. Таким образом, высокая позиция отличается, низкая позиция одинакова, и тупиковая ситуация, заключающаяся в том, что позиционирование должно быть одинаковым, будет разорвана напрямую.

Секрет емкости

Мы знаем, что HshMap расширяется в два раза по сравнению с исходной емкостью, а начальная емкость равна 16, поэтому емкость ta всегда будет 2^n. Число 2^n в двоичном формате очень характерно. После преобразования в двоичный формат первый бит равен 1, а остаток равен 0.Тогда после 2^n - 1 полученные результаты более регулярны, и необходимо получить расположение всех единиц.
Пожалуйста, помните, что любое число -1 получает перестановку всех единиц, тогда число должно быть 2 ^ n

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,  boolean evict)
    n = (tab = resize()).length;
    (n - 1) & hash

Если вы хотите найти в методе put(), вам действительно нужно вычислить оставшуюся часть текущей емкости после получения хэша ключа. Но избыток более требователен к производительности в компьютерном мире. Мы можем преобразовать хеш% n в (n - 1) & хеш.
Правило работы & состоит в том, что все 1 дают 1, а остальные 0.
Пусть значение хэша равно a b c d, значение (n - 1) равно m n x y, а диапазон значений вышеуказанных переменных равен [0, 1].
Результатом операции & является t x y z. В наиболее совершенном случае каждый бит четырехзначного числа может быть равен 0 или 1, поэтому существует 2 * 2 * 2 * 2 = 16 видов перестановок. Продолжим считать, что если m n x y имеет число, равное 0? Осталось всего 2 * 2 * 2 = 8 видов перестановок. Если есть два 0, остается только 2 * 2 = 4 вида перестановок.
Эта теория немного скучновата. Потому что мы точно знаем текущую емкость. Если n = 1110, n - 1 = 1101, что означает, что при длине вашего массива 14 будет только 8 видов перестановок, тогда это соответствует проблеме позиционирования HashMap, то есть когда длина массива 14, есть позиции 6. навсегда впустую. Если есть такое большое количество отходов, это неизбежно приведет к частому расширению HashMap и потере производительности.
Как это решить? Как сделать так, чтобы можно было найти все позиции, соответствующие приведенной выше математической модели, решение на самом деле (n - 1) все биты должны быть равны 1.
Тогда, если (n - 1), все биты должны быть равны 1. Тогда выполняется n = 2^x.

Секреты расширения

if ((e.hash & oldCap) == 0)
newTab[j] = loHead;
newTab[j + oldCap] = hiHead;

Здесь я был в растерянности, когда смотрел на это, пока не обнаружил, что (e.hash & oldCap) не (e.hash & (oldCap - 1)) эти два мира друг от друга. Смысл этого кода здесь в том, чтобы определить, равно ли значение старшего бита oldCap, соответствующего соответствующей позиции e.hash, 1.
Это очень важно, потому что если соответствующая позиция равна 1, это прямо означает, что та должна двигаться, а куда двигаться? К исходной емкости добавляется число, соответствующее исходной позиции массива. Если это 0, просто оставайтесь на месте. На самом деле, пока двоичный код и математика хороши, он должен реагировать мгновенно.
После расширения (e.hash & (newCap - 1)) роль может играть только бит e.hash, соответствующий старшему биту newCap. Старший бит newCap равен 0 и не влияет на результат, за которым следует by (т.е. результат hash & (oldCap - 1)) точно такой же и не влияет на результат. Я до сих пор не понимаю, поэтому украду картинку:

Если вы не понимаете, давайте продемонстрируем алгебраически:
Предполагая, что исходная мощность n = 10000, n - 1 = 1111
Предположим, что key.hash = 10001
Тогда позиция ta равна 1
Затем разверните
Теперь n=100000, n - 1 = 11111.
Тогда местоположение ta равно 10001.

Простите, название отдает дань уважения Ньютону...

Категории