HashMap в Java 8.

О работе HashMap спрашивают и джуниоров, и сеньоров. Часто всё сводится к рассказу о бакетах и оценке сложности на базе статей 1998 года. С тех времён много изменилось. Этот пост о текущей структуре, особенностях и недостатках HashMap.

❓Как устроен HashMap?
В основе HashMap лежит массив начальных элементов, которые называют бакетами. Их количество зависит от количества элементов — подбирается ближайшая степень двойки. Если элементов 20, то создаётся 32 бакета.
Если хэш-функция ключа распределяет значения равномерно, то в каждом бакете будет 0 или 1 элемент.
На практике такое происходит редко, и значения хэшей элементов иногда совпадают. Тогда элементы с одинаковым хэш кодом организуются в список. Если их становится больше 8, то элементы перестраиваются в двоичное дерево.

❓Как определяется нужный бакет?
Популярное заблуждение - по остатку деления хэша на количество бакетов. Это не совсем так. Количество бакетов кратно степени двойки, и при вычислении используется логическое И.
В массиве из 16 бакетов последний элемент имеет номер 15, в битовом представлении это 1111. Операция & оставит последние 4 бита числа.
Сравним:

hash % 16
hash & 15

Результат будет одинаковый, но логическое И выполняется в 2 раза быстрее. Вычисление бакета — частая операция в HashMap, и такая микрооптимизация даёт хороший прирост в производительности.

❓Что такое load factor и зачем он нужен?
HashMap быстро работает, когда в бакете 0 или 1 элемент. При добавлении элементов повышается шанс, что в одном бакете их будет несколько, a HashMap станет менее эффективен. Поэтому HashMap периодически расширяется. Параметр load factor определяет, когда это происходит. По умолчанию равен 0.75.
Пример: в HashMap 20 элементов и 32 бакета. Когда элементов будет 32*0.75=24, количество бакетов удвоится и элементы перераспределятся по ним.

❓Какие недостатки у HashMap?
1️⃣ Cильная зависимость от функции распределения хэшей.
2️⃣ Неэкономный расход памяти. При load factor = 0.75 будет пустовать 25% памяти. При неравномерном распределении хэшей — ещё больше.

❓В конструкторе HashMap проставляются свойства, а массив бакетов создаётся только при первой вставке. Зачем нужна ленивая инициализация?
Расширение HashMap — долгая операция. Когда добавляется набор элементов, можно сразу увеличить массив до необходимого размера. Очень популярный случай - когда в пустой HashMap добавляютcя элементы другой map:

Map result=new HashMap();
...
result.putAll(anotherMap);

Если бы внутренняя структура result создавалась в конструкторе, пришлось бы тут же её расширять. С отложенной инициализацией можно этого избежать.

А теперь разберём вопрос про порядок элементов:
✅ Обход HashMap происходит последовательно - бакет за бакетом. Поэтому задание сводится к определению бакетов, в которые попадут значения. Это и будет порядок вывода элементов:

10 % 16 = 10
20 % 16 = 4
30 % 16 = 14

Ответ: 20 10 30

​Вопрос на закрепление: в каком порядке выведутся ключи, если задать HashMap размер 100?

Кодировки: основы.

Компактные строки - важное обновление в java 9. Чтобы лучше понять проблему и новое решение, разберём в этом посте отличия между кодировками. А в среду обсудим компактные строки.

Символы хранятся в памяти в виде чисел. Кодировки отвечают за формат хранения и правила перевода символов в числа и обратно. Кодировки можно условно поделить на две группы:
1️⃣ ASCII-based
2️⃣ Unicode-based

1️⃣ ASCII
В большинстве ASCII кодировок символ занимает 1 байт и содержит число от 0 до 256. Первые 128 значений транслируются одинаково во всех кодировках:
0-31: управляющие последовательности - перенос строки, конец файла и т.д.
32-127: латинский алфавит, цифры, знаки препинания.

Специфичные символы языков отображаются на значения 128-255. Разные кодировки - разные наборы символов:
🔸Кириллица: ISO-8859-5, Windows-1251.
🔸Греческий алфавит: ISO-8859-7, Windows-1253.
🔸Исландские символы: OEM 861.

