Блок Примитивные типы
 Скачать 6.67 Mb.
|
|
§ Массив (Array) § Стек (Stack) § Очередь (Queue) § Связный список (Linked List) § Дерево (Tree) § Граф (Graph) § Префиксное дерево (Trie) § Хэш-Таблица (Hash Table) Отличие коллекции от массива? Массивы - это простые конструкции фиксированного размера, и поэтому они могут хранить только заданное количество элементов. Массивы встроены в ядро языка Java, и используемый при работе с ними синтаксис Java очень прост и понятен. Например, чтобы получить элемент массива с номером n, вам нужно вызвать функцию array[n]. Коллекции - это более сложный, но в то же время более гибкий тип данных. Прежде всего, размер коллекции можно изменять: вы можете добавлять в коллекцию любое количество элементов. Коллекции автоматически обрабатывают удаление элемента из любой позиции. На чём основаны основные реализации коллекций. List — упорядоченный список, в котором у каждого элемента есть индекс. Дубликаты значений допускаются. Set — это неупорядоченное множество уникальных элементов. Queue — очередь. В таком списке элементы можно добавлять только в хвост, а удалять — только из начала. Так реализуется концепция FIFO (first in, first out) — «первым пришёл — первым ушёл». Map состоит из пар «ключ-значение». Ключи уникальны, а значения могут повторяться. Порядок элементов не гарантирован. Map позволяет искать объекты (значения) по ключу. Map не наследуется от интерфейса Collection, но входит в состав фреймворка Collections. Методы интерфейса 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, данный метод возвращает массив объектов типа, переданного в параметре. Отличие ArrayList от LinkedList? Когда лучше использовать ArrayList, а когда LinkedList? ArrayList - это список на основе массива. LinkedList - связанный список на основе элементов и связи между ними. В качестве LinkedList лучше всего подходит представление вагонов поезда сцепленных последовательно. ArrayList следует использовать, когда в приоритете доступ по индексу, так как эти операции выполняются за константное время. Добавление в конец списка в среднем тоже выполняется за константное время. Кроме того, в ArrayList нет дополнительных расходов на хранение связки между элементами. Минусы в скорости вставки/удаления элементов, находящихся не в конце списка, так как при этой операции все элементы правее добавляемого/удаляемого сдвигаются. LinkedList удобен когда важнее быстродействие операций вставки/удаления, которые в LinkedList выполняются за константное время. Операции доступа по индексу производятся перебором с начала или конца (смотря что ближе) до нужного элемента. Дополнительные затраты на хранение связки между элементами. Одним словом - если часто вставляете/удаляете - выбирайте в пользу LinkedList, в противном случае ArrayList. Скорость ставки элемента в начало середину и конец у ArrayList vs LinkedList? У ArrayList вставка и удаление элементов в конце происходит быстро, а в середину и начало - медленно, потому что приходится сдвигать все элементы после операции с элементом. Чтоб вставить/удалить элемент в LinkedList необходимо всего лишь поменять ссылки в соседних элементах, поэтому – быстро. В чём разница между 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? Только в первом элементе. По условиями красно-черного дерева, то есть отсортированного дерева, элементы идут по возрастанию, поэтому null может содержаться только в корне дерева. Как работает 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 с нулевыми значениями. HashSet - хэш-множество. Хранит данные в хэш-таблице, которая вычисляет для каждого объекта хэш-код. Хэш-код - это целочисленное значение, которое вычисляется определенным способом из данных объекта, при этом для разных объектов будет разное значение. В Java хэш-таблицы реализованы в виде массивов связных списков. Каждый такой список называется группой. Чтобы найти место объекта в таблице, вычисляется его хэш-код и его модуль уменьшается до общего количества групп. Полученное значение будет индексом группы элемента. Начиная с Java 8 в группах вместо связных списков используются сбалансированные двоичные деревья. В стандартной библиотеке используется количество групп выраженное степенью 2 (по умолчанию 16). Любое указываемое значение количества групп автоматически округляется до следующей степени 2. Если хэш-таблица становится чрезмерно заполненной, она хэшируется повторно. Для этого сознается новая хэш-таблица с большим количеством групп, все элементы переносятся в новую таблицу. Хэш-таблица автоматически хэшируется повторно с увеличенным вдвое количеством групп при превышении коэффициента загрузки, который по умолчанию равен 0.75 (75%). хранит элементы с помощью хэширования содержит только уникальные элементы данные хранятся в произвольном порядке на основе хэш-кода допускает значение null быстрое нахождение объектов начальная емкость по умолчанию 16, коэффициент загрузки 0.75 не синхронизирован Как работает метод contains в ArrayList, LinkedList, HashSet? Метод contains в Arraylist использует метод indexOf (), который использует в свою очередь метод indexOfRange (). Там совершается обход элементов в цикле и если элемент не null, то вызывается стандартный метод equals (сравнение ссылок). Тоже самое для LinkedList. В методе contains HashSet используются «корзины» и поиск объекта происходит сначала по hashcode, а только потом по equals. Что такое HashMap? Это ассоциативный массив данных. Структура данных, которая хранит пары ключ-значение. HashMap это фактически массив (table), который хранит ссылки на связанные списки (LinkedList), в которых и хранятся объекты. Каждому элементу массива соответствует один список. Как работает HashMap? HashMap работает по принципам хэширования. Хеширование в простейшем представлении, это – способ преобразования любой переменной/объекта в уникальный код после применения любой формулы/алгоритма к их свойствам. Настоящая функция хеширования, должна следовать следующему правилу: Хеш-функция должна возвращать одинаковый хеш-код всякий раз, когда она применена к одинаковым или равным объектам. Другими словами, два одинаковых объекта должны возвращать одинаковые хеш-коды по очереди. Конструкторы класса: public HashMap() — создает хеш-отображение по умолчанию: объемом (capacity) = 16 и с коэффициентом загруженности (load factor) = 0.75; public HashMap(Map< ? extends K, ? extends V> m) — создает хеш-отображение, инициализируемое элементами другого заданного отображения с той начальной емкостью, которой хватит вместить в себя элементы другого отображения; public HashMap(int initialCapacity) — создает хеш-отображение с заданной начальной емкостью. Для корректной и правильной работы HashMap размер внутреннего массива обязательно должен быть степенью двойки (т.е. 16, 64, 128 и т.д.); public HashMap(int initialCapacity, float loadFactor) — создает хеш-отображение с заданными параметрами: начальной емкостью и коэффициентом загруженности. 23) Что такое Node в HashMap? Что содержит? Node (узел) это внутренний класс в классе HashMap, имплементирует интерфейс Map.Entry 24) Расскажите подробно, как работает метод put в HashMap? Первым делом, проверяется существует ли ключ (равен ли null). Если ключ не существует (null), значение помещается в таблицу на нулевую позицию, потому что хеш-код для значения null, это – всегда 0. На следующем шаге, рассчитывается хеш-значение используя хеш-код ключа, получаемый вызовом метода hashCode(). Теперь вызывается функция indexFor(hash, table.length), для вычисления точной позиции (индекса в массиве), куда будет помещен объект Node. Объекты Node хранятся в форме LinkedList. Когда объект Node должен быть помещен в определенное место, HashMap проверяет нет ли уже в этом месте записи. Если записи нету, то объект помещается в данную позицию. Если все же в данной позиции уже есть объект, то происходит последовательный переход по ссылкам между элементами в цепочке, в поисках последнего элемента, от которого и ставится ссылка на вновь добавленный элемент. Если в списке был найден элемент с таким же ключом, то он заменяется. Добавление, поиск и удаление элементов выполняется за константное время, при условии, что хеш-функция должна равномерно распределять элементы по корзинам, в этом случае временная сложность для этих 3 операций будет не ниже lg N, а в среднем случае как раз константное время. 25) Как работает метод get в HashMap? Способ, которым определяется уникальность ключа в методе put(), имеет ту же логику, которую применяет метод get(). Как только HashMap определяет ключ объекта, переданного в аргументе, он просто возвращает значение соответствующего объекта Node. Если же совпадений не найдено, метод get() вернет null. 26) Что происходит при коллизии? Мы начинаем сравнивать ключ и hashcode текущего объекта и тех которые внутри (если конечно их там несколько). Сначала проверяем равны ли hashcode ключей. Если да, то сравниваем их ключ методом equals. Если equals возвращает true, значит ключи совпадают по “значению” и hashcode – производится замена, новый объект заменяет тот который уже там находится под тем же ключом, Если hashcode и “значение” ключа неравны – новый объект добавляется в конец списка. 27) Как расширяется HashMap? Условия перестраивания HashMap в красно-чёрное дерево? Первоначальный размер HashMap - 16 бакетов (бакет это ячейка массива). Когда массив заполняется на 75% (loadFactory= 0,75), размер массива увеличивается в 2 раза, т.е. 32 бакета. И так далее (64, 128 …). При увеличении размера массива все объекты, уже содержащиеся в HashMap, будут распределены уже по новым бакетам с учётом их нового количества. Каждый бакет содержит в себе ноды (пары ключ-значение), когда эти нодов становится 8, а бакетов 64, то структура Node перестраивается в красно-черное дерево (TreeNode). 28) Почему Map — это не Collection, в то время как List и Set являются Collection? Коллекция (List и Set) представляет собой совокупность некоторых элементов (обычно экземпляров одного класса). Map - это совокупность пар "ключ"-"значение". Соответственно некоторые методы интерфейса Collection нельзя использовать в Map. Например, метод remove(Object o) в интерфейсе Collection предназначен для удаления элемента, тогда как такой же метод remove(Object key) в интерфейсе Map - удаляет элемент по заданному ключу. 29) Может ли null быть ключём в HashMap? HashMap оперирует с null-ключом без каких-либо проблем. Его hash всегда равен 0. 30) Как обойти HashMap через for-each? Метод entrySet() возвращает набор всех элементов в виде объектов Map.Entry for (Map.Entry System.out.printf("Key: %d Value: %s \n", e.getKey(), e.getValue()); } 31) Что такое бинарное дерево? Двоичное дерево — структура данных, в которой каждый узел (родительский) имеет не более двух потомков (правый и левый наследник). Двоичное дерево поиска строится по определенным правилам: - каждый узел имеет не более двух детей; - каждое значение, меньшее, чем значение узла, становится левым ребенком или ребенком левого ребенка; - каждое значение, большее или равное значению узла, становится правым ребенком или ребенком правого ребенка. 32) Что такое черно-красное дерево? Это один из видов самобалансирующихся бинарных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и позволяющее быстро выполнять основные операции дерева поиска: добавление, удаление и поиск узла. 33) В чём разница между Iterable и Iterator? Iterable – интерфейс, который реализуют коллекции. У него есть один метод, который производит Iterator. Iterator — объект с состоянием итерации. Он позволяет вам проверить, есть ли в нем больше элементов, используя hasNext(), и перейти к следующему элементу (если есть), используя next(). Так же есть метод remove(). 34) Зачем в итераторе метод remove? В обычном цикле при итерации по коллекции нельзя изменять размер коллекции, в итераторе – можно. 35) ListIterator - что это, в чём отличие от Iterator`а? ListIterator расширяет свойства интерфейса Iterator, позволяя перемещаться по коллекции в обоих направлениях, изменять содержимое коллекции и получать текущую позицию итератора. При этом следует помнить, что ListIterator не указывает на конкретный элемент коллекции и его текущая позиция определяется двумя элементами, которые возвращают методы previous() и next(). Таким образом, модификация коллекции осуществляется для последнего элемента, который был возвращен одним из методов previous() или next(). 36) Можно ли с помощью цикла for-each изменить поле объектов, которые находятся в массиве? И можно ли изменить сам объект? Элемент из КОЛЛЕКЦИИ в цикле for-each удалить нельзя, т.к. нельзя проводить одновременно итерацию (перебор) коллекции и изменение ее элементов. Итератор этого учесть не может. Значения элементов массива менять можно! Блок 7. Функциональные интерфейсы, Streams Чем является Stream в контексте Java? Интерфейс java.util.Stream представляет собой последовательность элементов, над которой можно производить различные операции. У стрима может быть сколько угодно вызовов промежуточных операций и последним вызов конечной операции. При этом все промежуточные операции выполняются лениво и пока не будет вызвана конечная операция никаких действий на самом деле не происходит. Stream API — это новый способ работать со структурами данных в функциональном стиле. Stream (поток) API (описание способов, которыми одна компьютерная программа может взаимодействовать с другой программой) — это по своей сути поток данных. Сам термин "поток" довольно размыт в программировании в целом и в Java в частности. Для чего нужен? С появлением Java 8 Stream API позволило программистам писать существенно короче то, что раньше занимало много строк кода, а именно — упростить работу с наборами данных, в частности, упростить операции фильтрации, сортировки и другие манипуляции с данными. Если у вас промежуточных операций нет, часто можно и нужно обойтись без стрима, иначе код будет сложнее чем без потока. Потоки данных обеспечивают представление данных, позволяющее выполнять вычисления на более высоком концептуальном уровне, чем коллекции. Средствами Stream API можно оптимизировать вычисления, используя, допустим, несколько потоков исполнения для расчета сумм, подсчета и объединения результатов. |