Документ Microsoft Word (2). Что такое generic и для чего они нужны
 Скачать 82.45 Kb.
|
|
Что такое generic и для чего они нужны? Обобщенное программирование (generic programming) – описание данных и алгоритмов в программе, которое можно применить к различным типам данных не меняя при этом само это описание. Шаблон (generic) – описание класса, метода или атрибута без использования конкретного типа данных. Generics - это технический термин, обозначающий набор свойств языка позволяющих определять и использовать обобщенные типы и методы. Обобщенные типы или методы отличаются от обычных тем, что имеют типизированные параметры. Шаблоны повышают наглядность кода и снижают количество явных преобразований типа и возможных ошибок от неявных преобразований. Синтаксические конструкции с использованием шаблонов запрещены в перечислениях, исключительных ситуациях и анонимных встроенных классах. При компиляции программы происходит уничтожение информации о шаблонах (type erasure) и приведение всех обобщенных и параметризованных типов, формальных параметров типа к использованию только базового типа. Примером использования обобщенных типов может служить Java Collection Framework. Так, класс LinkedList Преимущества кода с использованием Generic по сравнению с кодом без Generic: Более строгая проверка типов во время компиляции. Отсутствие необходимости приведения типов Возможность реализации общих алгоритмов, не завязанных на конкретных типах. Зачем вообще ввели дженерики? Как до дженериков программировали? До появления дженериков использовались коллекции для хранения объектов любого типа, т.е. непатентованных. Теперь универсальные шаблоны заставляют Java-программиста хранить определенный тип объектов. https://github.com/vectree/resources/blob/master/text/00292.md Что можно поставить в дженерики, что нельзя? Что можно типизировать? Что нельзя параметризировать? Можно типизировать только ссылочные типы. Нельзя типизировать примитивные типы. Невозможно объявить статические поля, типы которых являются параметрами типа. Невозможно использовать приведение или instanceof с параметризованными типами. Как параметризировать статический метод? Public static Generic-поля не могут быть статическими, статические методы не могут иметь generic-параметры или обращаться к generic-полям. Пример: public static или: public static Wildcard - wildcard с неограниченным типом подстановки то же самое что Diamond-operator <>: используется для записи типизированных параметров внутри. Дженерики оформляются такими скобками. Основная цель diamoind <> оператора упростить использование универсальных шаблонов при создании объекта. Это позволяет избежать непроверенных предупреждений в программе и делает программу более читаемой. Всегда использовать diamond синтаксис, если мы используем типизированные типы. Иначе можно пропустить, где используется raw type. Wildcard делятся на 3 типа: Upper bounded wildcard верхняя граница unbounded wildcard Lower bounded wildcard нижняя граница C Wildcard действует принцип PECS Producer можно только читать значения (в список нельзя ничего добавить кроме null) extends предоставляет, снабжает, но записать ничего не может, кроме нуль. Consumer только вписывать из этого типа переменных. Нельзя прочитать элемент из контейнера с супер, кроме объекта класса Object. Super wildcard принимает, но предоставить ничего не может. Что такое raw type? К чему приводит использование raw type? Стирание типов? Что такое стирание и сырые типы? Raw Types (сырые типы) – Это имя универсального класса или интерфейса без каких-либо аргументов типа. их нужно избегать. Пример сырого типа List <> list = new ArrayList<>; Пример нормального типа List Стирание типов - во время компиляции компилятор имеет полную информацию о типе, но эта информация обычно намеренно отбрасывается при создании байтового кода в процессе, известном как стирание типов. Это делается таким образом из- за проблем совместимости: целью разработчиков языка было обеспечение полной совместимости исходного кода и полной совместимости байтового кода между версиями платформы. Если бы он был реализован по-другому, вам пришлось бы перекомпилировать устаревшие приложения при переходе на более новые версии платформы. Если поле типизировано дженериком, то как в байт коде будет представлен этот тип? Будет представлен как экземпляр Object. В чём отличие в записях в параметре метода: (Collection collection) и ((Collection collection)? В первом случае вместо мы можем подставить абсолютно любой тип, а во втором только T и его наследников. Параметр vs Аргумент (в дженериках)? Параметр типа (type parameter). Используются при объявлении дженерик- типов. Например, для Box Аргумент типа (type argument). Тип объекта, который может использоваться вместо параметра типа. Например, для Box Paper — это аргумент типа. Почему последняя строчка не скомпилируется? List
Слева и справа разные типы, у дженериков нет наследования в данном виде. Основ реализации коллекций List — упорядоченный список, в котором у каждого элемента есть индекс. Дубликаты значений допускаются. Set — это неупорядоченное множество уникальных элементов. Queue — очередь. В таком списке элементы можно добавлять только в хвост, а удалять — только из начала. Так реализуется концепция FIFO (first in, first out) — «первым пришёл — первым ушёл». Map состоит из пар «ключ-значение». Ключи уникальны, а значения могут повторяться. Порядок элементов не гарантирован. Map позволяет искать объекты. Map не наследуется от интерфейса Collection, но входит в состав фреймворка Collections. Коллекция контейнеры или классы для хранения наборов других элементов. Коллекции могут хранить любые ссылочные типы данных Отличие коллекции от массива? Массивы - это простые конструкции фиксированного размера, и поэтому они могут хранить только заданное количество элементов. Массивы встроены в ядро языка Java, и используемый при работе с ними синтаксис Java очень прост и понятен. Например, чтобы получить элемент массива с номером n, вам нужно вызвать функцию array[n]. Коллекции - это более сложный, но в то же время более гибкий тип данных. Прежде всего, размер коллекции можно изменять: вы можете добавлять в коллекцию любое количество элементов. Коллекции автоматически обрабатывают удаление элемента из любой позиции. Коллизия – это, когда два разных объекта попадают в одну ячейку/корзинку/связанный список. Причиной этому служит то, что они имеют одинаковый hashcode. Для более эффективной работы с HashMap, hashcode не должен повторяться для не эквивалентных объектов Если возникает коллизия (т.е. hashcode вычисленный) объектов равны, то создается связанный список node в каждой ячейке массива node, где объекты ссылаются друг на друга. Что происходит при коллизии? Мы начинаем сравнивать ключ и hashcode текущего объекта и тех, которые внутри (если, конечно, их там несколько). Сначала проверяем равны ли hashcode ключей. Если да, то сравниваем их ключ методом equals. Если equals возвращает true, значит ключи совпадают по “значению” и hashcode – производится замена, новый объект заменяет тот который уже там находится под тем же ключом, Если hashcode и “значение” ключа неравны – новый объект добавляется в конец списка. Если возникает коллизия (т.е. hashcode вычисленный) объектов равны, то создается связанный список node в каждой ячейке массива node, где объекты ссылаются друг на друга. Метод contains в ArrayList, LinkedList, HashSet? Метод contains в Arraylist использует метод indexOf (), который использует в свою очередь метод indexOfRange (). Там совершается обход элементов в цикле и если элемент не null, то вызывается стандартный метод equals (сравнение ссылок). Тоже самое для LinkedList. В методе contains HashSet используются «корзины» и поиск объекта происходит сначала по hashcode, а только потом по equals. В реализации: Метод contains вызывает (косвенно) getEntry из HashMap, где ключ - это Object, для которого вы хотите узнать, находится ли он в HashSet. Как вы можете видеть ниже, два объекта могут быть сохранены в HashMap/HashSet, даже если их ключ сопоставляется с тем же значением с помощью хэш-функции. Метод выполняет итерацию по всем ключам, которые имеют одно и то же значение хэша, и выполняет equals на каждом из них, чтобы найти соответствующий ключ. final Entry int hash = (key == null) ? 0 : hash(key.hashCode()); for (Entry e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; } Отличие ArrayList от LinkedList? Когда лучше использовать ArrayList, а когда LinkedList? ArrayList - это список на основе массива. LinkedList - связанный список на основе элементов и связи между ними. В качестве LinkedList лучше всего подходит представление вагонов поезда, сцепленных последовательно. ArrayList следует использовать, когда в приоритете доступ по индексу, так как эти операции выполняются за константное время. Добавление в конец списка в среднем тоже выполняется за константное время. Кроме того, в ArrayList нет дополнительных расходов на хранение связки между элементами. Минусы в скорости вставки/удаления элементов, находящихся не в конце списка, так как при этой операции все элементы правее добавляемого/удаляемого сдвигаются. LinkedList удобен когда важнее быстродействие операций вставки/ удаления, которые в LinkedList выполняются за константное время. Операции доступа по индексу производятся перебором с начала или конца (смотря что ближе) до нужного элемента. Дополнительные затраты на хранение связки между элементами. Одним словом - если часто вставляете/удаляете - выбирайте в пользу LinkedList, в противном случае ArrayList. Скорость ставки элемента в начало середину и конец у ArrayList vs LinkedList? У ArrayList вставка и удаление элементов в конце происходит быстро, а в середину и начало - медленно, потому что приходится сдвигать все элементы после операции с элементом. Чтоб вставить/удалить элемент в LinkedList необходимо всего лишь поменять ссылки в соседних элементах, поэтому – быстро. Mетод put. Вычисляется хеш-значение ключа введенного объекта. Хэш ключа вычисляет метод static final int hash(Object key), который уже обращается к известному методу hashCode() ключа. Для этого используется либо переопределенный метод hashCode(), либо его реализация по умолчанию. Почему бы просто не вычислить с помощью hashCode()? Это сделано из-за того, что hashCode() можно реализовать так, что только нижние биты int'a будут заполнены. Например, для Integer, Float – если мы в HashMap кладем маленькие значения, то у них и биты хеш-кодов будут заполнены только нижние. В таком случае ключи в Hash Map будут иметь тенденцию скапливаться в нижних ячейках, а верхние будут оставаться пустыми, что не очень эффективно. На то, в какой бакет попадёт новая запись, влияют только младшие биты хеша. Поэтому и придумали различными манипуляциями подмешивать старшие биты хеша в младшие, чтобы улучшить распределение по бакетам (чтобы старшие биты родного хеша объекта начали вносить коррективы в то, в какой бакет попадёт объект) и, как следствие, производительность. Потому и придумана дополнительная функция hash внутри HashMap. 1. Вычисляем индекс бакета (ячейки массива), в который будет добавлен наш элемент: i = (n - 1) & hash где n – длина массива. & - побитовое умножение (количество бакетов (16-1) приводится в битовый эквивалент, над ними производится побитовое умножение. 2. Создается объект Node (включает хеш, ключ, значение, ссылка на следующий элемент, (либо null, если его нет)). 3. Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Если в бакете пусто, тогда просто размещаем в нем элемент. Иначе хэш и ключ нового элемента поочередно сравниваются с хешами и ключами элементов из списка и, при совпадении этих параметров, значение элемента перезаписывается. Если совпадений не найдено, элемент добавляется в конец списка. Разница между Iterable и Iterator? Iterable – интерфейс, который реализуют коллекции. У него есть один метод, который производит Iterator. Iterator — объект с состоянием итерации. Он позволяет вам проверить, есть ли в нем больше элементов, используя hasNext(), и перейти к следующему элементу (если есть), используя next(). Так же есть метод remove(). итератор интерфейс, который помогает нам в прохождении через коллекцию с помощью методов, таких как hasNext (), next () и remove () с другой стороны, Iterable — это другой интерфейс, который, если он реализован классом, заставляет класс быть итерационным и является целью для каждой конструкции. Он имеет только один метод с именем iterator (), который исходит из самого интерфейса Iterator. Зачем в итераторе метод remove? В обычном цикле при итерации по коллекции нельзя изменять размер коллекции, в итераторе – можно. listIterator - что это, в чём отличие от Iterator`а? ListIterator расширяет свойства интерфейса Iterator, позволяя перемещаться по коллекции в обоих направлениях, изменять содержимое коллекции и получать текущую позицию итератора. При этом следует помнить, что ListIterator не указывает на конкретный элемент коллекции и его текущая позиция определяется двумя элементами, которые возвращают методы previous() и next(). Таким образом, модификация коллекции осуществляется для последнего элемента, который был возвращен одним из методов previous() или next(). Как работает HashMap? Расскажите подробно, как работает метод put? Внутри Hashmap имеет вложенный класс Node в котором хранятся пары ключ значения: static class Node final K key; V value; Node Node(int hash, K key, V value, Node this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } Далее внутри HashMap есть массив объектов типа Node transient Node Это и есть массив bucket. HashMap состоит из «корзин» (bucket`ов). «Корзины» — это элементы массива, которые хранят ссылки на списки элементов. При добавлении новой пары ключ-значение вычисляет хеш-код ключа, на основании которого вычисляется номер bucket’a(номер ячейки массива), в которую попадёт новый элемент. Если bucket пуст, то в него сохраняется ссылка на вновь добавляемый элемент, если же там уже есть элемент, то происходит последовательный переход по ссылкам между элементами в цепочке, в поисках последнего элемента, от которого и ставится ссылка на вновь добавленный элемент. Если в списке был найден элемент с таким же ключом, то он заменяется. Добавление, поиск и удаление элементов выполняется за константное время. Вроде все здорово, с одной оговоркой, хеш-функций должна равномерно распределять элементы по корзинам, в этом случае временная сложность для этих 3 операций будет не ниже lg N, а в среднем случае как раз константное время. Что такое Мар? Почему Мар это не коллекция? Map - это совокупность пар "ключ"-"значение». Ключ в паре ключ-значение должен быть уникальным. Соответственно некоторые методы интерфейса Collection нельзя использовать в Map. Например, метод remove(Object o) в интерфейсе Collection предназначен для удаления элемента, тогда как такой же метод remove(Object key) в интерфейсе Map - удаляет элемент по заданному ключу. Какие структуры данных вы знаете? структура данных – это контейнер, который хранит информацию в определенном виде. Из-за такой «компоновки» она может быть эффективной в одних операциях и неэффективной в других. Цель разработчика – выбрать из существующих структур оптимальный для конкретной задачи вариант. ▪ Массив (Array) ▪ Стек (Stack) ▪ Очередь (Queue) ▪ Связный список (Linked List) ▪ Дерево (Tree) ▪ Граф (Graph) ▪ Префиксное дерево (Tree) ▪ Хэш-Таблица (Hash Table) |