Как видно из заголовка, это вопрос о детализации реализации из HashMap#resize - того, когда внутренний массив удваивается по размеру.
Это немного многословие, но я действительно пытался доказать, что я лучше всего это понял...
Это происходит в тот момент, когда записи в этом конкретном ведре /bin хранятся в модуле Linked, поэтому имеют точный порядок и в контексте вопроса это важно.
Как правило, resize можно было бы вызывать и из других мест, но пусть смотреть только на этот случай.
Предположим, вы поместили эти строки в качестве ключей в HashMap (справа там hashcode после HashMap#hash) - это внутреннее повторное хеширование.) Да, они тщательно сгенерированы, а не случайны.
DFHXR - 11111
YSXFJ - 01111
TUDDY - 11111
AXVUH - 01111
RUTWZ - 11111
DEDUC - 01111
WFCVW - 11111
ZETCU - 01111
GCVUR - 11111
Здесь есть простой пример: последние 4 бита одинаковы для всех из них - это означает, что когда мы вставляем 8 из этих ключей (всего 9), они заканчиваются в одном и том же ведре; и на 9-м HashMap#put будет вызываться resize.
Итак, если в настоящее время в HashMap есть 8 записей (с одним из ключей выше), это означает, что на этой карте 16 кодов, а последние 4 бита ключа они определили, где находятся записи.
Мы помещаем девятый ключ. На данный момент TREEIFY_THRESHOLD попадает и вызывается resize. Буферы удваиваются до 32, а еще один бит от ключей решает, куда будет идти эта запись (так что теперь будет 5 бит).
В конечном итоге достигается эта часть кода (когда resize происходит):
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
На самом деле это не так сложно... что он делает, он разбивает текущий бит на записи, которые будет перемещать на другие ячейки и на записи, которые не будет перемещать на другие но останутся в этом наверняка.
И это на самом деле довольно умно, как это получается - через этот кусок кода:
if ((e.hash & oldCap) == 0)
Что это значит, проверьте, является ли следующий бит (5-й в нашем случае) нулевым - если это так, это означает, что эта запись останется там, где она есть; если он не будет двигаться с мощностью двух смещений в новом бункере.
И теперь, наконец, вопрос: тщательно отредактирован фрагмент кода в размере, чтобы он сохранял порядок записей в этом бункере.
Итак, после того, как вы поместите эти 9 ключей в HashMap, порядок будет следующим:
DFHXR -> TUDDY -> RUTWZ -> WFCVW -> GCVUR (one bin)
YSXFJ -> AXVUH -> DEDUC -> ZETCU (another bin)
Почему вы хотите сохранить порядок некоторых записей в HashMap. Заказ в Map действительно плох, как описано здесь здесь или здесь.
Заказ на карте действительно плохой [...]
Это не плохо, это (по академической терминологии). Что Стюарт Маркс написал по первой ссылке, которую вы опубликовали:
[...] сохраняют гибкость для будущих изменений в реализации [...]
Это означает, что (как я понимаю), что теперь реализация выполняется, чтобы сохранить порядок, но в будущем, если будет найдена лучшая реализация, он будет использоваться либо для сохранения порядка, либо нет.
Существуют две распространенные причины для поддержания порядка в ящиках, реализованных как связанный список:
Во-первых, вы поддерживаете порядок, увеличивая (или уменьшая) хэш-значение. Это означает, что при поиске в бине вы можете остановить, как только текущий элемент будет больше (или меньше, если применимо), чем поиск хэша.
Другой подход предполагает перемещение записей на передний (или ближе к передней) ковша при доступе или просто добавление их на передний план. Это подходит для ситуаций, когда вероятность того, что доступ к элементу будет высока, если он только что был достигнут.
Я посмотрел источник JDK-8 и, по-видимому, он (по крайней мере, по большей части) выполнил более позднюю пассивную версию более поздней версии (добавить к фронту):
http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashMap.java
Хотя верно, что вы никогда не должны полагаться на порядок итераций из контейнеров, которые не гарантируют этого, это не означает, что он не может быть использован для производительности, если он структурный. Также обратите внимание, что реализация класса находится в привилегированном положении, чтобы использовать детали его реализации формальным способом, которым не должен пользоваться пользователь этого класса.
Если вы посмотрите на источник и понимаете, как его реализовано и использует, вы рискуете. Если разработчик делает это, это другое дело!
Примечание: У меня есть реализация алгоритма, который в значительной степени опирается на хеш-таблицу под названием Hashlife. Это использует эту модель, имеет хэш-таблицу, которая имеет силу два, потому что (а) вы можете получить запись с помощью маскировки бит (& mask), а не деления, и (б) переосмысливание упрощено, потому что вы только каждый раз разархивируете 'хэш-бункеров.
Бенчмаркинг показывает, что алгоритм набирает около 20% путем активного перемещения паттернов к передней части их бина при доступе.
Алгоритм в значительной степени использует повторяющиеся структуры в клеточных автоматах, которые являются общими, поэтому, если вы видели образец, вероятность увидеть его снова высока.