1. Что такое дженерики
 Скачать 0.84 Mb.
|
|
12. Расскажите про реализации интерфейса Set В множествах Set каждый элемент хранится только в одном экземпляре, а разные реализации Set используют разный порядок хранения элементов. Все классы, реализующие интерфейс Set, внутренне поддерживаются реализациями Map. В HashSet порядок элементов определяется по сложному алгоритму. TreeSet - объекты хранятся отсортированными по возрастанию в порядке сравнения LinkedHashSet - хранение элементов в порядке добавления. Множества часто используются для проверки принадлежности, чтобы вы могли легко проверить, принадлежит ли объект заданному множеству, поэтому на практике обычно выбирается реализация HashSet, оптимизированная для быстрого поиска. HashSet Класс HashSet реализует интерфейс Set, основан на хэш-таблице, а также поддерживается с помощью экземпляра HashMap. В HashSet элементы не упорядочены, нет никаких гарантий, что элементы будут в том же порядке спустя какое-то время. HashSet хранит элементы с помощью HashMap. Хоть и для добавления элемента в HashMap он должен быть представлен в виде пары «ключ-значение», в HashSet добавляется только значение. Операции добавления, удаления и поиска будут выполняться за константное время при условии, что хэш-функция правильно распределяет элементы по «корзинам». Хэш-функция — это функция, сужающая множество значений объекта до некоторого подмножества целых чисел. Класс Object имеет метод hashCode(), который используется классом HashSet для эффективного размещения объектов, заносимых в коллекцию. В классах объектов, заносимых в HashSet, этот метод должен быть переопределен (override). HashSet хранит элементы таким образом, чтобы элемент можно было очень быстро найти. Методы contains и indexOf у ArrayList проходят последовательно по элементам списка в поисках нужного элемента, а метод contains у HashSet ищет элемент многократно быстрее, так как использует совсем другой подход: элементы находятся в так называемых «корзинах» (на иллюстрации — 16 серых корзин), которые выбираются исходя из значений самих элементов (на иллюстрации — 7 зелёных элементов множества). Конструкторы HashSet : // Создание пустого набора с начальной емкостью (16) и со // значением коэффициента загрузки (0.75) по умолчанию public HashSet(); // Создание множества из элементов коллекции public HashSet(Collection c); // Создание множества с указанной начальной емкостью и со // значением коэффициента загрузки по умолчанию (0.75) public HashSet(int initialCapacity); // Создание множества с указанными начальной емкостью и по умолчанию 16 // коэффициентом загрузки по умолчанию 0.75 public HashSet(int initialCapacity, float loadFactor); Методы аналогичны методам ArrayList за исключением того, что метод add(Object o) добавляет объект в множество только в том случае, если его там нет. Возвращаемое методом значение — true, если объект добавлен, и false, если нет. Порядок добавления объектов во множество будет непредсказуемым. HashSet использует хэширование для ускорения выборки. Если вам нужно, чтобы результат был отсортирован, то пользуйтесь TreeSet. Реализация HashSet не синхронизируется. Если многократные потоки получают доступ к набору хеша одновременно, а один или несколько потоков должны изменять набор, то он должен быть синхронизирован внешне. Это лучше всего выполнить во время создания, чтобы предотвратить случайный несинхронизируемый доступ к набору : Set LinkedHashSet Класс LinkedHashSet расширяет класс HashSet, не добавляя никаких новых методов. Класс поддерживает связный список элементов набора в том порядке, в котором они вставлялись. Это позволяет организовать упорядоченную итерацию вставки в набор. Также, как и HashSet, LinkedHashSet не синхронизируется. Поэтому при использовании данной реализации в приложении с множеством потоков, часть из которых может вносить изменения в набор, следует на этапе создания выполнить синхронизацию TreeSet Проще говоря, TreeSet это отсортированная коллекция, которая расширяет класс AbstractSet и реализует интерфейс NavigableSet. Особенности: - Хранит уникальные элементы - Не сохраняет порядок вставки элементов - Сортирует элементы в порядке возрастания - не потокобезопасный - TreeSet не поддерживает добавление null, однако если бы вы написали свой собственный компаратор, который поддерживает null, то не было бы никаких проблем использовать null в качестве ключа В этой реализации объекты сортируются и хранятся в порядке возрастания в соответствии с их естественным порядком. TreeSet использует самобалансирующееся двоичное дерево поиска. По сравнению с HashSet производительность TreeSet находится на нижней стороне. Такие операции, как add , remove и search , занимают O (log n) время, в то время как такие операции, как печать n элементов в отсортированном порядке, требуют O (n) время. Будучи самобалансирующимся двоичным деревом поиска, каждый узел двоичного дерева содержит дополнительный бит, который используется для определения цвета узла, который является красным или черным. Во время последующих вставок и удалений эти «цветные» биты помогают обеспечить более или менее сбалансированное дерево. SortedSet По умолчанию сортировка производится привычным способом, но можно изменить это поведение через интерфейс Comparable. 13. В чем отличия TreeSet и HashSet? TreeSet обеспечивает упорядоченно хранение элементов в виде красно-черного дерева. Сложность выполнения основных операций не хуже O(log(N)) (Логарифмическое время). HashSet использует для хранения элементов такой же подход, что и HashMap, за тем отличием, что в HashSet в качестве ключа и значения выступает сам элемент, кроме того HashSet не поддерживает упорядоченное хранение элементов и обеспечивает временную сложность выполнения операций аналогично HashMap. 14. Чем LinkedHashSet отличается от HashSet? Класс LinkedHashSet расширяет класс HashSet, не добавляя никаких новых методов. Класс поддерживает связный список элементов набора в том порядке, в котором они вставлялись. Это позволяет организовать упорядоченную итерацию вставки в набор 15. Что будет, если добавлять элементы в TreeSet по возрастанию? такое же дерево, как и обычно. 16. Как устроен HashSet, сложность основных операций. - Т.к. класс реализует интерфейс Set, он может хранить только уникальные значения; - Может хранить NULL – значения; - Порядок добавления элементов вычисляется с помощью хэш-кода; - HashSet также реализует интерфейсы Serializable и Cloneable. Для поддержания постоянного времени выполнения операций время, затрачиваемое на действия с HashSet, должно быть прямо пропорционально количеству элементов в HashSet + «емкость» встроенного экземпляра HashMap (количество «корзин»). Поэтому для поддержания производительности очень важно не устанавливать слишком высокую начальную ёмкость (или слишком низкий коэффициент загрузки). Коэффициент загрузки = Количество хранимых элементов в таблице / размер хэш-таблицы Например, если изначальное количество ячеек в таблице равно 16, и коэффициент загрузки равен 0,75, то из этого следует, что когда количество заполненных ячеек достигнет 12, их количество автоматически увеличится. не является структурой данных с встроенной синхронизацией, поэтому если с ним работают одновременно несколько потоков, и как минимум один из них пытается внести изменения, необходимо обеспечить синхронизированный доступ извне. Set s = Collections.synchronizedSet(new HashSet(...)); 17. Как устроен LinkedHashSet, сложность основных операций. 18. Как устроен TreeSet, сложность основных операций. 19. Расскажите про интерфейс List Это тип данных, в котором каждый элемент содержит какой-то объект, а также ссылку на следующий элемент списка. Интерфейс List сохраняет последовательность добавления элементов и позволяет осуществлять доступ к элементу по индексу. List добавляет следующие методы: - void add(int index, Е obj) - вставляет obj в вызывающий список в позицию, указанную в index. Любые ранее вставленные элементы за указанной позицией вставки смещаются вверх. То есть никакие элементы не перезаписываются. - bооlеаn addAll (int index,Collection с) - вставляет все элементы в вызывающий список, начиная с позиции, переданной в index. Все ранее существовавшие элементы за точкой вставки смещаются вверх. То есть никакие элементы не перезаписываются. Возвращает true, если вызывающий список изменяется, и false в противном случае. - Е get (int index) - возвращает объект, сохраненный в указанной позиции вызывающего списка. int indexOf(Object obj) - возвращает индекс первого экземпляра obj в вызывающем списке. Если obj не содержится в списке, возвращается 1. - int lastlndexOf(Object obj) - возвращает индекс последнего экземпляра obj в вызывающем списке. Если obj не содержится в списке, возвращается 1. - Listlterator listlterator() - возвращает итератор, указывающий на начало списка. - Listlterator listlterator(int index) - возвращает итератор, указывающий на заданную позицию в списке. - Е remove(int index) - удаляет элемент из вызывающего списка в позиции index и возвращает удаленный элемент. Результирующий список уплотняется, то есть элементы, следующие за удаленным, сдвигаются на одну позицию назад. - Е set (int index, Е obj) - присваивает obj элементу, находящемуся в списке в позиции index. default void sort(Comparator c) - сортирует список, используя заданный компаратор (добавлен в версии JDК 8). - List subList (int start, int end) - возвращает список, включающий элементы от start до end-1 из вызывающего списка. Элементы из возвращаемого списка также сохраняют ссылки в вызывающем списке. 20. Как устроен ArrayList, сложность основных операций. ArrayList хранит элементы в динамическом массиве. Элементы ArrayList могут быть абсолютно любых типов в том числе и null. Основное преимущество такой коллекции над массивом – это расширяемость – увеличение длины при надобности. Если в этом массиве заканчивается место, то создаётся второй массив побольше, куда копируются все элементы из первого. Затем второй массив занимает место первого, а первый – выбрасывается (будет уничтожен сборщиком мусора). Длина нового массива рассчитывается так (3*n)/2+1, где n – это длина старого массива. Т.е. если старый массив был длиной 100 элементов, то новый будет 300/2+1 = 151 При добавлении элемента в середину ArrayList, все элементы справа от него копируются на 1 позицию вправо, а затем в пустую ячейку добавляется новый элемент. По возможности, избегайте операций вставки в середину коллекции. Ведь системе приходится заново пересчитывать индексы элементов. При удалении элемента из середины, все элементы справа от него копируются на 1 позицию влево. Сам массив не укорачивается (можно укоротить через trimToSize()). Особенности — Быстрый доступ к элементам по индексу за время O(1); — Доступ к элементам по значению за линейное время O(n); — Медленный, когда вставляются и удаляются элементы из «середины» списка; — Позволяет хранить любые значения в том числе и null; — Не синхронизирован. 21. Как устроен LinkedList, сложность основных операций. Связный список состоит из одинаковых элементов, которые хранят данные и хранят ссылки на следующий и предыдущий элементы. Вся работа с LinkedList сводится к изменению ссылок. Однако, у LinkedList есть отдельные методы для работы с началом и концом списка, которых нет в ArrayList: addFirst(), addLast(): методы для добавления элемента в начало/конец списка Вставка и удаление в середину LinkedList устроены гораздо проще, чем в ArrayList. Мы просто переопределяем ссылки соседних элементов, а ненужный элемент “выпадает” из цепочки ссылок. Особенности: — Из LinkedList можно организовать стэк, очередь, или двойную очередь, со временем доступа O(1) [константное время - поскольку выполняется единственная команда для его обнаружения]; — На вставку и удаление из середины списка, получение элемента по индексу или значению потребуется линейное время O(n) [линейное время - Например, процедура, суммирующая все элементы списка, требует время, пропорциональное длине списка]. Однако, на добавление и удаление из середины списка, используя ListIterator.add() и ListIterator.remove(), потребуется O(1); — Позволяет добавлять любые значения в том числе и null. Для хранения примитивных типов использует соответствующие классы-оберки; — Не синхронизирован. LinkedList содержит все те методы, которые определены в интерфейсах List, Queue, Deque. Некоторые из них: addFirst() / offerFirst(): добавляет элемент в начало списка addLast() / offerLast(): добавляет элемент в конец списка removeFirst() / pollFirst(): удаляет первый элемент из начала списка removeLast() / pollLast(): удаляет последний элемент из конца списка getFirst() / peekFirst(): получает первый элемент getLast() / peekLast(): получает последний элемент 22. Почему LinkedList реализует и List, и Deque? LinkedList — класс, реализующий два интерфейса — List и Deque. Это обеспечивает возможность создания двунаправленной очереди из любых (в том числе и null) элементов. Каждый объект, помещенный в связанный список, является узлом (нодом). Каждый узел содержит элемент, ссылку на предыдущий и следующий узел. Фактически связанный список состоит из последовательности узлов, каждый из которых предназначен для хранения объекта определенного при создании типа. 23. Чем отличаются ArrayList и LinkedList? ArrayList это список, реализованный на основе массива, а LinkedList — это классический двусвязный список, основанный на объектах с ссылками между ними. ArrayList: - доступ к произвольному элементу по индексу за константное время O(1); - доступ к элементам по значению за линейное время O(N); - вставка в конец в среднем производится за константное время O(1); - удаление произвольного элемента из списка занимает значительное время т.к. при этом все элементы, находящиеся «правее» смещаются на одну ячейку влево (реальный размер массива (capacity) не изменяется); - вставка элемента в произвольное место списка занимает значительное время т.к. при этом все элементы, находящиеся «правее» смещаются на одну ячейку вправо; - минимум накладных расходов при хранении. LinkedList: - на получение элемента по индексу или значению потребуется линейное время O(N); - на добавление и удаление в начало или конец списка потребуется константное O(1); - вставка или удаление в/из произвольного место константное O(1); - требует больше памяти для хранения такого же количества элементов, потому что кроме самого элемента хранятся еще указатели на следующий и предыдущий элементы списка. В целом, LinkedList в абсолютных величинах проигрывает ArrayList и по потребляемой памяти, и по скорости выполнения операций. LinkedList предпочтительно применять, когда нужны частые операции вставки/удаления или в случаях, когда необходимо гарантированное время добавления элемента в список. Для ArrayList или для LinkedList операция добавления элемента в середину (list.add(list.size()/2, newElement)) медленнее? Для ArrayList: -проверка массива на вместимость. Если вместимости недостаточно, то увеличение размера массива и копирование всех элементов в новый массив (O(N)); -копирование всех элементов, расположенных правее от позиции вставки, на одну позицию вправо (O(N)); -вставка элемента (O(1)). Для LinkedList: -поиск позиции вставки (O(N)); -вставка элемента (O(1)). В худшем случае вставка в середину списка эффективнее для LinkedList. В остальных - скорее всего, для ArrayList, поскольку копирование элементов осуществляется за счет вызова быстрого системного метода System.arraycopy(). 24. Что такое Queue? Queue - это очередь, которая обычно (но необязательно) строится по принципу FIFO (First-In-First- Out) - соответственно извлечение элемента осуществляется с начала очереди, вставка элемента - в конец очереди. Хотя этот принцип нарушает, к примеру, PriorityQueue, использующая «natural ordering» или переданный Comparator при вставке нового элемента. Особенностью PriorityQueue является возможность управления порядком элементов. По- умолчанию, элементы сортируются с использованием «natural ordering», но это поведение может быть переопределено при помощи объекта Comparator, который задаётся при создании очереди. Данная коллекция не поддерживает null в качестве элементов. Используя PriorityQueue, можно, например, реализовать алгоритм Дейкстры для поиска кратчайшего пути от одной вершины графа к другой. Либо для хранения объектов согласно определённого свойства. 25. Что такое Dequeue? Чем отличается от Queue? Deque (Double Ended Queue) расширяет Queue и согласно документации, это линейная коллекция, поддерживающая вставку/извлечение элементов с обоих концов. Помимо этого, реализации интерфейса Deque могут строится по принципу FIFO, либо LIFO. Реализации и Deque, и Queue обычно не переопределяют методы equals() и hashCode(), вместо этого используются унаследованные методы класса Object, основанные на сравнении ссылок. 26. Приведите пример реализации Dequeue. ArrayDeque (также известный как «Array Double Ended Queue», произносится как «ArrayDeck») - это особый вид растущего массива, который позволяет нам добавлять или удалять элементы с обеих сторон. Реализация ArrayDeque может использоваться как Stack (последний пришел-первый вышел) или Queue (первый пришел-первый вышел) Под капотом ArrayDeque поддерживается массив, который удваивает свой размер при заполнении. Первоначально, массив инициализируется с размером 16. Он реализован как двусторонняя очередь, где он поддерживает два указателя, а именно голову и хвост. ArrayDeque: • Это не потокобезопасный • Нулевые элементы не принимаются • Работает значительно быстрее, чем синхронизированный Stack • Более быстрая очередь, чем LinkedList из-за лучшей локализации. Большинство операций амортизировали сложность с постоянным временем • Iterator , возвращаемый ArrayDeque , является отказоустойчивым • ArrayDeque автоматически удваивает размер массива, когда head и хвостовой указатель встречает друг друга при добавлении элемента Deque |