200 символ может стать Ш, Θ, È или чем-то ещё. Фраза «Я люблю Java” в другой кодировке отобразится как «Ď ŰîŃŰî Java».

Итого:
✅ Один символ занимает 1 байт — компактно.
❌ Всего 256 значений — нет места для эмодзи.
❌ Неоднозначность трактовки.
❌ Нельзя использовать украинский и норвежский язык в одном тексте.

2️⃣ Unicode
В основе преобразований лежит таблица с большинством символов, которые используются в мире. Но не со всеми, многие азиатские иероглифы записываются в памяти как комбинация 2-3 символов. Или эмоджи, например,👩‍❤️‍💋‍👩 - это сочетание 8 Unicode-кодов.

Изначально Unicode использовал 2 байта для записи символа и кодировку UCS-2. После 256 символов ASCII казалось, что диапазона 0-65536 хватит навсегда. Эта кодировка использовалась в ранних версиях java для типа char.

Со временем в таблицу добавилось больше символов и встал вопрос об эффективном хранении данных. Сегодня, чтобы однозначно представить символ юникода нужно 32 бита — так символы хранятся в UTF-32.
✅ Прямое отображение.
✅ Простота обработки.
❌ Неэффективный расход памяти — если использовать только латиницу с кодами типа 0..045 и 0...077, ¾ памяти будет занято нулями.

На смену UCS-2 с фиксированными 2 байтами пришёл UTF-16 с переменной длиной. Если значение символа превышает 65536, то оно занимает 4 байта. Java перешла на UTF-16.

Кодировка UTF-8 тоже использует переменное количество памяти. Для каждого символа задаётся, сколько он занимает места — 1, 2, 3 или 4 байта.
✅ Экономный расход памяти для латинских символов.
❌ Обработка и поиск происходят чуть медленнее.
❌ Отметка длины находится в первых 2 битах и уменьшает диапазон значений.

Если в структуре 2 или больше байтов, то одни процессоры быстрее считывают их в прямом порядке, а другие — в обратном. Поэтому у UTF-16 и UTF-32 могут быть приставки LE или BE: Little/big endian.

ASCII-кодировки не умеют читать символы больше 255, поэтому когда они встречают юникод-символы, то показывают ❓ и текст «я люблю Java” превращается в “? ????? Java”.

Java 9: Сompact Strings.

По данным OpenJDK не менее 25% объектов в памяти занимают строки. По той же статистике 95% строк содержат только латинские символы и цифры, числовое значение которых умещается в 1 байт, а 5-15% памяти заняты бесполезными нулями.

Для хранения символов в java 8 используется тип char. Занимает 16 бит и содержит значение в кодировке UTF-16. Строка хранится как массив символов — char[].

В Java 9 вышло обновление Compact Strings, которое меняет структуру хранения строки.
Символы теперь лежат в byte[] и хранятся в одной из двух кодировок. Сама кодировка записана в новом параметре coder. Возможны 2 варианта:
1️⃣ Если все символы строки умещаются в 1 байт(латиница и цифры), то записываются в одну ячейку массива. Выставляется кодировка Latin-1.
2️⃣ Если хотя бы один символ требует 16 байт, все элементы занимают 2 ячейки массива. Выставляется кодировка UTF-16.

❓Можно ли было перевести строки на UTF-8, символы с переменной длиной?
Да, расход памяти стал бы ещё меньше, но производительность бы упала. Если символы в массиве одной длины, то по индексу можно быстро найти адрес символа в памяти. Если элементы с переменной длиной - адрес вычисляется на основе предыдущих элементов, а это долго. Все методы класса String работали бы дольше.

Строки в разных кодировках по-разному лежат в памяти, и работать с ними нужно тоже по-разному. Каждый метод в классе String начинается с проверки кодировки и разделяется на две ветки — для Latin-1 и UTF-16. Их код вынесен в отдельные классы StringLatin1 и StringUTF16.

❓Память сэкономили, кода стало в 3 раза больше, не упала ли производительность?
Любая дополнительная проверка снижает скорость обработки, особенно при работе с маленькими строками. Поэтому на уровне JVM и JIT добавлены оптимизации проверки кодировки и сравнения строк, изменён механизм конкатенации и других операций. Именно за счёт внутренних оптимизаций компактные строки работают в среднем на 20% быстрее и создают на 30% меньше промежуточных объектов.

