Java 20: новый костыль в HashMap
На вопрос выше логично ответить
Итак, что происходит внутри HashMap?
Ячейки хэш-таблицы (или бакеты) хранятся в переменной
При вызове
Кажется, что всё в порядке, но мы забыли про ребалансировку😒
HashMap хорошо работает, когда в каждом бакете 0 или 1 элемент. Тогда скорость поиска и добавления будет той самой О(1).
Когда элементов становится больше, растёт шанс, что в один бакет попадёт несколько элементов. Поэтому в определённый момент HashMap удваивает количество бакетов и перераспределяет элементы. За момент, когда пора начать эту операцию, отвечает поле
Его первое значение считается как [планируемое число элементов * 0.75], т.е когда HashMap заполнен на 3/4. При удвоении числа бакетов threshold тоже удваивается.
И смотрите, что получается:
🔹 Мы хотим добавить в мэп 1000 элементов и вызываем конструктор с подходящим параметром initialCapacity:
🔹 Рассчитывается threshold: 1024*0,75 = 768
🔹 Добавляется 768 элементов
🔹 Приходит 769 элемент, начинается ребалансировка:
▫️ количество бакетов удваивается, теперь их 2048
▫️ текущие элементы распределяются между ними
▫️ новый threshold удваивается, теперь это 1538
Что получилось: мы пообещали добавить в HashMap 1000 элементов. Сдержали обещание, но перестройка мэп всё равно произошла.
Чтобы HashMap работал оптимально, нужно учесть ребалансировку и передать в конструктор, например, 1500. Надо знать детали реализации, чтобы получить то, что хотим.
И это образцовое нарушение инкапсуляции🤌
В java 20 в HashMap добавили костыльный метод, который исправляет ситуацию:
Почему это костыль? Потому что исходная проблема не решается. Жизнь пользователя не становится легче, ему нужно запомнить "чтобы задать размер мэп — не пользуйся конструктором, пользуйся специальным методом".
Хороший API — понятный, удобный и дружелюбный. Пользователю легко выбрать нужный метод, все параметры хорошо описаны в документации. Когнитивная нагрузка при использовании минимальна, нет подводных камней и обходных путей. Для собеседований сложно придумать вопрос с подвохом🙂
Важные заметки:
🔸 В JDK много образцового кода, и я рекомендую изучать исходники как можно чаще. HashMap — неприятное исключение
🔸 В ConcurrentHashMap всё хорошо.
На вопрос выше логично ответить
new HashMap<>(1000). Сначала расскажу, почему этот ответ не походит. Потом наглядно покажу нарушение инкапсуляции, и что за костыль добавили в Java 20.Итак, что происходит внутри HashMap?
Ячейки хэш-таблицы (или бакеты) хранятся в переменной
Node[] table как простой массив.При вызове
new HashMap() без параметров создаётся 16 бакетов. Если передать параметр с размером, то берётся ближайшая степень двойки. new HashMap(1000) создаёт массив из 1024 элементов.Кажется, что всё в порядке, но мы забыли про ребалансировку😒
HashMap хорошо работает, когда в каждом бакете 0 или 1 элемент. Тогда скорость поиска и добавления будет той самой О(1).
Когда элементов становится больше, растёт шанс, что в один бакет попадёт несколько элементов. Поэтому в определённый момент HashMap удваивает количество бакетов и перераспределяет элементы. За момент, когда пора начать эту операцию, отвечает поле
threshold.Его первое значение считается как [планируемое число элементов * 0.75], т.е когда HashMap заполнен на 3/4. При удвоении числа бакетов threshold тоже удваивается.
И смотрите, что получается:
🔹 Мы хотим добавить в мэп 1000 элементов и вызываем конструктор с подходящим параметром initialCapacity:
new HashMap(1000);
🔹 Создаётся 1024 бакета (ближайшая степень двойки)🔹 Рассчитывается threshold: 1024*0,75 = 768
🔹 Добавляется 768 элементов
🔹 Приходит 769 элемент, начинается ребалансировка:
▫️ количество бакетов удваивается, теперь их 2048
▫️ текущие элементы распределяются между ними
▫️ новый threshold удваивается, теперь это 1538
Что получилось: мы пообещали добавить в HashMap 1000 элементов. Сдержали обещание, но перестройка мэп всё равно произошла.
Чтобы HashMap работал оптимально, нужно учесть ребалансировку и передать в конструктор, например, 1500. Надо знать детали реализации, чтобы получить то, что хотим.
И это образцовое нарушение инкапсуляции🤌
В java 20 в HashMap добавили костыльный метод, который исправляет ситуацию:
HashMap.newHashMap(1000);
Внутри произойдёт вычисление 1000 / 0.75 = 1334, в итоге создаётся 2048 бакетов.Почему это костыль? Потому что исходная проблема не решается. Жизнь пользователя не становится легче, ему нужно запомнить "чтобы задать размер мэп — не пользуйся конструктором, пользуйся специальным методом".
Хороший API — понятный, удобный и дружелюбный. Пользователю легко выбрать нужный метод, все параметры хорошо описаны в документации. Когнитивная нагрузка при использовании минимальна, нет подводных камней и обходных путей. Для собеседований сложно придумать вопрос с подвохом🙂
Важные заметки:
🔸 В JDK много образцового кода, и я рекомендую изучать исходники как можно чаще. HashMap — неприятное исключение
🔸 В ConcurrentHashMap всё хорошо.
new ConcurrentHashMap(1000) сразу создаёт 2048 бакетов и не занимается лишними балансировками