Ревью 6 Java Core. Преимущества кода с использованием Generic по сравнению с кодом без Generic
 Скачать 271.48 Kb.
|
|
Review 6 с Что такое Обобщения — это параметризованные типы. Сих помощью можно объявлять классы, интерфейсы и методы, где тип данных указан в виде параметра. Обобщения добавили в язык безопасность типов. Преимущества кода с использованием Generic по сравнению с кодом без Generic: - Более строгая проверка типов вовремя компиляции- Отсутствие необходимости приведения типов- Возможность реализации общих алгоритмов, не завязанных на конкретных типах. Что было до дженериков? До появления дженериков использовались коллекции для хранения объектов любого типа, те. непатентованных. Теперь универсальные шаблоны заставляют программиста хранить определенный тип объектов. Что можно поставить в дженерики, что нельзя Что можно типизировать? Что нельзя параметризировать? Можно типизировать только ссылочные типы. Нельзя типизировать примитивные типы. Невозможно объявить статические поля, типы которых являются параметрами типа. Невозможно использовать приведение или instanceof с параметризованными типами. Как параметризировать статический метод Public static Пример: public static return m.iterator().next();}; 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 ArrayList<>; Они нужны только для поддержки обратной совместимости кода, сырые типы являются не «типобезопасными». Если вы не указали тип, например, своей коллекции, то туда можно запихнуть другой объект любого типа Стирание типов - вовремя компиляции компилятор имеет полную информацию о типе, но эта информация обычно намеренно отбрасывается при создании байтового кода в процессе, известном как стирание типов. Это делается таким образом из-за проблем совместимости целью разработчиков языка было обеспечение полной совместимости исходного кода и полной совместимости байтового кода между версиями платформы. Если бы он был реализован подруг ому, вам пришлось бы перекомпилировать устаревшие приложения при переходе на более новые версии платформы. Если поле типизировано дженериком, то как в байт коде будет представлен этот тип? Будет представлен как экземпляр В чем отличие в записях в параметре метода (Collection collection) и ((Collection collection)? В первом случае вместо мы можем подставить абсолютно любой типа во втором только T и его наследников. Параметр vs Аргумент (в дженериках)? Параметр типа (type parameter). Используются при объявлении дженерик- типов. Например, для Box Аргумент типа (type argument). Тип объекта, который может использоваться вместо параметра типа. Например, для Box Paper — это аргумент типа. Статические методы как они типизируются Collection? Как параметризовать статический метод? Generic-поля не могут быть статическими, статические методы не могут иметь параметры или обращаться к generic-полям. Пример: public static return Почему последняя строчка не скомпилируется? List ArrayList
Основ реализации коллекций — упорядоченный список, в которому каждого элемента есть индекс. Дубликаты значений допускаются — это неупорядоченное множество уникальных элементов — очередь. В таком списке элементы можно добавлять только в хвоста удалять — только изначала. Так реализуется концепция FIFO (first in, first out) — первым пришёл — первым ушёл». Map состоит из пар «ключ-значение». Ключи уникальны, а значения могут повторяться. Порядок элементов не гарантирован. Map позволяет искать объекты (значения) по ключу Map не наследуется от интерфейса Collection, но входит в состав фреймворка Коллекция контейнеры или классы для хранения наборов других элементов. Коллекции могут хранить любые ссылочные типы данных Отличие коллекции от массива? Массивы - это простые конструкции фиксированного размера, и поэтому они могут хранить только заданное количество элементов. Массивы встроены в ядро языка Java, и используемый при работе сними синтаксис Java очень прости понятен. Например, чтобы получить элемент массива с номером n, вам нужно вызвать функцию array[n]. Коллекции - это более сложный, нов тоже время более гибкий тип данных. Прежде всего, размер коллекции можно изменять вы можете добавлять в коллекцию любое количество элементов. Коллекции автоматически обрабатывают удаление элемента из любой позиции. Коллизия это когда два разных объекта попадают в одну ячейку/корзинку/связанный список. Причиной этому служит то, что они имеют одинаковый hashcode. Для более эффективной работы сне должен повторяться для неэквивалентных объектов Если возникает коллизия (те. hashcode вычисленный) объектов равны, то создается связанный список node в каждой ячейке массива node, где объекты ссылаются друг на друга Что происходит при коллизии? Мы начинаем сравнивать ключи текущего объекта и тех которые внутри (если конечно их там несколько. Сначала проверяем равны ли hashcode ключей. Если да, то сравниваем их ключ методом Если equals возвращает true, значит ключи совпадают по значению и hashcode – производится замена, новый объект заменяет тот который уже там находится под тем же ключом, Если hashcode и значение ключа неравны – новый объект добавляется вконец списка. Если возникает коллизия (те. hashcode вычисленный) объектов равны, то создается связанный список node в каждой ячейке массива node, где объекты ссылаются друг на друга Метод contains в ArrayList, LinkedList, HashSet? Метод contains в Arraylist использует метод indexOf (), который использует в свою очередь метод indexOfRange (). Там совершается обход элементов в цикле и если элемент не null, то вызывается стандартный метод equals (сравнение ссылок. Тоже самое для В методе contains HashSet используются корзины и поиск объекта происходит сначала по hashcode, а только потом по equals. В реализации: Метод contains вызывает (косвенно) getEntry из HashMap, где ключ - это Object, для которого вы хотите узнать, находится ли он в Как вы можете видеть ниже, два объекта могут быть сохранены в HashMap/HashSet, даже если их ключ сопоставляется стем же значением с помощью хэш-функции. Метод выполняет итерацию по всем ключам, которые имеют одно и тоже значение хэша, и выполняет equals на каждом из них, чтобы найти соответствующий ключ Entry int hash = (key == null) ? 0 : hash(key.hashCode()); for (Entry e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return Отличие ArrayList от LinkedList? Когда лучше использовать ArrayList, а когда LinkedList? ArrayList - это список на основе массива. LinkedList - связанный список на основе элементов и связи между ними. В качестве LinkedList лучше всего подходит представление вагонов поезда сцепленных последовательно следует использовать, когда в приоритете доступ по индексу, так как эти операции выполняются за константное время. Добавление вконец списка в среднем тоже выполняется за константное время. Кроме того, в ArrayList нет дополнительных расходов на хранение связки между элементами. Минусы вскорости вставки/удаления элементов, находящихся не в конце списка, так как при этой операции все элементы правее добавляемого/удаляемого сдвигаются удобен когда важнее быстродействие операций вставки/ удаления, которые в LinkedList выполняются за константное время Операции доступа по индексу производятся перебором сначала или конца смотря что ближе) до нужного элемента. Дополнительные затраты на хранение связки между элементами. Одним словом - если часто вставляете/удаляете - выбирайте в пользу LinkedList, в противном случае Скорость ставки элемента в начало середину и конец у ArrayList vs LinkedList? У ArrayList вставка и удаление элементов в конце происходит быстро, а в середину и начало - медленно, потому что приходится сдвигать все элементы после операции с элементом. Чтоб вставить/удалить элемент в LinkedList необходимо всего лишь поменять ссылки в соседних элементах, поэтому – быстро. Коллизия это когда два разных объекта попадают в одну ячейку/корзинку/связанный список. Причиной этому служит то, что они имеют одинаковый hashcode. Для более эффективной работы сне должен повторяться для неэквивалентных объектов Если возникает коллизия (те. hashcode вычисленный) объектов равны, то создается связанный список node в каждой ячейке массива node, где объекты ссылаются друг на друга Что происходит при коллизии? Мы начинаем сравнивать ключи текущего объекта и тех которые внутри (если конечно их там несколько. Сначала проверяем равны ли hashcode ключей. Если да, то сравниваем их ключ методом Если equals возвращает true, значит ключи совпадают по значению и hashcode – производится замена, новый объект заменяет тот который уже там находится под тем же ключом, Если hashcode и значение ключа неравны – новый объект добавляется вконец списка. Если возникает коллизия (те. hashcode вычисленный) объектов равны, то создается связанный список node в каждой ячейке массива node, где объекты ссылаются друг на друга Mетод put. 1. Вычисляется хеш-значение ключа введенного объекта. Хэш ключа вычисляет метод 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) приводится в битовый эквивалент, над ними производится побитовое умножение. Создается объект Node (включает хеш, ключ, значение, ссылка наследующий элемент, (либо null, если его нет. Теперь, зная индекс в массиве, мы получаем список цепочку) элементов, привязанных к этой ячейке. Если в бакете пусто, тогда просто размещаем в нем элемент. Иначе хэш и ключ нового элемента поочередно сравниваются с хешами и ключами элементов из списка и, при совпадении этих параметров, значение элемента перезаписывается. Если совпадений не найдено, элемент добавляется вконец списка. Разница между Iterable и Iterator? Iterable – интерфейс, который реализуют коллекции. У него есть один метод, который производит Iterator. Iterator — объект с состоянием итерации. Он позволяет вам проверить, есть ливнем больше элементов, используя hasNext(), и перейти к следующему элементу (если есть, используя next(). Также есть метод итератор интерфейс, который помогает нам в прохождении через коллекцию с помощью методов, таких как hasNext (), next () и remove () с другой стороны, Iterable — это другой интерфейс, который, если он реализован классом, заставляет класс быть итерационными является целью для каждой конструкции. Он имеет только один метод с именем iterator (), который исходит из самого интерфейса Iterator. Зачем в итераторе метод remove? В обычном цикле при итерации по коллекции нельзя изменять размер коллекции, в итераторе – можно - что это, в чём отличие от а ListIterator расширяет свойства интерфейса Iterator, позволяя перемещаться по коллекции в обоих направлениях, изменять содержимое коллекции и получать текущую позицию итератора. При этом следует помнить, что ListIterator не указывает на конкретный элемент коллекции и его текущая позиция определяется двумя элементами, которые возвращают методы previous() и next(). Таким образом, модификация коллекции осуществляется для последнего элемента, который был возвращен одним из методов previous() или Как работает HashMap? Расскажите подробно, как работает метод Внутри Hashmap имеет вложенный класс Node в котором хранятся пары ключ значения class Node final int hash; final K key; V value; Node Node(int hash, K key, V value, Node this.hash = hash; 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 HashMap состоит из корзин (bucket`ов). Корзины — это элементы массива, которые хранят ссылки на списки элементов. При добавлении новой пары ключ-значение вычисляет хеш-код ключа, на основании которого вычисляется номер номер ячейки массива, в которую попадёт новый элемент. Если bucket пуст, тов него сохраняется ссылка на вновь добавляемый элемент, если же там уже есть элемент, то происходит последовательный переход по ссылкам между элементами в цепочке, в поисках последнего элемента, от которого и ставится ссылка на вновь добавленный элемент. Если в списке был найден элемент с таким же ключом, то он заменяется. Добавление, поиски удаление элементов выполняется за константное время. Вроде все здорово, с одной оговоркой, хеш-функций должна равномерно распределять элементы по корзинам, в этом случае временная сложность для этих 3 операций будет не ниже lg N, а в среднем случае как раз константное время. Что такое Мар? Почему Мар это не коллекция Map - это совокупность пар "ключ"-"значение». Ключ в паре ключ-значение должен быть уникальным. Соответственно некоторые методы интерфейса Collection нельзя использовать в Map. Например, метод remove(Object o) в интерфейсе Collection предназначен для удаления элемента, тогда как такой же метод remove(Object key) в интерфейсе Map - удаляет элемент по заданному ключу. Какие структуры данных вызнаете структура данных – это контейнер, который хранит информацию в определенном виде. Из-за такой компоновки она может быть эффективной в одних операциях и неэффективной в других. Цель разработчика – выбрать из существующих структур оптимальный для конкретной задачи вариант. ▪ Массив (Стек (Очередь (Связный список (Linked Дерево (Граф (Префиксное дерево (Tree) ▪ Хэш-Таблица (Hash Отличие между Queue и Deque и Stack? Queue (одностороняя очередь) - когда элементы можно получить в том порядке, в котором добавляли. FIFO (первым вошёл, первым вышел (двусторонняя очередь) - можно вставлять/получать элементы из начали и конца работает по схеме LIFO (последним вошел, первым вышел. Всякий раз, когда вызывается новый метод, содержащий примитивные значения или ссылки на объекты, тона вершине стека под них выделяется блок памяти. Отличие List от Set? 3 реализации Set -> Упорядоченность в HashSet, LinkedHashSet, TreeSet (Какая упорядоченность в какой и почему List хранит объекты в порядке вставки, элемент можно получить по индексу. Set не может хранить одинаковых элементов. К семейству интерфейса Set относятся HashSet, TreeSet и LinkedHashSet. В множествах Set разные реализации используют разный порядок хранения элементов. В HashSet порядок элементов на основе таблиц, оптимизирован для быстрого поиска. В контейнере TreeSet объекты хранятся на основе деревьев отсортированными по возрастанию. LinkedHashSet хранит элементы в порядке добавления в TreeSet? Только в первом элементе. Методы интерфейса Collection add(Object Добавление элемента в коллекцию, если он отсутствует. Возвращает true, если элемент добавлен Добавление элементов коллекции, если они отсутствуют. clear() Очистка коллекции Проверка присутствия элемента в наборе. Возвращает true, если элемент найден Проверка присутсвия коллекции в наборе. Возвращает true, если все элементы содержатся в наборе Проверка на равенство. hashCode() Получение hashCode набора. isEmpty() Проверка наличия элементов. Возвращает true если в коллекции нет ни одного элемента. iterator() Функция получения итератора коллекции Удаление элемента из набора Удаление из набора всех элементов переданной коллекции retainAll(Collection Удаление элементов, не принадлежащих переданной коллекции. size() Количество элементов коллекции toArray() Преобразование набора в массив элементов Преобразование набора в массив элементов. В отличии от предыдущего метода, который возвращает массив объектов типа 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 всегда равен Как обойти 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 Как работает метод get в Способ, которым определяется уникальность ключа в методе put(), имеет туже логику, которую применяет метод get(). Как только HashMap определяет ключ объекта, переданного в аргументе, он просто возвращает значение соответствующего объекта Node. Если же совпадений не найдено, метод get() вернет null. |