Самое главное - эти изменения никак не отразились на интерфейсе String. I/O классы, StringBuilder, StringBuffer тоже адаптированы без внешних изменений. Нужно просто перейти на java 9 и приложение будет занимать на 5-15% меньше памяти.

​Загрузчики классов в Java.

Пост о том, зачем нужны загрузчики классов, и почему по умолчанию их 3.

При компиляции исходный код преобразуется в файл с расширением .class. Когда в программе встречается имя нового класса, JVM "загружает" его: ищет файл с таким же именем и создаёт экземпляр типа Class. В этом объекте содержится информация о полях, методах и обо всём, что нужно для создания экземпляра.

Базовые классы JDK, такие как Object, String, ArrayList, являются основой для других объектов. Поэтому они загружаются на старте приложения, этим занимается объект JVM под названием Bootstrap ClassLoader.

Любая программа использует много сторонних библиотек. Чтобы не тратить ресурсы на загрузку лишних объектов, классы подгружаются по мере необходимости.

❓Какие события вызывают загрузку класса?
🔸Создание экземпляра:

new Example();

🔸Ссылка на статические поля/методы этого класса:

Example.getFormat();

🔸Явная загрузка класса:

cl.loadClass("Example");

Extension ClassLoader загружает редкие модули JDK: java.sql, jdk.httpserver и тд. Application ClassLoader загружает пользовательские классы.

Схема поиска подходящего .class файла выглядит так:

❓Почему так?
✅ Чтобы обеспечить однозначность и приоритет классов JDK. При такой схеме невозможно создать свой класс с именем java.lang.String.

❓Почему для классов JDK используется 2 загрузчика?
✅ Bootstrap работает на уровне виртуальной машины и загружает необходимый минимум классов на старте приложения. Extension ClassLoader - java объект, который загружает дополнительные модули JDK по мере необходимости.

❓Почему для отложенной загрузки классов нужны разные ClassLoader?
✅ Для безопасности классов JDK. Cуществует 4 модификатора доступа - private, protected, public и default. Последний ещё называют "доступ по умолчанию". Он даёт доступ к классам и методам того же пакета. Если мы назовём класс java.lang.Smth, он сможет работать с классами из пакета java.lang. Поэтому класс получает доступ к default полям другого класса только если:
🔸У него совпадает название пакета.
🔸Загружен тем же ClassLoader'ом.

JDK классы используют Bootstrap/Extension загрузчик, а наш java.lang.Smth - Application загрузчик, поэтому внутренние классы JDK недоступны классу Smth.

❓Что изменилось в java 9?
✅ Схема взаимодействия загрузчиков осталась той же. Поскольку JDK библиотеки (rt.jar, tools.jar) теперь разбиты на модули, работа с ними поменялась:
1️⃣ Изменились внутренние классы и методы загрузчиков. Проекты, которые используют загрузчики классов напрямую, столкнулись с проблемами совместимости.
2️⃣ Extension ClassLoader переименован в Platform ClassLoader. Теперь он загружает классы из модулей JDK и сторонних библиотек, одобренных Java Community: JDBC, JMS, JAX-RS и т.д.

Домашний проект: от выбора темы до пункта в резюме.

Написать работающую систему - важный шаг в обучении программированию. Закрепить теорию на практике, закрыть пробелы и попробовать новые технологии можно с помощью домашнего проекта. Давайте разберём популярные вопросы по этой теме:

❓Что писать?
Необязательно придумывать стартап, который изменит мир. Но если идей совсем нет:
1️⃣ Реализуйте с нуля текущий рабочий проект. Это очень удобно:
✅ Знакомая предметная область
✅ Понятные задачи
✅ Можно обсудить с коллегами непонятные места и текущие решения

2️⃣ Если рабочий проект надоел или не нравится, напишите свою версию популярной системы: Tinder, Яндекс.Маркет, «Кто хочет стать миллионером?» и тд. Помните, Вы пишете не "очередной велосипед", а тренируетесь и изучаете лучшие практики.
✅ Понятный функционал
✅ Современные подходы и технологии
❌ Детали реализации оригинала не всегда доступны, поэтому не с чем сравнить результат

