Какие проблемы с коллизиями и выделением памяти могут возникнуть при создании очень большой строки в JVM

Что проверяют

Знаете ли вы, как строка устроена в памяти и что происходит, когда она перерастает обычные объекты. Слово «коллизии» здесь проверяет понимание hashCode() у строк. Следом обычно спрашивают, как собрать строку на сотни мегабайт и не упасть.

Как отвечать

Про память:

• устройство: с Java 9 строка хранит byte[] с флагом кодировки (Compact Strings). Символы Latin-1 занимают байт, но один символ вне этого набора, например кириллица, переводит всю строку в UTF-16, и объём удваивается;
• предел длины: массив индексируется int, поэтому потолок около 2 млрд байт, а в UTF-16 символов вдвое меньше. Запрос массива больше лимита VM даёт OutOfMemoryError даже при свободной куче;
• рост StringBuilder: при нехватке места он выделяет массив примерно вдвое больше и копирует старый. В момент копирования в памяти оба массива, а toString() делает ещё одну копию. Если размер известен, задайте ёмкость в конструкторе;
• humongous-объекты в G1: массив больше половины региона кладётся сразу в старое поколение в несколько смежных регионов. Отсюда фрагментация, лишние циклы сборки и даже Full GC при свободной, но разрозненной памяти.

Про коллизии:

• hashCode(): считается по всем символам один раз и кэшируется в поле объекта. Для гигантской строки первый вызов линейный, а equals() при совпадении хэша и длины сравнивает содержимое целиком;
• подбор коллизий: полиномиальный хэш с множителем 31 легко обмануть, "Aa" и "BB" дают одно значение. С Java 8 HashMap превращает переполненную корзину в дерево, и для Comparable-ключей вроде строк худший случай становится O(log n).

Лучшее решение обычно в том, чтобы не держать всё в одной строке: писать в Writer или поток, читать файл построчно.

Где спотыкаются

Советуют «положить в пул строк» через intern(). Для огромной уникальной строки это лишняя запись в таблице строк, повторного использования не будет.

Повторяют устаревшее про утечку через substring(). С Java 7u6 подстрока копирует свой кусок и не держит исходный массив.

Предлагают ConcurrentHashMap как защиту от коллизий. Он решает многопоточность, а не качество хэша.