6 Дженерики, коллекции. Что такое дженерики
 Скачать 360 Kb.
|
|
Что такое List? List - это интерфейс для создания простых, упорядоченных списков, который расширяют функцональность интерфейса Collection. Объекты хранятся в порядке их добавления в список. Доступ к элементам списка осуществляется по индексу. Методы List • void add(int index, E obj): добавляет в список по индексу index объект obj • boolean addAll(int index, Collection col): добавляет в список по индексу index все элементы коллекции col. Если в результате добавления список был изменен, то возвращается true, иначе возвращается false • E get(int index): возвращает объект из списка по индексу index • int indexOf(Object obj): возвращает индекс первого вхождения объекта obj в список. Если объект не найден, то возвращается -1 • int lastIndexOf(Object obj): возвращает индекс последнего вхождения объекта obj в список. Если объект не найден, то возвращается -1 • ListIterator • static • E remove(int index): удаляет объект из списка по индексу index, возвращая при этом удаленный объект • E set(int index, E obj): присваивает значение объекта obj элементу, который находится по индексу index • void sort(Comparator comp): сортирует список с помощью компаратора comp • List Как происходит вставка элемента Для этого используется метод add(). При добавлении элементов фактически происходит перераспределение памяти - создание нового массива и копирование в него элементов из старого массива. Отличия List от Set? Множества — неупорядоченные коллекции, тогда как списки — упорядоченные, где каждый элемент имеет индекс начинающийся с нуля. Списки могут содержать два и более одинаковых элемента (в том числе null), а множества не могут. В List все идет по порядку добавления. В Set нет повторяющихся элементов. Что такое ArrayList? как реализован? Класс ArrayList – это по умолчанию встроенная реализация интерфейса List. Класс ArrayList представляет обобщенную коллекцию, которая наследует свою функциональность от класса AbstractList и реализует следующие интерфейсы: List, RandomAccess, Cloneable, Serializable. Проще говоря, ArrayList представляет простой список, аналогичный массиву, за тем исключением, что количество элементов в нем не фиксировано. При добавлении элементов фактически происходит перераспределение памяти - создание нового массива и копирование в него элементов из старого массива. Что такое LinkedList? Обобщенный класс LinkedList Как устроен LinkedList LinkedList — класс, реализующий два интерфейса — List и Deque. Это обеспечивает возможность создания двунаправленной очереди из любых (в том числе и null) элементов. Все дело во внутреннем устройстве класса LinkedList. Вместо массива там используется двусвязный список. Каждый объект, помещенный в связанный список, является узлом (нодом). Каждый узел содержит элемент, ссылку на предыдущий и следующий узел. Фактически связанный список состоит из последовательности узлов, каждый из которых предназначен для хранения объекта определенного при создании типа. Перечислите поля Node? E item; Node Node • prev — хранит ссылку на предыдущий объект типа Node. • item — хранит значение – элемент списка. • next — хранит ссылку на следующий объект типа Node. Отличие ArrayList и LinkedList? ArrayList это список, реализованный на основе массива, а LinkedList — это классический связный список, основанный на объектах с ссылками между ними. LinkedList - двусвязный список. Когда лучше использовать ArrayList, а когда LinkedList. В целом же, LinkedList в абсолютных величинах проигрывает ArrayList и по потребляемой памяти и по скорости выполнения операций. LinkedList предпочтительно применять, когда происходит активная работа (вставка/удаление) с серединой списка или в случаях, когда необходимо гарантированное время добавления элемента в список. ArrayList реализован на массивах. (используют если чаще читаются элементы, чем добавляются) Хранит свои элементы в массиве. • + осуществляется быстрый поиск элементов. • + меньше расхходует памятина хранение элементов • - увеличение ArrayList'a происходит медленно. • - при вставке элемента (или удалении) в середину или в начало, приходится переписывать все элементы. LinkedList является представителем двунаправленного списка. (цепочка) (используется если элементы чаще добавляются чем читаются) Хранит свои элементы в обектах у которых есть ссылки на предыдущий и следующий элементы. • + быстрая вставка и удаление в середину списка (переписать next и prev и всё) • - долгий поиск в середине (нужно перебрать все элементы) в среднем, сложности одинаковые. Но я бы не стал рекомендовать использовать LinkedList, за исключением ситуации когда, преобладает удаление или вставка в начало или конец списка. Скорость вставки элемента в начало середину и конец у ArrayList и LinkedList.
Как работает метод contains в ArrayList и LinkedList и HashMap. Метод коллекции contains() позволяет проверить наличие определенного элемента в наборе. Процесс проверки выполняется в цикле для всех элементов набора пока не будет найден соответствующий «эквивалент». При сравнении объектов используется метод equals() элемента набора. Поэтому, необходимо быть внимательным, если набор включает сложные объекты, для которых требуется метод equals() переписать. Через вызов метода IndexOf(объект) – метод совершает обход (у LinkedList обход совершается через итератор Node) и при нахождении элемента возвращает его индекс, при не нахождении возвращает -1, contains сравнивает вернувшее значение с 0 и возвращает true или false в зависимости от результата сравнения. Для hashSet вызывается map.containsKey(o) затем getNode (там берется сначала корзина по хэшу и длине массива, затем ищется по хэшу и equals уже нужный ключ, возвращает кей или null (если не найден ключ) сравнивается != с null и возвращается значение тру или фолс. Отличие двусвязного и односвязного списка? "Связной" список, или другими словами односвязный - список, где каждый элемент ссылается только на один следующий. У последнего нет ссылки. "Двусвязной" или двусвязный - список, где каждый элемент ссылается на следующий и предыдущий. Первый и последний cоотвественно не имеют ссылок на предыдущий и следующий. LinkedList реализует сразу три интерфейса List, Queue, Dequeue. То есть это структура, которая хранит порядок элементов, поддерживает добавление элементов с обеих концов и позволяет себя обходить с обеих направлений. Или в терминологии вопроса - двусвязный (двунаправленный) список. Что такое Iterator Это шаблон проектирования для прохода по всем элементам множества. Например foreach реализован с использованием итератора. Одним из ключевых методов интерфейса Collection является метод Iterator Интерфейс Iterator имеет следующее определение: public interface Iterator E next(); boolean hasNext(); void remove(); } В каких случаях нужно использовать iterator. Почему Позволяет единообразно обходить элементы любой коллекции не зависимо от структруры (массивы, связные списки или деревья). Необходим если в процессе обхода нужно будет удалять элементы коллекции. При удалении элемента в процессе обхода for each циклом будет выброшено ConcurrentModificationException, а при обход обычным for при удалении элементов, идущих подряд результат может быть непредсказуемым. *при достижении конца коллекции метод next() выбрасывает исключение NoSuchElementException. Зачем в итераторе метод remove remove — единственный безопасный способ изменить коллекцию во время итерации. В чём разница между Iterable и Iterator Интерфейс Iterable находится в пакете java.lang и имплементация этого интерфейса позволяет объекту быть итерируемым с помощью for-each. Из под реализации Iterable можно вызвать iterator. И не один. И даже в нескольких потоках. А может и не использовать итератор вовсе. Интерфейс Iterator находится в пакете java.util. В его имплементации задаются правила обхода коллекции. • Iterable (какое) - итерируемое. То, по чему можно итерироваться. Имплементируется классом, по которому нужно будет итерироваться. • Iterator (кто/что) - инструмент итерирования по коллекции. Итератор - это отдельный класс, как правило вложенный в итерируемый класс, который задает логику итерации по итерируемому. И, естественно, имплементирует интерфейс Iterator. ListIterator - что это, в чём отличие от обычного Интерфейс ListIterator расширяет интерфейс Iterator и используется для двустороннего обхода списка и видоизменения его элементов. ListIterator можно получить вызывая метод listIterator() для коллекций, реализующих List. Как реализовать Iterator? Чтобы реализовать итерируемую структуру данных, нам необходимо: 1. Реализовать интерфейс Iterable вместе с его методами в указанной структуре данных. 2. Создайте класс Iterator, реализующий интерфейс Iterator и соответствующие методы. Чтобы реализовать итератор, нам нужен курсор или указатель, чтобы отслеживать, на каком элементе мы сейчас находимся. В зависимости от базовой структуры данных мы можем переходить от одного элемента к другому. Это делается в методе next(), который возвращает текущий элемент, а курсор переходит к следующему элементу. Перед перемещением указателя мы проверяем, существует ли следующий элемент. т.е. мы можем изобразить закулисный код следующим образом: 1. Пока(iterator.hasNext()) { //если следующий элемент существует 2. next(); // продвигаем указатель 3. } курсора полностью зависит от структуры данных. Например, в связанном списке мы бы инициализировали курсор элементом head. В списке массивов мы бы инициализировали курсор нулевым элементом. С точки зрения реализации: • Если класс Iterator реализован как внутренний класс, мы можем просто использовать ключевое слово this (например, курсор = CustomDataStructure.this.element) для доступа к нужному элементу. • Если класс Iterator реализован как отдельный класс, мы можем передать этот объект структуры данных конструктору класса iterator. Iterable предоставляет метод, который возвращает Iterator. Как он это делает? Реализация интерфейса Iterable позволяет объекту использовать цикл for-each. Это достигается внутренним вызовом метода iterator(). Также метод iterator() возвращает Iterator, для перебора объекта этого класса. Абстрактные итераторы методы для обхода элементов, необходимых для определения, в общем, есть так три способа: IsDone() - чтобы определить конец траверса. Remove() - удалить метод текущего объекта Интерфейс Queue  Этот интерфейс описывает коллекции с предопределённым способом вставки и извлечения элементов, а именно — очереди FIFO (first-in-first-out). Помимо методов, определённых в интерфейсе Collection, определяет дополнительные методы для извлечения и добавления элементов в очередь. PriorityQueue — является единственной прямой реализацией интерфейса Queue (была добавлена, как и интерфейс Queue, в Java 1.5), не считая класса LinkedList, который так же реализует этот интерфейс, но был реализован намного раньше. Особенностью данной очереди является возможность управления порядком элементов. По умолчанию, элементы сортируются с использованием «natural ordering», но это поведение может быть переопределено при помощи объекта Comparator, который задаётся при создании очереди. Данная коллекция не поддерживает null в качестве элементов. ArrayDeque — реализация интерфейса Deque, который расширяет интерфейс Queue методами, позволяющими реализовать конструкцию вида LIFO (last-in-first-out). Интерфейс Deque и реализация ArrayDeque были добавлены в Java 1.6. Эта коллекция представляет собой реализацию с использованием массивов, подобно ArrayList, но не позволяет обращаться к элементам по индексу и хранение null. Как заявлено в документации, коллекция работает быстрее чем Stack, если используется как LIFO коллекция, а также быстрее чем LinkedList, если используется как FIFO. В чём разница между Queue и Deque и Stack. Queue обеспечивает порядок данных согласно принципу FIFO (стандартная очередь.) Stack реализует порядок согласно принципу LIFO. "last in — first out" Deque реализует возможность работы одновременно с началом и с концом структуры данных. Обобщенный интерфейс Queue Stack – LIFO коллекция. То есть добавлять и удалять элементы можно только с одного конца. Кроме того, стек наследуется от Vector, и тоже является пересинхронизированным и устаревшим. Его документация явно рекомендует использовать Deque. Очередь (Queue) - это как конвейер. С одной стороны кладешь, с другой забираешь. Стек (Stack) - как обойма пистолета, что последним кладешь, то первым забираешь. Двунаправленная очередь (Deque) - совмещает в себе очередь и стек. Вы можете добавлять значения как в начало так и в конец, так же и забирать их либо по принципу стека, либо по принципу очереди, придумать "живой" пример затруднительно, но затею можно понять, изучив методы этого инструмента. Это такой ящик с двумя отверстиями, в который вы что то можете класть и с одной и с другой стороны, так же и забирать. Например, кладем слева и забираем слева (как стек) или кладем слева, а забираем справа (как очередь) или с другой стороны подходим и делаем то же самое. На чём основаны основные реализации коллекций. Например, ArrayList построен на Object[ ]. 10 млн. эл-тов. Нужно в начало, середину и конец вставить по 100 тыс. эл-тов. Нужно выбрать более эффективную проекцию: ArrayList или LinkedList. Начало - LinkedList. Середина - ArrayList. Конец - ArrayList. ArrayList - метод, который сдвигает массив нативный, поэтому операция будет быстрее, чем с LinkedList (Пробежать по всем элементам). Какая внутренняя структура данных находится внутри HashMap? Массив связных списков, т.е. массив каждый элемент которого является связным списком - ассоциативный массив. Внутри HashMap располагается массив Node’ов, у них есть 4 поля: хэш, ключ, значение, ссылка на следующий элемент. Перегрузка какого метода m будет вызвана, что при этом произойдёт? public class Ex1 { public static void main(String[] args) { List Gen gen = new Gen(); gen.m(integerList); } static class Gen for (T s : collection) { System.out.println(s); } } for (String s : list) { System.out.println(s); } } } } Что произойдет? Почему отработает 2 метод? Как это исправить? Отработает второй А так? 1. public class Ex1 { public static void main(String[] args) { List Gen gen = newGen(); gen.m(integerList); } static class Gen for (T s : collection) { System.out.println(s); } } for (String s : list) { System.out.println(s); } } } } Отработает первый Есть интерфейс Iterable и интерфейс Iterator. Iterable - стоит самый первый в иерархии. Нужно реализовать метод, который возвращает экземпляр итератора. Как его реализовать, если итератор - это интерфейс? Создается приватный вложенный класс, который реализует интерфейс итератор. ковариантность, контрвариантность, инвариантность Ковариантность, контравариантность и инвариантность Ковариантность — это сохранение иерархии наследования исходных типов в производных типах в том же порядке. Например, если Кошка — это подтип Животные, то Множество<Кошки> — это подтип Множество<Животные>. Следовательно, с учетом принципа подстановки можно выполнить такое присваивание: Множество<Животные> = Множество<Кошки> Контравариантность — это обращение иерархии исходных типов на противоположную в производных типах. Например, если Кошка — это подтип Животные, то Множество<Животные> — это подтип Множество<Кошки>. Следовательно, с учетом принципа подстановки можно выполнить такое присваивание: Множество<Кошки> = Множество<Животные> Инвариантность — отсутствие наследования между производными типами. Если Кошка — это подтип Животные, то Множество<Кошки> не является подтипом Множество<Животные> и Множество<Животные> не является подтипом Множество<Кошки>. Что именно хранят arrayList и LinkedList - ссылки или объекты ArrayList хранит ссылки, а LL хранит объекты - node, а внутри ссылки Преимущества Дженериков В какой момент времени создается хешмапа? В момент вызова метода put() Если создать хешмапу размером 30. Каким размером она будет создана Т.к по умолчанию 16, а вместимость увеличивается на два, то будет создана размером 32 По какой коллекции обязательно проходиться итератором Set, так как у этой коллекции нет индексов Какой бакет будет у null ключа c 0 хешкодом в hashmap? 0 Как вычислить индекс бакета в мапе если совсем упрощённо, то мы получим индекс бакета взяв остаток от деления хэшкода на количество бакетов (длинну массива) Если мапа расширяется что происходит с элементами Элементы перераспределяются, бакеты пересчитываются Начальная ёмкость хэшмапы и максимальная Начальная – 16, максимальная - константа (2 в 30 степени) |