❓Как работать над проектом?
Здесь Вы сами себе проджект-менеджер:
▫️Опишите функции до начала работы. Ориентируйтесь на текущие навыки и добавьте небольшой челлендж
▫️Декомпозируйте и отсортируйте задачи
▫️Составьте план
▫️Поставьте нестрогие дедлайны
▫️Двигайтесь от простого к сложному. Напишите основу на чистой java, добавьте maven/gradle, затем Spring, Spring Boot, базу данных и другие технологии
▫️Пишите тесты, это поможет найти узкие места
▫️Напишите эмулятор запросов, нагрузите приложение и изучите профайлеры

❓Нужно ли добавлять проект в резюме?
Как хотите🙂 Это большой бонус, если:
🔸Вы только начинаете карьеру разработчика.
🔸Домашний проект больше соответствует вакансии, чем текущее место работы.
🔸Вы хотите показать область своих интересов. Это полезно при собеседовании в компанию с большим количеством проектов.

❓Как подготовить проект к показу?
Прежде чем добавлять ссылку на проект в резюме, сделайте 2 несложных шага:
1️⃣ Добавьте файл README.md в корневую директорию. Иногда это единственное, на что посмотрит посторонний человек. Не пожалейте времени, тщательно опишите:
▪️О чём проект
▪️Основные функции
▪️Архитектуру (нарисуйте схему)
▪️Используемые технологии

2️⃣ Проработайте структуру проекта - дайте модулям и классам понятные имена. Функции, указанные в README, должно быть легко найти в коде.

Эти простые действия помогут сориентироваться в проекте и лучше оценить Вашу работу.

​​Java 25 лет!

Java, выпущенная в 1995 году под руководством Джеймса Гослинга, используется на 3 миллиардах устройств по всей планете, от мобильного телефона и PC, до холодильника и компьютера в автомобиле.

Более 10 миллионов разработчиков пишут на Java и других мощных языках, которые используют JVM: Kotlin, Scala, Groovy, Jython, JRuby, Clojure.

Поздравляю всех причастных: разработчиков, тестировщиков, менеджеров, аналитиков! Java — это сила!

Мы не знаем точно, что будет дальше в мире технологий, но Java явно войдет в историю. Быть причастным к этому и кодить на одном языке с массой крутых разработчиков очень приятно! С 25-летием, родная

@java_developer

Best practices: как проверять входные данные.

Запросы пользователей и ответы сторонних систем иногда приходят некорретными или в неправильном формате. Проверить данные можно по-разному, посмотрим разные варианты на простом примере:

String info(Request req) {
return req.toString(); }

Для нормальной работы параметр req не должен быть пустым. Мы можем:
1️⃣ Оставить как есть: тогда JVM выбросит NullPointerException(NPE)
2️⃣ Добавить проверку и самим бросить исключение:

if (req==null) throw new NPE();

3️⃣ Добавить проверку и вернуть null:

if (req==null) return null;

4️⃣ Добавить проверку и вернуть Optional.empty():

if (req==null) return Optional.empty();

Оценим их с точки зрения производительности и дизайна.

Начнём с производительности. Запустим каждый вариант миллион раз:
▪️14 мс - JVM исключение
▪️2 мс - явный выброс исключения
▪️0,03 мс - null
▪️0,03 мс - Optional.empty()

Что это значит?
1️⃣ Создание исключения гораздо дольше, чем выход из метода. Время уходит на создание стек-трейса - чем он глубже, тем хуже производительность. Стек-трейс из сервиса на Spring Boot собирается в 50-100 раз дольше, чем стек-трейс из метода main.

2️⃣ Если исключение явно создаётся в коде, JVM переиспользует ранее собранный стэк-трейс. Так получается выигрыш в 5-10 раз, но разница с вариантом без исключения всё ещё внушительна.

По этим цифрам легко решить, что исключения - удар по производительности. 10 лет назад была тенденция избегать исключений любой ценой. Например, возвращать из метода пару (результат, код_ошибки).

