Ревью: Generics. Collections. Методы интерфейса Collection? https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html http://www.smachek.com/post/java_collections/ https://jsehelper.blogspot.com/2016/01/java-collections-framework-1.html Что такое Generic? Преимущества - Обобщения - это параметризованные типы. С их помощью можно объявлять классы, интерфейсы и методы, где тип данных указан в виде параметра. Обобщения добавили в язык безопасность типов https://youtu.be/mNyQYTp-Njw http://phantompainray.blogspot.com/2014/02/generic.html Что можно поставить в дженерики, что нельзя? Что можно типизировать? Что нельзя параметризировать? Можно типизировать только ссылочные типы. Нельзя типизировать примитивные типы.Невозможно объявить статические поля, типы которых являются параметрами типа. Невозможно использовать приведение или instanceof с параметризованными типами. Что такое WildCard и всё что с ними связано? https://habr.com/ru/company/sberbank/blog/416413/ Что такое PECS ? https://stackoverflow.com/questions/2723397/what-is-pecs-producer-extends-consumer-super Статические методы как они типизируются Collection? Как параметризовать статический метод? http://www.quizful.net/post/java-generics-tutorial Отличие коллекции от массива? Массивы - это простые конструкции фиксированного размера, и поэтому они могут хранить только заданное количество элементов. Массивы встроены в ядро языка Java, и используемый при работе с ними синтаксис Java очень прост и понятен. Например, чтобы получить элемент массива с номером n, вам нужно вызвать функцию array[n]. Коллекции - это более сложный, но в то же время более гибкий тип данных. Прежде всего, размер коллекции можно изменять: вы можете добавлять в коллекцию любое количество элементов. Коллекции автоматически обрабатывают удаление элемента из любой позиции. https://www.youtube.com/watch?v=-S_huEuNJiU Можно ли с помощью цикла for each изменить поле объектов, которые находятся в массиве? И можно ли изменить сам объект? Элемент из КОЛЛЕКЦИИ в цикле for-each удалить нельзя, т.к. нельзя проводить одновременно итерацию (перебор) коллекции и изменение ее элементов. Итератор этого учесть не может. Значения элементов массива менять можно! Отличие ArrayList от LinkedList? Когда лучше использовать ArrayList, а когда LinkedList? ArrayList - это список на основе массива. LinkedList - связанный список на основе элементов и связи между ними. В качестве LinkedList лучше всего подходит представление вагонов поезда сцепленных последовательно. ArrayList следует использовать, когда в приоритете доступ по индексу, так как эти операции выполняются за константное время. Добавление в конец списка в среднем тоже выполняется за константное время. Кроме того в ArrayList нет дополнительных расходов на хранение связки между элементами. Минусы в скорости вставки/удаления элементов находящихся не в конце списка, так как при этой операции все элементы правее добавляемого/удаляемого сдвигаются. LinkedList удобен когда важнее быстродействие операций вставки/удаления, которые в LinkedList выполняются за константное время. Операции доступа по индексу производятся перебором с начала или конца (смотря что ближе) до нужного элемента. Дополнительные затраты на хранение связки между элементами. Одним словом - если часто вставляете/удаляете - выбирайте в пользу LinkedList, в противном случае ArrayList В чём разница между Queue и Deque и Stack? Queue (одностороняя очередь) - когда элементы можно получить в том порядке в котором добавляли. FIFO Dequeue (двусторонняя очередь) - можно вставлять/получать элементы из начали и конца. Расскажи отличие List от Set? 3 реализации Set -> Упорядоченность в HashSet, LinkedHashSet, TreeSet (Какая упорядоченность в какой и почему)? List хранит объекты в порядке вставки, элемент можно получить по индексу. Set не может хранить одинаковых элементов. К семейству интерфейса Set относятся HashSet, TreeSet и LinkedHashSet. В множествах Set разные реализации используют разный порядок хранения элементов. В HashSet порядок элементов оптимизирован для быстрого поиска. В контейнере TreeSet объекты хранятся отсортированными по возрастанию. LinkedHashSet хранит элементы в порядке добавления. 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, данный метод возвращает массив объектов типа, переданного в параметре. Как работает 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() не мог бы быть выполнен. Как работает HashMap? Расскажите подробно, как работает метод put? Что происходит при коллизии? Как работает метод get в HashMap? Метод put в HashMap? Почему Map не входит в Collection? Может ли null быть ключём в HashMap? Как расширяется HashMap? Как обойти HashMap через for-each? http://opensourceforgeeks.blogspot.com/2015/02/understanding-how-hashmap-and-hashset.html https://javarush.ru/groups/posts/2496-podrobnihy-razbor-klassa-hashmap https://www.youtube.com/watch?v=kk_9md24Ttk Что такое бинарное дерево? Условия перестраивания HashMap в красно-чёрное дерево? https://youtu.be/HBMlhZAOhoI https://youtu.be/n7Y2karbxF4 https://www.cs.usfca.edu/galles/visualization/RedBlack.html Как работает метод contains в ArrayList, LinkedList, HashSet? В чём разница между Iterable и Iterator? listIterator - что это, в чём отличие от обычного? Что такое даймонд оператор? Что такое raw type? К чему приводит использование raw type? Стирание типов? Что такое стирание и сырые типы? - Основная цель diamoind оператора упростить использование универсальных шаблонов при создании объекта . Это позволяет избежать непроверенных предупреждений в программе и делает программу более читаемой. Raw Types (сырые типы) – Это имя универсального класса или интерфейса без каких-либо аргументов типа. их нужно избегать. Пример сырого типа List <> list = new ArrayList<>; Пример нормального типа List list = new ArrayList<>; Они нужны только для поддержки обратной совместимости кода, «сырые типы» являются не «типобезопасными». Если вы не указали тип, например, своей коллекции, то туда можно запихнуть другой объект любого типа Стирание типов - во время компиляции компилятор имеет полную информацию о типе, но эта информация обычно намеренно отбрасывается при создании байтового кода в процессе, известном как стирание типов . Это делается таким образом из-за проблем совместимости: целью разработчиков языка было обеспечение полной совместимости исходного кода и полной совместимости байтового кода между версиями платформы. Если бы он был реализован по-другому, вам пришлось бы перекомпилировать устаревшие приложения при переходе на более новые версии платформы. Параметр vs Аргумент. (в дженериках)? Параметр – это тип данных, которыми оперируют классы, интерфейсы указанные в дженериках Null в TreeSet? Что было до дженериков? Если поле типизировано дженериком как в байт коде будет представлен этот тип? Зачем в итераторе метод remove? Какой механизм обеспечивает обратную совместимость сырых типов и дженериков? Какие структуры данных вы знаете? Расскажи про иерархию коллекций? Почему последняя строчка не скомпилируется? List arrayLists = new ArrayList(); ArrayList arrayList = new ArrayList(); ? Скорость ставки элемента в начало середину и конец у ArrayList vs LinkedList? На чём основаны основные реализации коллекций. Например, ArrayList построен на Object[ ]? В чем отличие в записях в параметре метода: (Collection collection) и ((Collection collection)? 1. Как работает методcontains вArrayList, LinkedList, HashSet? public boolean contains(Object o) { return indexOf(o) >= 0; } Метод contains в Arraylist использует метод indexOf (), который использует в свою очередь метод indexOfRange (). Там совершается обход элементов в цикле и если элемент не null, то вызывается стандартный метод equals (сравнение ссылок). Тоже самое для LinkedList. В методе contains HashSet используются «корзины» и поиск объекта происходит сначала по hashcode, а только потом по equals. В реализации: Метод contains вызывает (косвенно) getEntry из HashMap, где ключ - это Object, для которого вы хотите узнать, находится ли он в HashSet. Как вы можете видеть ниже, два объекта могут быть сохранены в HashMap/HashSet, даже если их ключ сопоставляется с тем же значением с помощью хэш-функции. Метод выполняет итерацию по всем ключам, которые имеют одно и то же значение хэша, и выполняет equals на каждом из них, чтобы найти соответствующий ключ. final Entry getEntry(Object key) { int hash = (key == null) ? 0 : hash(key.hashCode()); for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; } 2. Как работает HashMap? Расскажите подробно, как работает метод put? Что происходит при коллизии? Внутри Hashmap имеет вложенный класс Node в котором хранятся пары ключ значения: static class Node implements Map.Entry { final int hash; final K key; V value; Node next; Node(int hash, K key, V value, Node next) { 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[] table; Это и есть массив bucket. Если возникает коллизия (т.е. hashcode вычисленный) объектов равны, то создается связанный список node в каждой ячейке массива node, где объекты ссылаются друг на друга Как работает HashMap. HashMap состоит из «корзин» (bucket`ов). «Корзины» — это элементы массива, которые хранят ссылки на списки элементов. При добавлении новой пары ключ-значение вычисляет хеш-код ключа, на основании которого вычисляется номер bucket’a(номер ячейки массива), в которую попадёт новый элемент. Если bucket пуст, то в него сохраняется ссылка на вновь добавляемый элемент, если же там уже есть элемент, то происходит последовательный переход по ссылкам между элементами в цепочке, в поисках последнего элемента, от которого и ставится ссылка на вновь добавленный элемент. Если в списке был найден элемент с таким же ключом, то он заменяется. Добавление, поиск и удаление элементов выполняется за константное время. Вроде все здорово, с одной оговоркой, хеш-функций должна равномерно распределять элементы по корзинам, в этом случае временная сложность для этих 3 операций будет не ниже lg N, а в среднем случае как раз константное время. метод 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) приводится в битовый эквивалент, над ними производится побитовое умножение. 2. Создается объект Node (включает хеш, ключ, значение, ссылка на следующий элемент, (либо null, если его нет)). 3. Теперь, зная индекс в массиве, мы получаем список (цепочку) элементов, привязанных к этой ячейке. Если в бакете пусто, тогда просто размещаем в нем элемент. Иначе хэш и ключ нового элемента поочередно сравниваются с хешами и ключами элементов из списка и, при совпадении этих параметров, значение элемента перезаписывается. Если совпадений не найдено, элемент добавляется в конец списка. |
Скачать 19.7 Kb.