Что будет результатом кода?
Anonymous Quiz
23%
[10, 20, 30, 40]
7%
[20, 30, 40, 10]
56%
[20, 30, 40]
12%
[10, 20, 30]
2%
[30, 40, 20]
👍8🔥2
Что выбрать, Stack или Queue?
Queue – один из основных интерфейсов Java Collections Framework. В общем случае (но не обязательно) представляет FIFO-коллекцию – элементы можно добавлять в хвост, брать или удалять из головы. Его наследник, интерфейс Deque (double ended queue, двусторонняя очередь), позволяет манипулировать элементами на обеих сторонах.
Stack – LIFO коллекция. То есть добавлять и удалять элементы можно только с одного конца. Кроме того, стек наследуется от Vector, и тоже является пересинхронизированным и устаревшим. Его документация явно рекомендует предпочесть использовать Deque.
Java Guru🤓 #java
Queue – один из основных интерфейсов Java Collections Framework. В общем случае (но не обязательно) представляет FIFO-коллекцию – элементы можно добавлять в хвост, брать или удалять из головы. Его наследник, интерфейс Deque (double ended queue, двусторонняя очередь), позволяет манипулировать элементами на обеих сторонах.
Stack – LIFO коллекция. То есть добавлять и удалять элементы можно только с одного конца. Кроме того, стек наследуется от Vector, и тоже является пересинхронизированным и устаревшим. Его документация явно рекомендует предпочесть использовать Deque.
Java Guru🤓 #java
❤7👍5
Что происходит внутри 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), внутренний массив увеличивается вдвое, а для всего содержимого выполняется рехэш – все имеющиеся ноды перераспределяются по бакетам по тем же правилам, но уже с учетом нового размера.
👍22🔥6❤4🤔2
Какая временная сложность у contains() в ArrayList?
Anonymous Quiz
13%
O(1)
73%
O(n)
9%
O(log n)
1%
O(n 2)
5%
Зависит от размера
👍6🔥1
Что происходит внутри TreeMap.put()?
Недавно мы в деталях рассматривали, какие процессы происходят при добавлении элемента в HashMap. Теперь поговорим о TreeMap. Здесь не так много тонкостей, как в хэш-таблице.
TreeMap требует либо задать порядок ключей вручную (передать в конструктор Comparator), либо чтобы они имели собственный естественный порядок (были Comparable).
Подобно нодам в хэш-таблице, внутренняя структура дерева строится из объектов внутреннего класса узла – Entry. В каждом узле хранится информация о данных (пара key-value), и о положении в структуре (ссылки на родительский узел, левую и правую ветви).
Сама структура представляет из себя красно-чёрное дерево относительно ключей. Не будем здесь углубляться в детали его реализации. О нем важно знать два факта:
1. Это бинарное дерево поиска. Значит, каждый новый элемент начинает искать свое место в дереве, сравниваясь с узлами начиная с корневого. Меньшие элементы движутся влево, большие – вправо. Для этого и требуется наличие метода compare. Дойдя до конца, пара ключ-значение «повисает» новым узлом.
2. Это самобалансирующееся дерево. Если какая-то ветка начинает становиться слишком длинной (а её эффективность вырождаться в эффективность связного списка), происходит балансировка. В результате этой операции правило из пунтка 1 остается в силе, но нагрузка на ветки перераспределяется. Самое длинное поддерево становится выше самого короткого максимум на один элемент.
Java Guru🤓 #java
Недавно мы в деталях рассматривали, какие процессы происходят при добавлении элемента в HashMap. Теперь поговорим о TreeMap. Здесь не так много тонкостей, как в хэш-таблице.
TreeMap требует либо задать порядок ключей вручную (передать в конструктор Comparator), либо чтобы они имели собственный естественный порядок (были Comparable).
Подобно нодам в хэш-таблице, внутренняя структура дерева строится из объектов внутреннего класса узла – Entry. В каждом узле хранится информация о данных (пара key-value), и о положении в структуре (ссылки на родительский узел, левую и правую ветви).
Сама структура представляет из себя красно-чёрное дерево относительно ключей. Не будем здесь углубляться в детали его реализации. О нем важно знать два факта:
1. Это бинарное дерево поиска. Значит, каждый новый элемент начинает искать свое место в дереве, сравниваясь с узлами начиная с корневого. Меньшие элементы движутся влево, большие – вправо. Для этого и требуется наличие метода compare. Дойдя до конца, пара ключ-значение «повисает» новым узлом.
2. Это самобалансирующееся дерево. Если какая-то ветка начинает становиться слишком длинной (а её эффективность вырождаться в эффективность связного списка), происходит балансировка. В результате этой операции правило из пунтка 1 остается в силе, но нагрузка на ветки перераспределяется. Самое длинное поддерево становится выше самого короткого максимум на один элемент.
Java Guru🤓 #java
❤6🔥3👍2
Что будет результатом кода?
Anonymous Quiz
7%
Ошибка компиляции
1%
null
45%
Hello
4%
World
43%
Hello World
👍15🔥6
Можно ли хранить null в стандартных коллекциях?
Все интерфейсы Collections Framework позволяют своим реализациям самостоятельно решать, поддерживать ли null-значения. Если реализация не может принять null, она выбрасывает NullPointerException или ClassCastException.
Большинство списков (LinkedList, ArrayList) принимают null без проблем. Большинство очередей (Queue и Deque) не хранят null – возвращая из читающего метода null они сообщают пользователю о пустоте коллекции.
Unmodifiable Maps не допускают null-ов совсем. Обычные изменяемые мапы обычно не испытывают трудности со значениями null. А вот с ключами дело обстоит интереснее.
HashMap не может посчитать hash-сумму от null. Но вместо этого для таких ключей просто используется бакет номер 0.
Иногда этот вопрос дается как задача с подвохом про TreeMap. Nullability её ключей зависит от готовности к этому компаратора. Натуральный порядок (который работает для Comparable ключей) не поддерживает null. Раньше в реализации был баг, который позволял положить значение по ключу null в корень дерева без выброса исключения.
Для значений Set-ов действуют те же правила, что для ключей лежащих в основе их Map-ов.
Java Guru🤓 #java
Все интерфейсы Collections Framework позволяют своим реализациям самостоятельно решать, поддерживать ли null-значения. Если реализация не может принять null, она выбрасывает NullPointerException или ClassCastException.
Большинство списков (LinkedList, ArrayList) принимают null без проблем. Большинство очередей (Queue и Deque) не хранят null – возвращая из читающего метода null они сообщают пользователю о пустоте коллекции.
Unmodifiable Maps не допускают null-ов совсем. Обычные изменяемые мапы обычно не испытывают трудности со значениями null. А вот с ключами дело обстоит интереснее.
HashMap не может посчитать hash-сумму от null. Но вместо этого для таких ключей просто используется бакет номер 0.
Иногда этот вопрос дается как задача с подвохом про TreeMap. Nullability её ключей зависит от готовности к этому компаратора. Натуральный порядок (который работает для Comparable ключей) не поддерживает null. Раньше в реализации был баг, который позволял положить значение по ключу null в корень дерева без выброса исключения.
Для значений Set-ов действуют те же правила, что для ключей лежащих в основе их Map-ов.
Java Guru🤓 #java
👍15🔥5❤3
Какие есть преимущества у массива перед коллекцией?
Для хранения ссылочных типов массив подходит хуже чем ArrayList. В основе реализации коллекции лежит такой же массив, поэтому эффективность будет той же самой. Однако, вам придется самостоятельно реализовывать логику управления хранилищем: например, увеличение массива при переполнении. А значит, будет больше шансов на ошибку.
Если использовать массивы вместо коллекций для примитивов, можно получить выигрыш по эффективности. Коллекции – generic-типы, из-за этого простые значения хранятся в них в форме ссылочных типов-оберток.
1. Autoboxing выделяет память под новый объект, это дорогая операция;
2. Кроме данных, Object занимает дополнительную память под метаинформацию;
3. Ячейки массива лежат близко в оперативной памяти, это увеличивает шансы попадания в кэш процессора.
С другой стороны, для массива всё так же нужно написать больше кода, он сложнее. Поэтому замена листов на массивы обычно считается излишней микрооптимизацией.
Когда сэкономить всё-таки хочется, стоит выбрать одну из множества готовых библиотек не-generic реализаций коллекций. Списки примитивов можно найти в Eclipse Collections. В Android есть HashMap с целочисленными ключами – SparseArray.
Java Guru🤓 #java
Для хранения ссылочных типов массив подходит хуже чем ArrayList. В основе реализации коллекции лежит такой же массив, поэтому эффективность будет той же самой. Однако, вам придется самостоятельно реализовывать логику управления хранилищем: например, увеличение массива при переполнении. А значит, будет больше шансов на ошибку.
Если использовать массивы вместо коллекций для примитивов, можно получить выигрыш по эффективности. Коллекции – generic-типы, из-за этого простые значения хранятся в них в форме ссылочных типов-оберток.
1. Autoboxing выделяет память под новый объект, это дорогая операция;
2. Кроме данных, Object занимает дополнительную память под метаинформацию;
3. Ячейки массива лежат близко в оперативной памяти, это увеличивает шансы попадания в кэш процессора.
С другой стороны, для массива всё так же нужно написать больше кода, он сложнее. Поэтому замена листов на массивы обычно считается излишней микрооптимизацией.
Когда сэкономить всё-таки хочется, стоит выбрать одну из множества готовых библиотек не-generic реализаций коллекций. Списки примитивов можно найти в Eclipse Collections. В Android есть HashMap с целочисленными ключами – SparseArray.
Java Guru🤓 #java
🔥9👍6❤5
Что такое fail-fast и fail-safe итераторы?
Это не какие-то отдельные типы, а характеристики разных реализаций интерфейса Iterator. Они определяют, как поведет себя итератор при изменении перебираемой последовательности.
Fail-fast – «быстрый» итератор. Когда после его создания коллекция как-либо изменилась, он падает с ошибкой без лишних разбирательств. Так работает итератор класса ArrayList, при изменении он выбрасывает ConcurrentModificationException. Рекомендуется не основывать логику программы на fail-fast отказах, и использовать их только как признак ошибки реализации.
Fail-safe – «умный» итератор. Обычно плата за отказоустойчивость – возможная неконсистентность данных («слабая консистентность»). Итератор класса ConcurrentHashMap работает с копией данных, он не выбросит исключение при изменении коллекции, но может не увидеть часть свежих изменений. Плата за отсутствие ошибок других fail-safe итераторов может отличаться, детали всегда можно найти в документации коллекций.
Java Guru🤓 #java
Это не какие-то отдельные типы, а характеристики разных реализаций интерфейса Iterator. Они определяют, как поведет себя итератор при изменении перебираемой последовательности.
Fail-fast – «быстрый» итератор. Когда после его создания коллекция как-либо изменилась, он падает с ошибкой без лишних разбирательств. Так работает итератор класса ArrayList, при изменении он выбрасывает ConcurrentModificationException. Рекомендуется не основывать логику программы на fail-fast отказах, и использовать их только как признак ошибки реализации.
Fail-safe – «умный» итератор. Обычно плата за отказоустойчивость – возможная неконсистентность данных («слабая консистентность»). Итератор класса ConcurrentHashMap работает с копией данных, он не выбросит исключение при изменении коллекции, но может не увидеть часть свежих изменений. Плата за отсутствие ошибок других fail-safe итераторов может отличаться, детали всегда можно найти в документации коллекций.
Java Guru🤓 #java
👍14❤4🔥4
Какая настройка при создании связи Customer-Order приведет к неправильному поведению при сохранении нескольких Order, связанных с одним Customer?
Anonymous Quiz
21%
CascadeType.ALL
15%
fetch = FetchType.EAGER
10%
optional = false
45%
unique = true
10%
referencedColumnName
🔥10👍4❤2
Какие существуют примитивы?
В Java имеется 9 возможных типов значения переменной: ссылка на объект или один из восьми примитивных типов:
🔘 byte – знаковое целое число от -2^7 до 2^7-1;
🔘 short – знаковое целое число от -2^15 до 2^15-1;
🔘 int – знаковое целое число от -2^31 до 2^31-1;
🔘 long – знаковое целое число от -2^63 до 2^63-1;
🔘 float – знаковое число с плавающей точкой 32 бита стандарта IEEE 754;
🔘 double – то же, что и float, но 64 бита;
🔘 char – 16-битный символ Unicode, от '\u0000'(0) до '\uffff'(65535);
🔘 boolean – true или false;
По умолчанию поля примитивных типов принимают нулевые значения: 0, 0L, '\u0000', false. Про особенности работы, способ хранения и специальные значения чисел с плавающей точкой стоит почитать подробнее.
Отдельная интересная тема – boxing/unboxing. Каждый примитивный тип снабжен своей ссылочной версией. Примитивное значение заворачивается и разворачивается из него автоматически при необходимости. Это может приводить к большим затратам на выделение памяти, когда например int индекс цикла используется в качестве значения переменной Object и превращается в Integer без нужды – частая задача на собеседованиях. Еще классы-обертки содержат набор утилитарных методов для их примитивов.
Сколько памяти занимает примитив – вопрос с подвохом. Спецификация требует, чтобы размер был достаточным для всех значений. Конкретный размер определяется реализацией JVM, он может быть больше. Например в 64-bit HotSpot переменная boolean занимает не 1 бит, а 8.
Java Guru🤓 #java
В Java имеется 9 возможных типов значения переменной: ссылка на объект или один из восьми примитивных типов:
По умолчанию поля примитивных типов принимают нулевые значения: 0, 0L, '\u0000', false. Про особенности работы, способ хранения и специальные значения чисел с плавающей точкой стоит почитать подробнее.
Отдельная интересная тема – boxing/unboxing. Каждый примитивный тип снабжен своей ссылочной версией. Примитивное значение заворачивается и разворачивается из него автоматически при необходимости. Это может приводить к большим затратам на выделение памяти, когда например int индекс цикла используется в качестве значения переменной Object и превращается в Integer без нужды – частая задача на собеседованиях. Еще классы-обертки содержат набор утилитарных методов для их примитивов.
Сколько памяти занимает примитив – вопрос с подвохом. Спецификация требует, чтобы размер был достаточным для всех значений. Конкретный размер определяется реализацией JVM, он может быть больше. Например в 64-bit HotSpot переменная boolean занимает не 1 бит, а 8.
Java Guru🤓 #java
Please open Telegram to view this post
VIEW IN TELEGRAM
👍11🔥5❤3
Сколько объектов станут доступны для сборщика мусора после удаления ссылки на сет?
Anonymous Quiz
13%
0
13%
1
10%
2
21%
3
43%
4
👍13🔥6
Что такое static?
Ключевое слово static используется для объявления вложенных классов, статических методов, полей, блоков инициализации и статических импортов.
Статические поля и методы – члены класса а не экземпляра, потому к ним можно обращаться через имя класса. Код статического блока или метода имеет доступ только к статическим членам. Статические поля не участвуют в сериализации.
Для статических методов используется раннее связывание, то есть вызов конкретного метода разрешается на этапе компиляции, не работают перегрузка и переопределение в наследниках.
Статический блок инициализации выполняется потокобезопасно, один раз сразу после загрузки класса класслоадером. Инициализаторы статических полей выполняются в неявном статическом блоке. Блоков может быть несколько, выполнятся они в порядке объявления.
Статический импорт (static import) импортирует статические члены классов в .java-файл.
Java Guru🤓 #java
Ключевое слово static используется для объявления вложенных классов, статических методов, полей, блоков инициализации и статических импортов.
Статические поля и методы – члены класса а не экземпляра, потому к ним можно обращаться через имя класса. Код статического блока или метода имеет доступ только к статическим членам. Статические поля не участвуют в сериализации.
Для статических методов используется раннее связывание, то есть вызов конкретного метода разрешается на этапе компиляции, не работают перегрузка и переопределение в наследниках.
Статический блок инициализации выполняется потокобезопасно, один раз сразу после загрузки класса класслоадером. Инициализаторы статических полей выполняются в неявном статическом блоке. Блоков может быть несколько, выполнятся они в порядке объявления.
Статический импорт (static import) импортирует статические члены классов в .java-файл.
Java Guru🤓 #java
👍21🔥4❤2
Что будет результатом кода?
Anonymous Quiz
2%
[1, 2, 3, 4, 5, 6]
5%
[2, 4, 6, 8, 10, 12]
5%
[2, 4, 6]
83%
[4, 8, 12]
4%
Ошибка компиляции
👍20🥱13🔥3🌭1