Каков результат выполнения следующего кода?
Anonymous Quiz
17%
Ошибка компиляции в строке 1
18%
Ошибка компиляции в строке 9
10%
Ошибка выполнения в строке 9
12%
Ошибка компиляции в строке 18
13%
10
28%
15
3%
20
👍12🔥6☃1🥴1🍌1
Что происходит внутри 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), внутренний массив увеличивается вдвое, а для всего содержимого выполняется рехэш – все имеющиеся ноды перераспределяются по бакетам по тем же правилам, но уже с учетом нового размера.
🔥24👍16🐳1
Kotlin заходит в Telegram!
Рассказываем про Kotlin — молодой язык родом из Питера, который вовсю теснит Java в мобильной и бэкенд-разработке.
Его официально поддерживает Google, используют Jira и Adobe, а разработчики топовых приложений для Android переписывают на Kotlin свои продукты. Советуем подписаться, чтобы узнавать больше!
Рассказываем про Kotlin — молодой язык родом из Питера, который вовсю теснит Java в мобильной и бэкенд-разработке.
Его официально поддерживает Google, используют Jira и Adobe, а разработчики топовых приложений для Android переписывают на Kotlin свои продукты. Советуем подписаться, чтобы узнавать больше!
👍5🔥2
Что произойдет в результате компиляции и выполнения данного кода?
Anonymous Quiz
43%
Скомпилируется и запустится без ошибок
24%
Ошибка выполнения
33%
Ошибка компиляции
👍10🍌1
Что происходит внутри TreeMap.put()?
Недавно мы в деталях рассматривали, какие процессы происходят при добавлении элемента в HashMap. Теперь поговорим о TreeMap. Здесь не так много тонкостей, как в хэш-таблице.
TreeMap требует либо задать порядок ключей вручную (передать в конструктор Comparator), либо чтобы они имели собственный естественный порядок (были Comparable).
Подобно нодам в хэш-таблице, внутренняя структура дерева строится из объектов внутреннего класса узла – Entry. В каждом узле хранится информация о данных (пара key-value), и о положении в структуре (ссылки на родительский узел, левую и правую ветви).
Сама структура представляет из себя красно-чёрное дерево относительно ключей. Не будем здесь углубляться в детали его реализации. О нем важно знать два факта:
1. Это бинарное дерево поиска. Значит, каждый новый элемент начинает искать свое место в дереве, сравниваясь с узлами начиная с корневого. Меньшие элементы движутся влево, большие – вправо. Для этого и требуется наличие метода compare. Дойдя до конца, пара ключ-значение «повисает» новым узлом.
2. Это самобалансирующееся дерево. Если какая-то ветка начинает становиться слишком длинной (а её эффективность вырождаться в эффективность связного списка), происходит балансировка. В результате этой операции правило из пунтка 1 остается в силе, но нагрузка на ветки перераспределяется. Самое длинное поддерево становится выше самого короткого максимум на один элемент.
Недавно мы в деталях рассматривали, какие процессы происходят при добавлении элемента в HashMap. Теперь поговорим о TreeMap. Здесь не так много тонкостей, как в хэш-таблице.
TreeMap требует либо задать порядок ключей вручную (передать в конструктор Comparator), либо чтобы они имели собственный естественный порядок (были Comparable).
Подобно нодам в хэш-таблице, внутренняя структура дерева строится из объектов внутреннего класса узла – Entry. В каждом узле хранится информация о данных (пара key-value), и о положении в структуре (ссылки на родительский узел, левую и правую ветви).
Сама структура представляет из себя красно-чёрное дерево относительно ключей. Не будем здесь углубляться в детали его реализации. О нем важно знать два факта:
1. Это бинарное дерево поиска. Значит, каждый новый элемент начинает искать свое место в дереве, сравниваясь с узлами начиная с корневого. Меньшие элементы движутся влево, большие – вправо. Для этого и требуется наличие метода compare. Дойдя до конца, пара ключ-значение «повисает» новым узлом.
2. Это самобалансирующееся дерево. Если какая-то ветка начинает становиться слишком длинной (а её эффективность вырождаться в эффективность связного списка), происходит балансировка. В результате этой операции правило из пунтка 1 остается в силе, но нагрузка на ветки перераспределяется. Самое длинное поддерево становится выше самого короткого максимум на один элемент.
👍20🔥3❤1
Что будет в результате компиляции и выполнения данного кода?
Anonymous Quiz
15%
Ошибка компиляции в строке 13
49%
Ошибка компиляции в строке 14
11%
Ошибка компиляции в строке 15
20%
Код скомпилируется
4%
Ошибка времени выполнения
👍16
Разрабатывать высоконагруженные сервисы, работать только на современном стеке и за один день стать частью классной команды из амбициозных специалистов! Звучит как мечта, но это реальность One Day Offer для Java-разработчиков от Сбера 💻
Уже 12 августа Сбер приглашает Java-разработчиков уровня Middle/Senior/Lead познакомиться, пройти все этапы отбора, получите оффер и присоединиться к Java-сообществу крупнейшего банка страны.
Чем именно предстоит заниматься на должности Java-разработчика 👇
✔️ Участвовать в выводе продуктов с нуля в промышленную эксплуатацию.
✔️ Создавать высоконагруженные сервисы в направлениях digital и phygital.
✔️ Внедрять и автоматизировать новые процессы.
✔️ Создавать и развивать IT-продукты для сотрудников банка и миллионов клиентов.
Готовы к таким интересным задачам? Переходите по ссылке, регистрируйтесь на One Day Offer и участвуйте в интервью!
Уже 12 августа Сбер приглашает Java-разработчиков уровня Middle/Senior/Lead познакомиться, пройти все этапы отбора, получите оффер и присоединиться к Java-сообществу крупнейшего банка страны.
Чем именно предстоит заниматься на должности Java-разработчика 👇
✔️ Участвовать в выводе продуктов с нуля в промышленную эксплуатацию.
✔️ Создавать высоконагруженные сервисы в направлениях digital и phygital.
✔️ Внедрять и автоматизировать новые процессы.
✔️ Создавать и развивать IT-продукты для сотрудников банка и миллионов клиентов.
Готовы к таким интересным задачам? Переходите по ссылке, регистрируйтесь на One Day Offer и участвуйте в интервью!
👍5🔥4
Какие есть преимущества у массива перед коллекцией?
Для хранения ссылочных типов массив подходит хуже чем ArrayList. В основе реализации коллекции лежит такой же массив, поэтому эффективность будет той же самой. Однако, вам придется самостоятельно реализовывать логику управления хранилищем: например, увеличение массива при переполнении. А значит, будет больше шансов на ошибку.
Если использовать массивы вместо коллекций для примитивов, можно получить выигрыш по эффективности. Коллекции – generic-типы, из-за этого простые значения хранятся в них в форме ссылочных типов-оберток.
1. Autoboxing выделяет память под новый объект, это дорогая операция;
2. Кроме данных, Object занимает дополнительную память под метаинформацию;
3. Ячейки массива лежат близко в оперативной памяти, это увеличивает шансы попадания в кэш процессора.
С другой стороны, для массива всё так же нужно написать больше кода, он сложнее. Поэтому замена листов на массивы обычно считается излишней микрооптимизацией.
Когда сэкономить всё-таки хочется, стоит выбрать одну из множества готовых библиотек не-generic реализаций коллекций. Списки примитивов можно найти в Eclipse Collections. В Android есть HashMap с целочисленными ключами – SparseArray.
Для хранения ссылочных типов массив подходит хуже чем ArrayList. В основе реализации коллекции лежит такой же массив, поэтому эффективность будет той же самой. Однако, вам придется самостоятельно реализовывать логику управления хранилищем: например, увеличение массива при переполнении. А значит, будет больше шансов на ошибку.
Если использовать массивы вместо коллекций для примитивов, можно получить выигрыш по эффективности. Коллекции – generic-типы, из-за этого простые значения хранятся в них в форме ссылочных типов-оберток.
1. Autoboxing выделяет память под новый объект, это дорогая операция;
2. Кроме данных, Object занимает дополнительную память под метаинформацию;
3. Ячейки массива лежат близко в оперативной памяти, это увеличивает шансы попадания в кэш процессора.
С другой стороны, для массива всё так же нужно написать больше кода, он сложнее. Поэтому замена листов на массивы обычно считается излишней микрооптимизацией.
Когда сэкономить всё-таки хочется, стоит выбрать одну из множества готовых библиотек не-generic реализаций коллекций. Списки примитивов можно найти в Eclipse Collections. В Android есть HashMap с целочисленными ключами – SparseArray.
👍18🔥3
Что напечатает следующий код?
Anonymous Quiz
11%
a
45%
b
5%
Результат может варьироваться от запуска к запуску
10%
Ничего не напечатает
6%
Возникнет ошибка времени выполнения
24%
Возникнет ошибка компиляции
👍17🌚5🤯3❤1
Как обойти коллекцию?
for/while. Классический способ: целочисленная переменная-индекс, которая увеличивается от 0 до size(). Можно использовать для неполного обхода, с нестандартным шагом. Плата за это – возможность ошибиться в индексах и менее читабельный код.
Iterator. ООП-способ: методом iterator() получить объект-итератор, и вызывать у него next() пока hasNext() возвращает true. В реализации может быть дополнительная логика, такая как потокобезопасность. Такой «объект-итерацию» коллекции можно передать в сторонний код, не отдавая саму коллекцию. Всё еще требует слишком много кода.
for Iterable. Синтаксический сахар для обхода итератором. Простейший синтаксис когда нужен просто обход. В отличие от явного использования итератора не дает возможности модифицировать элементы в процессе.
Стримы. Создать от коллекции стрим и работать с элементами в нём. Кроме простого forEach(), можно воспользоваться всей мощью Java Steam API – фильтровать, преобразовывать и агрегировать элементы. За это создаются лишние объекты, а синтаксис гораздо более развесистый.
Функции Java 8. С этой версии появились удобные средства для обхода не только строк. У коллекций и хэш-таблиц добавились методы forEach для обхода и replaceAll для модификации. Как со стримами, они дают функциональный стиль, но без избыточного создания стримов. Внутри используются простые итераторы и циклы for.
for/while. Классический способ: целочисленная переменная-индекс, которая увеличивается от 0 до size(). Можно использовать для неполного обхода, с нестандартным шагом. Плата за это – возможность ошибиться в индексах и менее читабельный код.
Iterator. ООП-способ: методом iterator() получить объект-итератор, и вызывать у него next() пока hasNext() возвращает true. В реализации может быть дополнительная логика, такая как потокобезопасность. Такой «объект-итерацию» коллекции можно передать в сторонний код, не отдавая саму коллекцию. Всё еще требует слишком много кода.
for Iterable. Синтаксический сахар для обхода итератором. Простейший синтаксис когда нужен просто обход. В отличие от явного использования итератора не дает возможности модифицировать элементы в процессе.
Стримы. Создать от коллекции стрим и работать с элементами в нём. Кроме простого forEach(), можно воспользоваться всей мощью Java Steam API – фильтровать, преобразовывать и агрегировать элементы. За это создаются лишние объекты, а синтаксис гораздо более развесистый.
Функции Java 8. С этой версии появились удобные средства для обхода не только строк. У коллекций и хэш-таблиц добавились методы forEach для обхода и replaceAll для модификации. Как со стримами, они дают функциональный стиль, но без избыточного создания стримов. Внутри используются простые итераторы и циклы for.
👍16🔥6❤1
Что выведет пример?
Anonymous Quiz
20%
A4
3%
AB3
13%
AB5
3%
BA2
19%
BA4
13%
Ошибка времени выполнения
29%
Ошибка компиляции
👍9
📕 Книги для Java программиста - канал с книгами по Java. Постоянно выходят новинки как на русском так и на английском языке!
📰 Java News - канал с последними новостями из мира Java!
Please open Telegram to view this post
VIEW IN TELEGRAM
👍5❤🔥2
Что такое fail-fast и fail-safe итераторы?
Это не какие-то отдельные типы, а характеристики разных реализаций интерфейса Iterator. Они определяют, как поведет себя итератор при изменении перебираемой последовательности.
Fail-fast – «быстрый» итератор. Когда после его создания коллекция как-либо изменилась, он падает с ошибкой без лишних разбирательств. Так работает итератор класса ArrayList, при изменении он выбрасывает ConcurrentModificationException. Рекомендуется не основывать логику программы на fail-fast отказах, и использовать их только как признак ошибки реализации.
Fail-safe – «умный» итератор. Обычно плата за отказоустойчивость – возможная неконсистентность данных («слабая консистентность»). Итератор класса ConcurrentHashMap работает с копией данных, он не выбросит исключение при изменении коллекции, но может не увидеть часть свежих изменений. Плата за отсутствие ошибок других fail-safe итераторов может отличаться, детали всегда можно найти в документации коллекций.
Это не какие-то отдельные типы, а характеристики разных реализаций интерфейса Iterator. Они определяют, как поведет себя итератор при изменении перебираемой последовательности.
Fail-fast – «быстрый» итератор. Когда после его создания коллекция как-либо изменилась, он падает с ошибкой без лишних разбирательств. Так работает итератор класса ArrayList, при изменении он выбрасывает ConcurrentModificationException. Рекомендуется не основывать логику программы на fail-fast отказах, и использовать их только как признак ошибки реализации.
Fail-safe – «умный» итератор. Обычно плата за отказоустойчивость – возможная неконсистентность данных («слабая консистентность»). Итератор класса ConcurrentHashMap работает с копией данных, он не выбросит исключение при изменении коллекции, но может не увидеть часть свежих изменений. Плата за отсутствие ошибок других fail-safe итераторов может отличаться, детали всегда можно найти в документации коллекций.
👍23🔥5
👍16🔥4🍌3