В 2020 это уже не актуально. Если взаимодействие в системе не построено на исключениях, то это капля в море относительно других операций. В примере сверху исключение создаётся миллион раз подряд - такого в продакшене обычно нет.
Исключения делают код чище:
🔹Понятное возвращаемое значение
🔹В части throws явно обозначены непредвиденные ситуации
🔹Логика метода и обработка ошибок разделены

Теперь сравним создание исключения и возврат null с точки зрения дизайна.
Исключение подразумевает обработку ошибки, например:
🔸Показать пользователю сообщение.
🔸Прекратить работу с файлом.
🔸Поменять формат данных.

Optional.empty(), null или объект по умолчанию возвращается, когда реагировать на ситуацию необязательно. Например, когда данные быстро устаревают. Возвращаемый тип Optional удобнее использовать: не нужно смотреть в документации, возвращает ли функция пустой результат, и как он обозначается: null, -1 или 0.

​Что вернёт метод?

Что вернётся из try-catch-finally?

Вопросы такого типа популярны на собеседованиях. Поведение try-catch-finally в спецификации описывается через 24 предложения "если". Логика запутанная, и легко допустить ошибку.

Чтобы решать такие задачки, воспользуйтесь следующей моделью:
Результатом блока try-catch-finally могут быть 3 варианта:
🔸Ничего
🔸Возврат значения
🔸Исключение
Представим, что результат записывается в переменную result. В начале работы там "ничего".

Блоки обрабатываются в строгом порядке:
1️⃣ try
2️⃣ catch
3️⃣ finally
На каждом шаге переменная result может быть перезаписана. Итоговое значение result и будет результатом выполнения. Особый случай — при вызове System.exit(0) выполнение прекращается сразу же .

Разберём пример из опроса:
▫️try установит результат на "вернуть try".
▫️Блока catch нет.
▫️В finally результат меняется на "вернуть finally".
Итог: вернётся "finally"

Другой пример:
try { throw new NPE(); }
catch (SecurityEx e)
{ return "ex"; }
finally {}

▫️В блоке try результатом станет "NPE".
▫️Блок catch пропускается, т.к нет подходящего типа исключения.
▫️В блоке finally результат не переопределяется.
Итог: выброс NPE.

Этот пример важен, потому что такие ошибки часто встречаются на практике. Блок finally - не оберег от исключений. Если результат "исключение" дальше не переопределён, он пробрасывается в вышестоящий метод.

​Что вернёт метод?

Stream API: ускоряемся🚀

Stream API помогает писать выразительный код, который быстро работает. Несложными действиями можно повысить скорость ещё больше:

1️⃣ Добавить parallel().
Для поддержки параллельности нужны дополнительные ресурсы, и прирост скорости заметен только если в коллекции много элементов. Если:
N – количество элементов,
Q – количество операций над каждым элементом,
то при N*Q>10000 можно смело добавлять parallel()

2️⃣ Добавить или удалить sorted(), unordered().
🔸sorted(): отсортировать стрим и добавить свойство «отсортирован».
🔸unordered(): выставить свойство «порядок не важен».
Источник данных и методы sorted, unordered, dictinct,... определяют свойства стрима: конечный размер, уникальность, отсортированные значения и другие. Благодаря этому некоторые методы оптимизируют работу. Если порядок не важен, параллельная обработка будет быстрее. Если список уже отсортирован, удаление повторяющихся элементов distinct() займёт меньше времени. Иногда наоборот — дополнительные ограничения замедляют работу.
Другие специфичные примеры.

3️⃣ Пользоваться специальными методами.
Чем меньше операций, тем быстрее всё работает. Проверить, что ни один элемент не удовлетворяет условию можно так:
filter(...).findFirst().isPresent()
а можно короче, понятнее и быстрее:
noneMatch(...)

Иногда стримы даже не нужны, много полезных методов есть в интерфейсе Collections. Например, максимальный элемент в списке быстрее найти через Collections.max(...), чем с использованием стрима.
Больше примеров

4️⃣ Объединить однотипные операции.
Чаще это касается сложной фильтрации:
filter(1).filter(2).filter(3)
можно ускорить в 2-4 раза, если объединить условия:
filter(1 & 2 & 3)