2020-10-10
563
Допустим нужно удалить n элементов с позиции m в списке. Вместо выполнения удаления одного элемента n раз (каждый раз смещая на 1 позицию элементы, стоящие «правее» в списке), нужно выполнить смещение всех элементов, стоящих «правее» n + m позиции на n элементов «левее» к началу списка. Таким образом, вместо выполнения n итераций перемещения элементов списка, все выполняется за 1 проход.
Сколько необходимо дополнительной памяти при вызове ArrayList.add()?
Если в массиве достаточно места для размещения нового элемента, то дополнительной памяти не требуется. Иначе происходит создание нового массива размером в 1,5 раза превышающим существующий (это верно для JDK выше 1.7, в более ранних версиях размер увеличения иной).
Сколько выделяется дополнительно памяти при вызове LinkedList.add()?
Создается один новый экземпляр вложенного класса Node.
Оцените количество памяти на хранение одного примитива типа byte в LinkedList?
Каждый элемент LinkedList хранит ссылку на предыдущий элемент, следующий элемент и ссылку на данные.
|
|
|
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
//...
}
Для 32-битных систем каждая ссылка занимает 32 бита (4 байта). Сам объект (заголовок) вложенного класса Node занимает 8 байт. 4 + 4 + 4 + 8 = 20 байт, а т.к. размер каждого объекта в Java кратен 8, соответственно получаем 24 байта. Примитив типа byte занимает 1 байт памяти, но в JCF примитивы упаковываются: объект типа Byte занимает в памяти 16 байт (8 байт на заголовок объекта, 1 байт на поле типа byte и 7 байт для кратности 8). Также напомню, что значения от -128 до 127 кэшируются и для них новые объекты каждый раз не создаются. Таким образом, в x32 JVM 24 байта тратятся на хранение одного элемента в списке и 16 байт - на хранение упакованного объекта типа Byte. Итого 40 байт.
Для 64-битной JVM каждая ссылка занимает 64 бита (8 байт), размер заголовка каждого объекта составляет 16 байт (два машинных слова). Вычисления аналогичны: 8 + 8 + 8 + 16 = 40 байт и 24 байта. Итого 64 байта.
Оцените количество памяти на хранение одного примитива типа byte в ArrayList?
ArrayList основан на массиве, для примитивных типов данных осуществляется автоматическая упаковка значения, поэтому 16 байт тратится на хранение упакованного объекта и 4 байта (8 для x64) - на хранение ссылки на этот объект в самой структуре данных. Таким образом, в x32 JVM 4 байта используются на хранение одного элемента и 16 байт - на хранение упакованного объекта типа Byte. Для x64 - 8 байт и 24 байта соответственно.
Для ArrayList или для LinkedList операция добавления элемента в середину (list.add(list.size()/2, newElement)) медленнее?
Для ArrayList:
● проверка массива на вместимость. Если вместимости недостаточно, то увеличение размера массива и копирование всех элементов в новый массив (O(N));
|
|
|
● копирование всех элементов, расположенных правее от позиции вставки, на одну позицию вправо (O(N));
● вставка элемента (O(1)).
Для LinkedList:
● поиск позиции вставки (O(N));
● вставка элемента (O(1)).
В худшем случае вставка в середину списка эффективнее для LinkedList. В остальных - скорее всего, для ArrayList, поскольку копирование элементов осуществляется за счет вызова быстрого системного метода System.arraycopy().
В реализации класса ArrayList есть следующие поля: Object[] elementData, int size. Объясните, зачем хранить отдельно size, если всегда можно взять elementData.length?
Размер массива elementData представляет собой вместимость (capacity) ArrayList, которая всегда больше переменной size - реального количества хранимых элементов. При необходимости вместимость автоматически возрастает.
Почему LinkedList реализует и List, и Deque?
LinkedList позволяет добавлять элементы в начало и конец списка за константное время, что хорошо согласуется с поведением интерфейса Deque.
LinkedList — это односвязный, двусвязный или четырехсвязный список?
Двусвязный: каждый элемент LinkedList хранит ссылку на предыдущий и следующий элементы.
Как перебрать элементы LinkedList в обратном порядке, не используя медленный get(index)?
Для этого в LinkedList есть обратный итератор, который можно получить вызва метод descendingIterator().
49. Предназначение метода remove() у Iterator. Fail-Fast vs. Fail-Safe.
Что такое «fail-fast поведение»?
fail-fast поведение означает, что при возникновении ошибки или состояния, которое может привести к ошибке, система немедленно прекращает дальнейшую работу и уведомляет об этом. Использование fail-fast подхода позволяет избежать недетерминированного поведения программы в течение времени.
В Java Collections API некоторые итераторы ведут себя как fail-fast и выбрасывают ConcurrentModificationException, если после его создания была произведена модификация коллекции, т.е. добавлен или удален элемент напрямую из коллекции, а не используя методы итератора.
Реализация такого поведения осуществляется за счет подсчета количества модификаций коллекции (modification count):
● при изменении коллекции счетчик модификаций также изменяется;
● при создании итератора ему передается текущее значение счетчика;
● при каждом обращении к итератору сохраненное значение счетчика сравнивается с текущим, и, если они не совпадают, возникает исключение.
Какая разница между fail-fast и fail-safe?
В противоположность fail-fast, итераторы fail-safe не вызывают никаких исключений при изменении структуры, потому что они работают с клоном коллекции вместо оригинала.
Приведите примеры итераторов реализующих поведение fail-safe
Итератор коллекции CopyOnWriteArrayList и итератор представления keySet коллекции ConcurrentHashMap являются примерами итераторов fail-safe.
Как поведёт себя коллекция, если вызвать iterator.remove()?
Если вызову iterator.remove() предшествовал вызов iterator.next(), то iterator.remove() удалит элемент коллекции, на который указывает итератор, в противном случае будет выброшено IllegalStateException().
Как поведёт себя уже инстанциированный итератор для collection, если вызвать collection.remove()?
При следующем вызове методов итератора будет выброшено ConcurrentModificationException.
