Коллекции Flashcards
Какие данные могут хранить коллекции
Коллекции могут хранить любые ссылочные типы данных
коллекция
Коллекции это классы, основная цель которых – хранить набор других элементов.
List
List — это упорядоченный список.
Объекты хранятся в порядке их добавления в список.
Доступ к элементам списка осуществляется по индексу.
Set
Set — множество уникальных объектов.
В коллекции этого типа разрешено наличие только одной ссылки типа null.
Queue
Queue — коллекция, предназначенная для хранения элементов в порядке, нужном для их обработки.
В дополнение к базовым операциям интерфейса Collection, очередь предоставляет дополнительные операции вставки, получения и контроля.
основные реализации List
ArrayList Список
LinkedList Список
Vector Вектор
Stack Стек
основные реализации Set
HashSet Множество
TreeSet Множество
SortedSet (расширяющий интерфейс Отсортированное
множество
основные реализации Map.
HashMap Карта/Словарь
TreeMap Карта/Словарь
SortedMap (расширяющий интерфейс) Отсортированный
словарь
Hashtable Хеш-таблица
реализации SortedSet
java.util.SortedSet<E> наследует java.util.Set<E>.</E></E>
Реализации: java.util.TreeSet<E></E>
java.util.SortedSet<E></E>
Реализации этого интерфейса, помимо того что следят за уникальностью хранимых объектов, поддерживают их в порядке возрастания. Отношение порядка между объектами может быть определено, как с помощью метода compareTo интерфейса java.lang.Comparable<T>, так и при помощи специального класса-компаратора, наследующего интерфейс java.util.Comparator<T>.</T></T>
java.util.TreeSet<E></E>
коллекция, которая хранит свои элементы в виде упорядоченного по значениям дерева. TreeSet инкапсулирует в себе TreeMap, который в свою очередь использует сбалансированное бинарное красно-черное дерево для хранения элементов. TreeSet хорош тем, что для операций add, remove и contains потребуется гарантированное время log(n).
В чем отличия/сходства List и Set?
Оба унаследованы от Collection, а значит имеют одинаковый набор и сигнатуры методов. List хранит объекты в порядке вставки, элемент можно получить по индексу. Set не может хранить одинаковых элементов.
Что разного/общего у классов ArrayList и LinkedList, когда лучше использовать ArrayList, а когда LinkedList?
ArrayList реализован внутри в виде обычного массива. Поэтому при вставке элемента в середину, приходится сначала сдвигать на один все элементы после него, а уже затем в освободившееся место вставлять новый элемент. Зато в нем быстро реализованы взятие и изменение элемента – операции get, set, так как в них мы просто обращаемся к соответствующему элементу массива.
LinkedList реализован внутри по-другому. Он реализован в виде связного списка: набора отдельных элементов, каждый из которых хранит ссылку на следующий и предыдущий элементы. Чтобы вставить элемент в середину такого списка, достаточно поменять ссылки его будущих соседей. А вот чтобы получить элемент с номером 130, нужно пройтись последовательно по всем объектам от 0 до 130. Другими словами операции set и get тут реализованы очень медленно.
Если необходимо вставлять (или удалять) в середину коллекции много элементов, то лучше использовать LinkedList. Во всех остальных случаях – ArrayList.
LinkedList требует больше памяти для хранения такого же количества элементов, потому что кроме самого элемента хранятся еще указатели на следующий и предыдущий элементы списка, тогда как в ArrayList элементы просто идут по порядку
В каких случаях разумно использовать массив, а не ArrayList?
Если коротко, то Oracle пишет — используйте ArrayList вместо массивов. Если ответить на этот вопрос нужно по-другому, то можно сказать следующее: массивы могут быть быстрее и кушать меньше памяти. Списки теряют в производительности из-за возможности автоматического увеличения размера и сопутствующих проверок. Плюс к этому, что размер списка увеличивается не на 1, а на большее кол-во элементов (+15)*. Так же доступ к [10] в массиве может быть быстрее чем вызов get(10) у списка.
*Читатель прислал комментарий «У ArrayList увеличение происходит в 1.5 раза. int newCapacity = oldCapacity + (oldCapacity»_space; 1);».
Чем отличается ArrayList от Vector?
Vector deprecated. У Vector некоторые методы синхронизированы и поэтому они медленные. В любом случае Vector не рекомендуется использовать вообще.
Что вы знаете о реализации классов HashSet и TreeSet?
Название Hash… происходит от понятия хэш-функция. Хэш-функция — это функция, сужающая множество значений объекта до некоторого подмножества целых чисел. Класс Object имеет метод hashCode(), который используется классом HashSet для эффективного размещения объектов, заносимых в коллекцию. В классах объектов, заносимых в HashSet, этот метод должен быть переопределен (override).
HashSet реализован на основе хеш-таблицы, а TreeSet — на основе бинарного дерева.
HashSet гораздо быстрее чем TreeSet (константное время против логарифмического для большинства операций, таких как add, remove, contains), но TreeSet гарантирует упорядоченность объектов. Оба не синхронизированы.
HashSet
предоставляет константное время для add(), remove(), contains() и size()
порядок элементов в контейнере может меняться
производительность итерации по контейнеру зависит от емкости и «коэффициента загрузки» (рекомендуется оставлять load factor значением по умолчанию равным 0.75, что является хорошим компромиссом между временем доступа и объемом хранимых данных)
TreeSet
время для базовых операций add(), remove(), contains() — log(n)
гарантирует порядок элементов
не предоставляет каких-либо параметров для настройки производительности
предоставляет дополнительные методы для упорядоченного списка: first(), last(), headSet(), tailSet() и т.д.
Чем отличаются HashMap и TreeMap? Как они устроены и работают? Что со временем доступа к объектам, какие зависимости?
В целом ответ про HashSet и TreeSet подходит и к этому вопросу.
HashMap работает строго быстрее TreeMap.
TreeMap реализован на красно-черном дереве, время добавления/поиска/удаления элемента — O(log N), где N — число элементов в TreeMap на данный момент.
У HashMap время доступа к отдельному элементу — O(1) при условии, что хэш-функция (Object.hashCode()) определена нормально (что является правдой в случае Integer).
Общая рекомендация — если не нужна упорядоченность, использовать HashMap. Исключение — ситуация с вещественными числами, которые в качестве ключей почти всегда очень плохи. Для них нужно использовать TreeMap, предварительно поставив ему компаратор, который сравнивает вещественные числа так, как это нужно в данной задаче. Например, для обычных геометрических задач два вещественных числа могут считаться равными, если отличаются не более, чем на 1e-9.
Что такое Hashtable, чем она отличается от HashMap? На сегодняшний день она deprecated, как все-таки использовать нужную функциональность?
Некоторые методы HashTable синхронизированы, поэтому она медленнее HashMap.
HashTable синхронизирована, а HashMap нет.
HashTable не позволяет иметь null ключи или значения. HashMap позволяет иметь один null ключ и сколько угодно null значений.
У HashMap есть подкласс LinkedHashMap, который добавляет возможности по итерации. Если вам нужна эта функциональность, то можно легко переключаться между классами.
Общее замечание — не рекомендуется использовать HashTable даже в многопоточных приложениях. Для этого есть ConcurrentHashMap.
Что будет, если в Map положить два значения с одинаковым ключом?
Последнее значение перезапишет предыдущее.
Как задается порядок следования объектов в коллекции, как отсортировать коллекцию?
Класс ТгееМар полностью реализует интерфейс SortedMap. Он реализован как бинарное дерево поиска, значит его элементы хранятся в упорядоченном виде. Это значительно ускоряет поиск нужного элемента. Порядок задается либо естественным следованием элементов, либо объектом, реализующим интерфейс сравнения Comparator.
В этом классе четыре конструктора:
ТгееМар() — создает пустой объект с естественным порядком элементов;
TreeМар(Comparator с) — создает пустой объект, в котором порядок задается объектом сравнения с;
ТгееМар(Map f) — создает объект, содержащий все элементы отображения f, с естественным порядком его элементов;
ТгееМар(SortedMap sf) — создает объект, содержащий все элементы отображения sf, в том же порядке.
Интерфейс Comparator описывает два метода сравнения:
int compare(Object obj1, object obj2) — возвращает отрицательное число, если obj1 в каком-то смысле меньше obj2; нуль, если они считаются равными; положительное число, если obj1 больше obj2. Для читателей, знакомых с теорией множеств, скажем, что этот метод сравнения обладает свойствами тождества, антисимметричности и транзитивности;
boolean equals(Object obj) — сравнивает данный объект с объектом obj, возвращая true, если объекты совпадают в каком-либо смысле, заданном этим методом.
Для каждой коллекции можно реализовать эти два метода, задав конкретный способ сравнения элементов, и определить объект класса SortedMap вторым конструктором. Элементы коллекции будут автоматически отсортированы в заданном порядке.
Дайте определение понятию “итератор”.
Итератор — объект, позволяющий перебирать элементы коллекции. Например foreach реализован с использованием итератора. Одним из ключевых методов интерфейса Collection является метод Iterator<E> iterator(). Он возвращает итератор — то есть объект, реализующий интерфейс Iterator.</E>
Какую функциональность представляет класс Collections
Некоторые из методов
Сигнатура метода Описание
Collections.sort(List myList) Сортирует список в естественном порядке.
Collections.sort(List, Comparator c) Сортировка с использованием компаратора.
Collections.shuffle(List myList) Перемешивает коллекцию в случайном порядке.
Collections.reverse(List myList) Переворачивает коллекцию в обратном порядке.
Collections.binarySearch(List mlist, T key) поиск в коллекции по ключу с использованием бинарного поиска.
Collections.copy(List dest, List src) Копирует коллекцию источник src в dest.
Collections.frequency(Collection c, Object o) Возвращает число вхождений объекта в коллекции.
Collections.synchronizedCollection(Collection c) Возвращает синхронизированную (потокобезопасную) коллекцию.
Как получить не модифицируемую коллекцию?
Коллекцию, доступную только для чтения можно получить с помощью методов:
public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s) {
return new UnmodifiableSortedSet<>(s);
}</T></T></T>
public static <T> List<T> unmodifiableList(List<? extends T> list) {
return (list instanceof RandomAccess ?
new UnmodifiableRandomAccessList<>(list) :
new UnmodifiableList<>(list));
}
и т.д. для каждого типа (Map, SortedMap и т.п.)</T></T>
Какие коллекции синхронизированы?
Для этого используется пакет Concurrent. А так @Deprecated HashTable, Vector.