Документ Microsoft Word (2). Что такое generic и для чего они нужны
 Скачать 82.45 Kb.
|
|
Отличие между Queue и Deque и Stack? Queue (одностороняя очередь) - когда элементы можно получить в том порядке, в котором добавляли. FIFO (первым вошёл, первым вышел). Dequeue (двусторонняя очередь) - можно вставлять/получать элементы из начали и конца. Stack работает по схеме LIFO (последним вошел, первым вышел). Всякий раз, когда вызывается новый метод, содержащий примитивные значения или ссылки на объекты, то на вершине стека под них выделяется блок памяти. Отличие List от Set? 3 реализации Set -> Упорядоченность в HashSet, LinkedHashSet, TreeSet (Какая упорядоченность в какой и почему)? List хранит объекты в порядке вставки, элемент можно получить по индексу. Set не может хранить одинаковых элементов. К семейству интерфейса Set относятся HashSet, TreeSet и LinkedHashSet. В множествах Set разные реализации используют разный порядок хранения элементов. В HashSet порядок элементов на основе hash-таблиц, оптимизирован для быстрого поиска. В контейнере TreeSet объекты хранятся на основе «деревьев» отсортированными по возрастанию. LinkedHashSet хранит элементы в порядке добавления. Null в TreeSet? Только в первом элементе. Методы интерфейса Collection add(Object o) Добавление элемента в коллекцию, если он отсутствует. Возвращает true, если элемент добавлен. addAll(Collection c) Добавление элементов коллекции, если они отсутствуют. clear() Очистка коллекции. contains(Object o) Проверка присутствия элемента в наборе. Возвращает true, если элемент найден. containsAll(Collection c) Проверка присутсвия коллекции в наборе. Возвращает true, если все элементы содержатся в наборе. equals(Object o) Проверка на равенство. hashCode() Получение hashCode набора. isEmpty() Проверка наличия элементов. Возвращает true если в коллекции нет ни одного элемента. iterator() Функция получения итератора коллекции. remove(Object o) Удаление элемента из набора. removeAll(Collection c) Удаление из набора всех элементов переданной коллекции. retainAll(Collection c) Удаление элементов, не принадлежащих переданной коллекции. size() Количество элементов коллекции toArray() Преобразование набора в массив элементов. toArray(T[] a) Преобразование набора в массив элементов. В отличии от предыдущего метода, который возвращает массив объектов типа Object, данный метод возвращает массив объектов типа, переданного в параметре. Как работает HashSet? Почему в HashSet вместо value не null, а new Object? Класс HashSet реализует интерфейс Set, основан на хэш-таблице, а также поддерживается с помощью экземпляра HashMap. В HashSet элементы не упорядочены, нет никаких гарантий, что элементы будут в том же порядке спустя какое-то время. Операции добавления, удаления и поиска будут выполняться за константное время при условии, что хэш- функция правильно распределяет элементы по «корзинам», о чем будет рассказано далее. Т.к. класс реализует интерфейс Set, он может хранить только уникальные значения; Может хранить NULL – значения; Порядок добавления элементов вычисляется с помощью хэш-кода; HashSet также реализует интерфейсы Serializable и Cloneable. HashSet хранит new Object(), потому что в контракте указывается метод remove() который возвращает true, если указанный объект существовал и был удален. Для этого он использует обёртку, HashMap#remove() который возвращает удаленное значение. Если бы вы сохранили null вместо объекта, то вызов HashMap#remove() вернул бы бы null, что было бы неотличимо от результата попытки удалить несуществующий объект, и контракт HashSet.remove() не мог бы быть выполнен. Говоря простым языком, HashSet построен практически как HashMap с нулевыми значениями. Бинарное дерево? Двоичное дерево — структура данных, в которой каждый узел (родительский) имеет не более двух потомков (правый и левый наследник). Двоичное дерево поиска строится по определенным правилам: - каждый узел имеет не более двух детей; - каждое значение, меньшее, чем значение узла, становится левым ребенком или ребенком левого ребенка; - каждое значение, большее или равное значению узла, становится правым ребенком или ребенком правого ребенка. Черно-красное дерево? Это один из видов самобалансирующихся бинарных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и позволяющее быстро выполнять основные операции дерева поиска: добавление, удаление и поиск узла. Как расширяется HashMap? Условия перестраивания HashMap в красно-чёрное дерево? Первоначальный размер HashMap - 16 бакетов (бакет это ячейка массива). Когда массив заполняется на 75% (loadFactory = 0,75), размер массива увеличивается в 2 раза, т.е. 32 бакета. И так далее (64, 128 …). При увеличении размера массива все объекты, уже содержащиеся в HashMap, будут распределены уже по новым бакетам с учётом их нового количества. Каждый бакет содержит в себе ноды (пары ключ-значение), когда эти нодов становится 8, а бакетов 64, то структура Node перестраивается в красно- черное дерево (TreeNode). Почему Map — это не Collection, в то время как List и Set являются Collection? Коллекция (List и Set) представляет собой совокупность некоторых элементов (обычно экземпляров одного класса). Map - это совокупность пар "ключ"-"значение". Соответственно некоторые методы интерфейса Collection нельзя использовать в Map. Например, метод remove(Object o) в интерфейсе Collection предназначен для удаления элемента, тогда как такой же метод remove(Object key) в интерфейсе Map - удаляет элемент по заданному ключу. Может ли null быть ключём в HashMap? HashMap оперирует с null-ключом без каких-либо проблем. Его hash всегда равен 0. Как обойти HashMap через for-each? Метод entrySet() возвращает набор всех элементов в виде объектов Map.Entry for (Map.Entry System.out.printf("Key: %d Value: %s \n", e.getKey(), e.getValue()); } Что такое HashMap? Это ассоциативный массив данных. Структура данных, которая хранит пары ключ-значение. HashMap это фактически массив (table), который хранит ссылки на связанные списки (LinkedList), в которых и хранятся объекты. Каждому элементу массива соответствует один список. Как работает HashMap? HashMap работает по принципам хэширования. Хеширование в простейшем представлении, это – способ преобразования любой переменной/объекта в уникальный код после применения любой формулы/алгоритма к их свойствам. Настоящая функция хеширования, должна следовать следующему правилу: Хеш-функция должна возвращать одинаковый хеш-код всякий раз, когда она применена к одинаковым или равным объектам. Другими словами, два одинаковых объекта должны возвращать одинаковые хеш-коды по очереди. Что такое Node в HashMap? Что содержит? Node (узел) это внутренний класс в классе HashMap, имплементирует интерфейс Map.Entry Как работает метод put в HashMap? Первым делом, проверяется существует ли ключ (равен ли null). Если ключ не существует (null), значение помещается в таблицу на нулевую позицию, потому что хеш-код для значения null, это – всегда 0. На следующем шаге, рассчитывается хеш-значение используя хеш-код ключа, получаемый вызовом метода hashCode(). Теперь вызывается функция indexFor(hash, table.length), для вычисления точной позиции (индекса в массиве), куда будет помещен объект Node. Объекты Node хранятся в форме LinkedList. Когда объект Node должен быть помещен в определенное место, HashMap проверяет нет ли уже в этом месте записи. Если записи нету, то объект помещается в данную позицию. Если все же в данной позиции уже есть объект, то происходит последовательный переход по ссылкам между элементами в цепочке, в поисках последнего элемента, от которого и ставится ссылка на вновь добавленный элемент. Если в списке был найден элемент с таким же ключом, то он заменяется. Добавление, поиск и удаление элементов выполняется за константное время, при условии, что хеш-функция должна равномерно распределять элементы по корзинам, в этом случае временная сложность для этих 3 операций будет не ниже lg N, а в среднем случае как раз константное время. Как работает метод get в HashMap? Способ, которым определяется уникальность ключа в методе put(), имеет ту же логику, которую применяет метод get(). Как только HashMap определяет ключ объекта, переданного в аргументе, он просто возвращает значение соответствующего объекта Node. Если же совпадений не найдено, метод get() вернет null. Что такое «коллекция»? «Коллекция» - это структура данных, набор каких-либо объектов. Данными (объектами в наборе) могут быть числа, строки, объекты пользовательских классов и т.п. Назовите основные интерфейсы JCF и их реализации. На вершине иерархии в Java Collection Framework располагаются 2 интерфейса: Collection и Map. Эти интерфейсы разделяют все коллекции, входящие во фреймворк на две части по типу хранения данных: простые последовательные наборы элементов и наборы пар «ключ — значение» соответственно. Интерфейс Collection расширяют интерфейсы: List (список) представляет собой коллекцию, в которой допустимы дублирующие значения. Реализации: ArrayList - инкапсулирует в себе обычный массив, длина которого автоматически увеличивается при добавлении новых элементов. Элементы такой коллекции пронумерованы, начиная от нуля, к ним можно обратиться по индексу. LinkedList (двунаправленный связный список) - состоит из узлов, каждый из которых содержит как собственно данные, так и две ссылки на следующий и предыдущий узел. Vector — реализация динамического массива объектов, методы которой синхронизированы. Stack — реализация стека LIFO (last-in-first-out). Set (сет) описывает неупорядоченную коллекцию, не содержащую повторяющихся элементов. Реализации: HashSet - использует HashMap для хранения данных. В качестве ключа и значения используется добавляемый элемент. Из-за особенностей реализации порядок элементов не гарантируется при добавлении. LinkedHashSet — гарантирует, что порядок элементов при обходе коллекции будет идентичен порядку добавления элементов. TreeSet — предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator, либо сохраняет элементы с использованием «natural ordering». Queue (очередь) предназначена для хранения элементов с предопределённым способом вставки и извлечения FIFO (first-in-first-out): PriorityQueue — предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator, либо сохраняет элементы с использованием «natural ordering». ArrayDeque — реализация интерфейса Deque, который расширяет интерфейс Queue методами, позволяющими реализовать конструкцию вида LIFO (last-in-first-out). Интерфейс Map реализован классами: Hashtable — хэш-таблица, методы которой синхронизированы. Не позволяет использовать null в качестве значения или ключа и не является упорядоченной. HashMap — хэш-таблица. Позволяет использовать null в качестве значения или ключа и не является упорядоченной. LinkedHashMap — упорядоченная реализация хэш-таблицы. TreeMap — реализация, основанная на красно-чёрных деревьях. Является упорядоченной и предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator, либо сохраняет элементы с использованием «natural ordering». WeakHashMap — реализация хэш-таблицы, которая организована с использованием weak references для ключей (сборщик мусора автоматически удалит элемент из коллекции при следующей сборке мусора, если на ключ этого элемента нет жёстких ссылок). Расположите в виде иерархии следующие интерфейсы: List, Set, Map, SortedSet, SortedMap, Collection, Iterable, Iterator, NavigableSet, NavigableMap. Iterable Collection List Set SortedSet NavigableSet Map SortedMap NavigableMap Iterator Почему Map — это не Collection, в то время как List и Set являются Collection? Collection представляет собой совокупность некоторых элементов. Map - это совокупность пар «ключ-значение». В чем разница между классами java.util.Collection и java.util.Collections? java.util.Collections - набор статических методов для работы с коллекциями. java.util.Collection - один из основных интерфейсов Java Collections Framework. Что такое «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. Чем различаются Enumeration и Iterator. Хотя оба интерфейса и предназначены для обхода коллекций между ними имеются существенные различия: с помощью Enumeration нельзя добавлять/удалять элементы; в Iterator исправлены имена методов для повышения читаемости кода (Enumeration.hasMoreElements() соответствует Iterator.hasNext(), Enumeration.nextElement() соответствует Iterator.next() и т.д); Enumeration присутствуют в устаревших классах, таких как Vector/Stack, тогда как Iterator есть во всех современных классах-коллекциях. Как между собой связаны Iterable и Iterator? Интерфейс Iterable имеет только один метод - iterator(), который возвращает Iterator. Как между собой связаны Iterable, Iterator и «for-each»? Классы, реализующие интерфейс Iterable, могут применяться в конструкции for-each, которая использует Iterator. Сравните Iterator и ListIterator. ListIterator расширяет интерфейс Iterator ListIterator может быть использован только для перебора элементов коллекции List; Iterator позволяет перебирать элементы только в одном направлении, при помощи метода next(). Тогда как ListIterator позволяет перебирать список в обоих направлениях, при помощи методов next() и previous(); ListIterator не указывает на конкретный элемент: его текущая позиция располагается между элементами, которые возвращают методы previous() и next(). При помощи ListIterator вы можете модифицировать список, добавляя/удаляя элементы с помощью методов add() и remove(). Iterator не поддерживает данного функционала. Что произойдет при вызове Iterator.next() без предварительного вызова Iterator.hasNext()? Если итератор указывает на последний элемент коллекции, то возникнет исключение NoSuchElementException, иначе будет возвращен следующий элемент. Сколько элементов будет пропущено, если Iterator.next() будет вызван после 10-ти вызовов Iterator.hasNext()? Нисколько - hasNext() осуществляет только проверку наличия следующего элемента. Как поведёт себя коллекция, если вызвать iterator.remove()? Если вызову iterator.remove() предшествовал вызов iterator.next(), то iterator.remove() удалит элемент коллекции, на который указывает итератор, в противном случае будет выброшено IllegalStateException(). Как поведёт себя уже инстанциированный итератор для collection, если вызвать collection.remove()? При следующем вызове методов итератора будет выброшено ConcurrentModificationException. Как избежать ConcurrentModificationException во время перебора коллекции? Попробовать подобрать или реализовать самостоятельно другой итератор, работающий по принципу fail-safe. Использовать ConcurrentHashMap и CopyOnWriteArrayList. Преобразовать список в массив и перебирать массив. Блокировать изменения списка на время перебора с помощью блока synchronized. Отрицательная сторона последних двух вариантов - ухудшение производительности. Какая коллекция реализует дисциплину обслуживания FIFO? FIFO, First-In-First-Out («первым пришел-первым ушел») - по этому принципу построена коллекция Queue. Какая коллекция реализует дисциплину обслуживания FILO? FILO, First-In-Last-Out («первым пришел, последним ушел») - по этому принципу построена коллекция Stack. |