Что происходит внутри HashMap.put()?
Мы уже рассматривали хэш-таблицы в целом, теперь рассмотрим в деталях, как новые ключ и значение складываются в HashMap.
1. Вычисляется хэш ключа. Если ключ null, хэш считается равным 0. Чтобы достичь лучшего распределения, результат вызова hashCode() «перемешивается»: его старшие биты XOR-ятся на младшие.
2. Значения внутри хэш-таблицы хранятся в специальных структурах данных – нодах, в массиве. Из хэша высчитывается номер бакета – индекс для значения в этом массиве. Полученный хэш обрезается по текущей длине массива. Длина – всегда степень двойки, так что для скорости используется битовая операция &.
3. В бакете ищется нода. В ячейке массива лежит не просто одна нода, а связка всех нод, которые туда попали. Исполнение проходит по этой связке (цепочке или дереву), и ищет ноду с таким же ключом. Ключ сравнивается с имеющимися сначала на ==, затем на equals.
4. Если нода найдена – её значение просто заменяется новым. Работа метода на этом завершается.
5. Если ноды с таким же ключом в бакете пока нет – добавляемая пара ключ-значение запаковывается в новый объект типа Node, и прикрепляется к структуре существующих нод бакета. Ноды составляют структуру за счет того, что в ноде хранится ссылка на следующий элемент (для дерева – следующие элементы). Кроме самой пары и ссылок, чтобы потом не считать заново, записывается и хэш ключа.
6. В случае, когда структурой была цепочка а не дерево, и длина цепочки превысила 7 элементов – происходит процедура treeification – превращение списка в самобалансирующееся дерево. В случае коллизии это ускоряет доступ к элементам на чтение с O(n) до O(log(n)). У comparable-ключей для балансировки используется их естественный порядок. Другие ключи балансируются по порядку имен их классов и значениям identityHashCode-ов. Для маленьких хэш-таблиц (< 64 бакетов) «одеревенение» заменяется увеличением (см. п.8).
7. Если новая нода попала в пустую ячейку, заняла новый бакет – увеличивается счетчик структурных модификаций. Изменение этого счетчика сообщит всем итераторам контейнера, что при следующем обращении они должны выбросить ConcurrentModificationException.
8. Когда количество занятых бакетов массива превысило пороговое (capacity * load factor), внутренний массив увеличивается вдвое, а для всего содержимого выполняется рехэш – все имеющиеся ноды перераспределяются по бакетам по тем же правилам, но уже с учетом нового размера.
Мы уже рассматривали хэш-таблицы в целом, теперь рассмотрим в деталях, как новые ключ и значение складываются в HashMap.
1. Вычисляется хэш ключа. Если ключ null, хэш считается равным 0. Чтобы достичь лучшего распределения, результат вызова hashCode() «перемешивается»: его старшие биты XOR-ятся на младшие.
2. Значения внутри хэш-таблицы хранятся в специальных структурах данных – нодах, в массиве. Из хэша высчитывается номер бакета – индекс для значения в этом массиве. Полученный хэш обрезается по текущей длине массива. Длина – всегда степень двойки, так что для скорости используется битовая операция &.
3. В бакете ищется нода. В ячейке массива лежит не просто одна нода, а связка всех нод, которые туда попали. Исполнение проходит по этой связке (цепочке или дереву), и ищет ноду с таким же ключом. Ключ сравнивается с имеющимися сначала на ==, затем на equals.
4. Если нода найдена – её значение просто заменяется новым. Работа метода на этом завершается.
5. Если ноды с таким же ключом в бакете пока нет – добавляемая пара ключ-значение запаковывается в новый объект типа Node, и прикрепляется к структуре существующих нод бакета. Ноды составляют структуру за счет того, что в ноде хранится ссылка на следующий элемент (для дерева – следующие элементы). Кроме самой пары и ссылок, чтобы потом не считать заново, записывается и хэш ключа.
6. В случае, когда структурой была цепочка а не дерево, и длина цепочки превысила 7 элементов – происходит процедура treeification – превращение списка в самобалансирующееся дерево. В случае коллизии это ускоряет доступ к элементам на чтение с O(n) до O(log(n)). У comparable-ключей для балансировки используется их естественный порядок. Другие ключи балансируются по порядку имен их классов и значениям identityHashCode-ов. Для маленьких хэш-таблиц (< 64 бакетов) «одеревенение» заменяется увеличением (см. п.8).
7. Если новая нода попала в пустую ячейку, заняла новый бакет – увеличивается счетчик структурных модификаций. Изменение этого счетчика сообщит всем итераторам контейнера, что при следующем обращении они должны выбросить ConcurrentModificationException.
8. Когда количество занятых бакетов массива превысило пороговое (capacity * load factor), внутренний массив увеличивается вдвое, а для всего содержимого выполняется рехэш – все имеющиеся ноды перераспределяются по бакетам по тем же правилам, но уже с учетом нового размера.
👍9🔥8❤2
Двухфакторная аутентификация (2FA) — стандарт безопасности, без которого нельзя представить современные приложения.
Как реализовать её на практике с помощью Spring Security? Какие есть подходы и сценарии использования? Это то, что нужно знать каждому начинающему backend-разработчику на Java.
На открытом уроке курса «Разработчик на Spring Framework» вы увидите, как работает 2FA в Spring Boot, и разберёте реальные примеры внедрения. Это не просто теория, а практические шаги, которые помогут вам прокачать скиллы и почувствовать уверенность в разработке безопасных сервисов.
Вебинар, который пройдёт 18 сентября в 20:00 МСК. Все участники получат скидку на обучение на курсе «Разработчик на Spring Framework». Регистрация открыта: https://vk.cc/cPl1EW
Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576
Как реализовать её на практике с помощью Spring Security? Какие есть подходы и сценарии использования? Это то, что нужно знать каждому начинающему backend-разработчику на Java.
На открытом уроке курса «Разработчик на Spring Framework» вы увидите, как работает 2FA в Spring Boot, и разберёте реальные примеры внедрения. Это не просто теория, а практические шаги, которые помогут вам прокачать скиллы и почувствовать уверенность в разработке безопасных сервисов.
Вебинар, который пройдёт 18 сентября в 20:00 МСК. Все участники получат скидку на обучение на курсе «Разработчик на Spring Framework». Регистрация открыта: https://vk.cc/cPl1EW
Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576
❤2👍2🔥2
👍12🔥4🤔2
🗓 17 сентября в 20:00 МСК
🆓 Бесплатно. Урок в рамках старта курса «Java Developer. Professional».
🎯 О чём поговорим:
👥 Кому будет интересно:
Это мероприятие будет полезно Java-разработчикам, архитекторам и IT-специалистам финансовых организаций. Вы получите ценные знания, которые сможете применить на практике.
🔗 Ссылка на регистрацию: https://vk.cc/cPn5Ma
Реклама. ООО «Отус онлайн-образование», ОГРН 1177746618576
Please open Telegram to view this post
VIEW IN TELEGRAM
👍1🔥1