ОглавлениеCore
 Скачать 1.53 Mb.
|
|
List vs. Set Разница между списком и множеством в Java: Список – это упорядоченная последовательность элементов, тогда как Set – это отдельный список элементов, который не упорядочен. Список допускает дублирование, а Set не допускает дублирование элементов. Список разрешает любое количество нулевых значений в своей коллекции, а Set разрешает только одно нулевое значение в своей коллекции. Список может быть вставлен как в прямом, так и в обратном направлении с помощью Listiterator, тогда как Set можно просматривать только в прямом направлении с помощью итератора. Map не в Collection Интерфейс Map реализован классами: • Hashtable – хеш-таблица, методы которой синхронизированы. Не позволяет использовать null в качестве значения или ключа и не является упорядоченной. • HashMap – хеш-таблица. Позволяет использовать null в качестве значения или ключа и не является упорядоченной. • LinkedHashMap – упорядоченная реализация хеш-таблицы. • TreeMap – реализация, основанная на красно-черных деревьях. Является упорядоченной и предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator либо сохраняет элементы с использованием «natural ordering». • WeakHashMap – реализация хеш-таблицы, которая организована с использованием weak references для ключей (сборщик мусора автоматически удалит элемент из коллекции при следующей сборке мусора, если на ключ этого элемента нет жестких ссылок). В чем разница между классами java.util.Collection и java.util.Collections? java.util.Collections – набор статических методов для работы с коллекциями. java.util.Collection – один из основных интерфейсов Java Collections Framework. Чем отличается ArrayList от LinkedList? В каких случаях лучше использовать первый, а в каких второй? ArrayList это список, реализованный на основе массива, а LinkedList – это классический двусвязный список, основанный на объектах с ссылками между ними. ArrayList: • доступ к произвольному элементу по индексу за константное время O(1); • доступ к элементам по значению за линейное время O(N); • вставка в конец в среднем производится за константное время O(1); • удаление произвольного элемента из списка занимает значительное время, т. к. при этом все элементы, находящиеся «правее», смещаются на одну ячейку влево (реальный размер массива (capacity) не изменяется); • вставка элемента в произвольное место списка занимает значительное время, т. к. при этом все элементы, находящиеся «правее», смещаются на одну ячейку вправо; • минимум накладных расходов при хранении. LinkedList: • на получение элемента по индексу или значению потребуется линейное время O(N); • на добавление и удаление в начало или конец списка потребуется константное O(1); • вставка или удаление в/из произвольного место линейное O(N); • требует больше памяти для хранения такого же количества элементов, потому что кроме самого элемента хранятся еще указатели на следующий и предыдущий элементы списка. В целом LinkedList в абсолютных величинах проигрывает ArrayList и по потребляемой памяти и по скорости выполнения операций. LinkedList предпочтительно применять, когда нужны частые операции вставки/удаления или в случаях, когда необходимо гарантированное время добавления элемента в список. Что работает быстрее ArrayList или LinkedList? Смотря какие действия будут выполняться над структурой. См. Чем отличается ArrayList от LinkedList. Какое худшее время работы метода contains() для элемента, который есть в LinkedList? O(N). Время поиска элемента линейно пропорционально количеству элементов в списке. Какое худшее время работы метода contains() для элемента, который есть в ArrayList? O(N). Время поиска элемента линейно пропорционально количеству элементов в списке. Какое худшее время работы метода add() для LinkedList? O(N). Добавление в начало/конец списка осуществляется за время O(1). Какое худшее время работы метода add() для ArrayList? O(N). Вставка элемента в конец списка осуществляется за время O(1), но если вместимость массива недостаточна, то происходит создание нового массива с увеличенным размером и копирование всех элементов из старого массива в новый. Необходимо добавить 1 млн. элементов, какую структуру вы используете? Однозначный ответ можно дать только исходя из информации о том, в какую часть списка происходит добавление элементов, что потом будет происходить с элементами списка, существуют ли какие-то ограничения по памяти или скорости выполнения. См. Чем отличается ArrayList от LinkedList. Как происходит удаление элементов из ArrayList? Как меняется в этом случае размер ArrayList? При удалении произвольного элемента из списка все элементы, находящиеся «правее», смещаются на одну ячейку влево и реальный размер массива (его емкость, capacity) не изменяется никак. Механизм автоматического «расширения» массива существует, а вот автоматического «сжатия» нет, можно только явно выполнить «сжатие» командой trimToSize(). Предложите эффективный алгоритм удаления нескольких рядом стоящих элементов из середины списка, реализуемого ArrayList Допустим, нужно удалить 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 item; Node Node //... } Для 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(). Что такое «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. Как избежать ConcurrentModificationException во время перебора коллекции? • попробовать подобрать другой итератор, работающий по принципу fail-safe, к примеру, для List можно использовать ListIterator; • использовать ConcurrentHashMap и CopyOnWriteArrayList; • преобразовать список в массив и перебирать массив; • блокировать изменения списка на время перебора с помощью блока synchronized. Отрицательная сторона последних двух вариантов – ухудшение производительности. Чем различаются Enumeration и Iterator? Хотя оба интерфейса и предназначены для обхода коллекций, между ними имеются существенные различия: • с помощью Enumeration нельзя добавлять/удалять элементы; • в Iterator исправлены имена методов для повышения читаемости кода (Enumeration.hasMoreElements() соответствует Iterator.hasNext(), Enumeration.nextElement() соответствует Iterator.next() и т. д); • Enumeration присутствуют в устаревших классах, таких как Vector/Stack, тогда как Iterator есть во всех современных классах-коллекциях. Что произойдет при вызове Iterator.next() без предварительного вызова Iterator.hasNext()? Если итератор указывает на последний элемент коллекции, то возникнет исключение NoSuchElementException, иначе будет возвращен следующий элемент. Сколько элементов будет пропущено, если Iterator.next() будет вызван после 10-ти вызовов Iterator.hasNext()? Нисколько – hasNext() осуществляет только проверку наличия следующего элемента. Как между собой связаны Iterable и Iterator? Интерфейс Iterable имеет только один метод iterator(), который возвращает Iterator. Как между собой связаны Iterable, Iterator и «for-each»? Классы, реализующие интерфейс Iterable, могут применяться в конструкции for-each, которая использует Iterator. Comparator vs. Comparable Интерфейс Comparable является хорошим выбором, когда он используется для определения порядка по умолчанию или, другими словами, если это основной способ сравнения объектов. Зачем же использовать Comparator, если уже есть Comparable? Есть несколько причин: • иногда нельзя изменить исходный код класса, чьи объекты необходимо отсортировать, что делает невозможным использование Comparable; • использование компараторов позволяет избежать добавления дополнительного кода в классы домена; • можно определить несколько разных стратегий сравнения, что невозможно при использовании Comparable. Сравните Iterator и ListIterator • ListIterator расширяет интерфейс Iterator; • ListIterator может быть использован только для перебора элементов коллекции List; • Iterator позволяет перебирать элементы только в одном направлении при помощи метода next(), тогда как ListIterator позволяет перебирать список в обоих направлениях при помощи методов next() и previous(); • ListIterator не указывает на конкретный элемент: его текущая позиция располагается между элементами, которые возвращают методы previous() и next(); • при помощи ListIterator можно модифицировать список, добавляя/удаляя элементы с помощью методов add() и remove(), Iterator не поддерживает данного функционала. Зачем добавили ArrayList, если уже был Vector? • методы класса Vector синхронизированы, а ArrayList нет; • по умолчанию Vector удваивает свой размер, когда заканчивается выделенная под элементы память, ArrayList же увеличивает свой размер только на половину; • Vector это устаревший класс и его использование не рекомендовано. Сравните интерфейсы Queue и Deque. Кто кого расширяет: Queue расширяет Deque или Deque расширяет Queue? Queue – это очередь, которая обычно (но необязательно) строится по принципу FIFO (First- In-First-Out). Соответственно извлечение элемента осуществляется с начала очереди, вставка элемента – в конец очереди. Хотя этот принцип нарушает, к примеру, PriorityQueue, использующая «natural ordering» или переданный Comparator при вставке нового элемента. Deque (Double Ended Queue) расширяет Queue и согласно документации это линейная коллекция, поддерживающая вставку/извлечение элементов с обоих концов. Помимо этого реализации интерфейса Deque могут строится по принципу FIFO либо LIFO. Реализации и Deque, и Queue обычно не переопределяют методы equals() и hashCode(), вместо этого используются унаследованные методы класса Object, основанные на сравнении ссылок. Что позволяет сделать PriorityQueue? Особенностью PriorityQueue является возможность управления порядком элементов. По умолчанию элементы сортируются с использованием «natural ordering», но это поведение может быть переопределено при помощи объекта Comparator, который задается при создании очереди. Данная коллекция не поддерживает null в качестве элементов. Используя PriorityQueue, можно, например, реализовать алгоритм Дейкстры для поиска кратчайшего пути от одной вершины графа к другой. Либо для хранения объектов согласно определенного свойства. Зачем нужен HashMap, если есть Hashtable? • методы класса Hashtable синхронизированы, что приводит к снижению производительности, а HashMap – нет; • HashTable не может содержать элементы null, тогда как HashMap может содержать один ключ null и любое количество значений null; • Iterator у HashMap в отличие от Enumeration у HashTable работает по принципу «fail- fast» (выдает исключение при любой несогласованности данных); • Hashtable – это устаревший класс и его использование не рекомендовано. Как устроен HashMap? HashMap состоит из «корзин» (buckets). С технической точки зрения «корзины» – это элементы массива, которые хранят ссылки на списки элементов. При добавлении новой пары «ключ-значение» вычисляется хеш-код ключа, на основании которого вычисляется номер корзины (номер ячейки массива), в которую попадет новый элемент. Если корзина пустая, то в нее сохраняется ссылка на вновь добавляемый элемент, если там уже есть элемент, то происходит последовательный переход по ссылкам между элементами в цепочке в поисках последнего элемента, от которого и ставится ссылка на вновь добавленный элемент. Если в списке был найден элемент с таким же ключом, то он заменяется. |