предисловие
Все мои статьи обновляются синхронно с Github--Java-Notes, Если вы хотите узнать о JVM, анализе исходного кода HashMap, весне и решении проблемы с предложением (версия Java), вы можете нажать звездочку. Вы можете увидеть мою домашнюю страницу на github, которая обновляется каждый день.
Приглашаю вас завершить репо со мной
иметь ввиду
Первое, что вы должны помнить:Независимо от того, передаете ли вы параметры или нет, независимо от того, какую длину вы передаете, при использовании HashMap его длина равна 2 в n-й степени, а максимальная длина составляет 2 в 30-й степени.
Максимальная длина
В исходном коде HashMap постоянное значение максимальной длины определяется так
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
Где используется это значение?
- функция resize(), она используется для расширения
- tableSizeFor(), это также используется для расширения
- в конструкторе
- putEntries(), при сохранении группы элементов HashMap, а не одного
Почему длина таблицы должна быть 2 в энной степени
Обратите внимание, что в исходном коде они используютленивая операция инициализации, то есть таблица инициализируется только тогда, когда она используется, если вы неputДля других операций длина таблицы всегда равна нулю.
В основном есть две функции, которые гарантируют его длину в энной степени двойки.
- tableSizeFor()
- resize()
Что касается процесса расчета и процесса загрузки, пожалуйста, обратитесь к этой моей статье:Какая длина стола
В этой статье я анализирую процесс создания таблицы из исходного кода, включая вызовы функций, о которых говорилось выше, после прочтения вы должны понять, почемуtableДлина должна быть 2 в энной степени
Конечно, на github есть и китайские комментарии к той части исходного кода, которую я написал для hashMap:Китайская аннотация исходного кода HashMap
В чем преимущество n раз по 2
- легко рассчитать
- Распределение хеша более равномерное
равномерно распределены
Если это не 2 в энной степени, то некоторые позиции никогда не используются
Для получения дополнительной информации, пожалуйста, обратитесь к этому сообщению в блоге, он использует пример, чтобы рассказать, почему,Почему длина должна быть равна 2 в энной степени?
легко рассчитать
-
Когда емкость должна быть 2 ^ n, h & (length - 1) == h % длины
-
Очень удобно рассчитать новое местоположение после расширения по сравнению с JDK1.7.
Изменения JDK 1.8
В JDK1.8 HashMap сильно изменился, в том числе
-
Алгоритм миграции элементов (из старого в новый массив)
-
Используйте красно-черное дерево
-
Связанный список - это хвостовая вставка
Среди них я остановлюсь на алгоритме миграции элементов, когда JDK1.8
Сначала посмотрите на код Java и мои комментарии, если вы хотите увидеть полный,Вы можете увидеть мой репозиторий на github
// 将原来数组中的所有元素都 copy进新的数组
if(oldTab != null){
for (int j = 0; j < oldCap; j++) {
Entry e;
if((e = oldTab[j]) != null){
oldTab[j] = null;
// 说明还没有成链，数组上只有一个
if(e.next == null){
// 重新计算 数组索引 值
newTable[e.h & (newCap-1)] = e;
}
// 判断是否为树结构
//else if (e instanceof TreeNode)
// 如果不是树，只是链表,即长度还没有大于 8 进化成树
else{
// 扩容后，如果元素的 index 还是原来的。就使用这个lo前缀的
Entry loHead=null, loTail =null;
// 扩容后 元素index改变，那么就使用 hi前缀开头的
Entry hiHead = null, hiTail = null;
Entry next;
do {
next = e.next;
//这个非常重要，也比较难懂，
// 将它和原来的长度进行相与，就是判断他的原来的hash的上一个 bit 位是否为 1。
//以此来判断他是在相同的索引还是table长度加上原来的索引
if((e.h & oldCap) == 0){
// 如果 loTail == null ,说明这个 位置上是第一次添加，没有哈希冲突
if(loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else{
if(hiTail == null)
loHead = e;
else
hiTail.next = e;
hiTail = e ;
}
}while ((e = next) != null);
if(loTail != null){
loTail.next = null;
newTable[j] = loHead;
}
// 新的index 等于原来的 index+oldCap
else {
hiTail.next = null;
newTable[j+oldCap] = hiHead;
}
}
}
}
}
Мы видим последнее предложение исходного кода выше,
newTable[j+oldCap] = hiHead;Это означает, что даже если наши элементы будут перенесены из старого массива в новый массив, нам не нужно пересчитывать сумму его хеша и длину нового массива.索引值+原来数组的长度Просто
Синий означает, что не нужно двигаться, зеленый означает, что нужно пересчитать индекс, мы видим, что он только что добавил 16 (исходная длина таблицы массива)
нужно рассчитать показатель
Мы заметили, что в приведенном выше исходном коде мы использовали это суждение, когда оценивали, нужно ли изменить положение элемента после раскрытия.
if((e.h & oldCap) == 0),
Если он равен 0, то менять не нужно, достаточно использовать старый индекс, если равен 1, то нужно использовать новый индекс
Почему это так?
- Если индекс элемента должен измениться, то
hash&(newTable.length-1)должно быть сhash&(oldTable.length-1)+oldTable.lengthравный - Поскольку длина таблицы должна быть n-й степенью 2, то есть oldCap должен быть n-й степенью 2, то есть oldCap имеет один и только один бит равен 1, и эта позиция находится в самом старшем должность;
Возьмем пример:
Мы предполагаем, что последние 12 бит хеш-значения элемента равны 110111010111, исходная длина массива равна 16, а длина массива после расширения равна 32.
Вы можете попробовать при следующем расширении, и индекс не изменится при расширении до 64. Конечно, ответ в том, что он не изменится, потому что хэш-значение элемента равно 0 в этой позиции.
По сравнению с расширением 1.7
Давайте сравним способ JDK1.7, Если он хочет расширить емкость и вычислить индекс элемента после расширения, ему нужно использоватьindexFor函数
/**
* Returns index for hash code h.
*/
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);
}
То есть более хлопотно и неэлегантно снова сравнивать хеш-значение элемента с новой длиной массива -1.