Коллекции Flashcards
- Что такое «коллекция»?
«Коллекция» - это структура данных, набор каких-либо объектов. Данными (объектами в наборе) могут быть числа, строки, объекты пользовательских классов и т.п.
коллекция — это сбор чего-то, контейнер для каких-то элементов.
MЫ ХОТИМ:
- add
- remove
- clear
- contains
- size
- iterator
- tyoArray
- isEmpty
- equals, hashcode
С ДВУМЯ КОЛЛЕКЦИЯМИ:
- addAll все из одной в другую
- containsAll содержит все из другой
- removeAll все из другой
- retainAll оставить только общие
Соответственно, для описание такого общего поведения для всех коллекций написали разработчики Java интерфейс java.util.Collection.
Массивы решают проблему с хранением нескольких значений в одном месте. Но накладывает ограничение: размер массива постоянен. Если, как в примере, мы сказали что размер = 2, значит он равен двум. И всё. Если мы хотим массив больше — нам нужно создать новый экземпляр.
Кроме того, поиск элемента — тоже сложная вещь для массива. Есть метод Arrays.binarySearch, но данный поиск работает только на сортированном массиве (для несортированного массива результат неопределён или попросту непредсказуем). То есть поиск нас будет обязывать каждый раз сортировать.
Удаление — тоже лишь очищает значение. Поэтому мы ещё и не знаем, сколько в массиве реально данных, знаем только сколько ячеек в массиве.
- Расскажите про иерархию коллекций
Collection:
- Set -> SortedSet
- List
- Queue
- Deque
Map -> SortedMap
https: //i0.wp.com/dumbitdude.com/wp-content/uploads/2017/06/hieararchy-for-java-collection-framework.jpg?resize=1000%2C631
https: //habr.com/ru/post/237043/
На вершине иерархии в Java Collection Framework располагаются 2 интерфейса: Collection и Map. Эти интерфейсы разделяют все коллекции, входящие во фреймворк на две части по типу хранения данных: простые последовательные наборы элементов и наборы пар «ключ — значение» соответственно.
Интерфейс Collection расширяют интерфейсы:
● List (список) представляет собой коллекцию, в которой допустимы
дублирующие значения. Элементы такой коллекции пронумерованы, начиная от нуля, к ним можно обратиться по индексу. Реализации:
-ArrayList - инкапсулирует в себе обычный массив, длина которого автоматически увеличивается при добавлении новых элементов.
-LinkedList (двунаправленный связный список) - состоит из узлов, каждый из которых содержит как собственно данные, так и две ссылки на следующий и предыдущий узел.
-Vector — реализация динамического массива объектов, методы которой синхронизированы.
-Stack — реализация стека LIFO (last-in-first-out).
● Set (сет) описывает неупорядоченную коллекцию, не содержащую повторяющихся элементов. Реализации:
-HashSet - использует HashMap для хранения данных. В качестве ключа и значения используется добавляемый элемент. Из-за особенностей реализации порядок элементов не гарантируется при добавлении.
-LinkedHashSet — гарантирует, что порядок элементов при обходе коллекции будет идентичен порядку добавления элементов.
-TreeSet — предоставляет возможность управлять порядком элементов в коллекции при помощи объекта Comparator, либо сохраняет элементы с использованием «natural ordering».
● Queue (очередь) предназначена для хранения элементов с предопределенным способом вставки и извлечения FIFO (first-in-first-out): -PriorityQueue — предоставляет возможность управлять порядком
элементов в коллекции при помощи объекта Comparator, либо сохраняет элементы с использованием «natural ordering».
-ArrayDeque — реализация интерфейса Deque, который расширяет интерфейс Queue методами, позволяющими реализовать конструкцию вида LIFO (last-in-first-out).
- Почему Map — это не Collection, в то время как List и Set являются Collection?
Collection представляет собой совокупность некоторых элементов. Map - это совокупность пар «ключ-значение».
- В чем разница между классами java.util.Collection и java.util.Collections?
Класс java.util.Collections содержит исключительно статические методы для работы с коллекциями. В них входят методы, реализующие полиморфные алгоритмы (такие алгоритмы, использование которых возможно с разными видами структур данных), “оболочки”, возвращающие новую коллекцию с инкапсулированной указанной структурой данных и некоторые другие методы.
java.util.Collection - это корневой интерфейс Java Collections Framework. Этот интерфейс в основном применяется там, где требуется высокий уровень абстракции, например, в классе java.util.Collections.
- Какая разница между итераторами с fail-fast и fail-safe поведением? (С
примерами)
Fail-fast итератор генерирует исключение ConcurrentModificationException, если коллекция меняется во время итерации, а fail-safe – нет.
В противоположность fail-fast, итераторы fail-safe не вызывают никаких исключений при изменении структуры, потому что они работают с клоном коллекции вместо оригинала.
Итератор коллекции CopyOnWriteArrayList и итератор представления keySet коллекции ConcurrentHashMap являются примерами итераторов fail-safe.
fail-fast Iterator
Итераторы в Java используются для итерации по объектам Collection. Fail-Fast итераторы немедленно вызывают ConcurrentModificationException, если есть структурная модификация коллекции. Структурная модификация означает добавление, удаление или обновление любого элемента из коллекции, когда поток выполняет итерацию по этой коллекции. Iterator в классах ArrayList, HashMap - это примеры fail-fast Iterator.
import java.util.ArrayList;
import java.util.Iterator;
public class FailFastIteratorExample {
public static void main(String[] args) {
// Создание ArrayList целых чисел
ArrayList list = new ArrayList();
// Добавление элементов в список
list. add(1452);
list. add(6854);
list. add(8741);
// Получение итератора из списка
Iterator it = list.iterator();
while (it.hasNext()) {
Integer integer = (Integer) it.next();
// Это вызовет исключение
// ConcurrentModificationException
list.add(8457);
}
}
}
Вывод:
Exception in thread “main” java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(Unknown Source)
at java.util.ArrayList$Itr.next(Unknown Source)
at pack1.MainClass.main(MainClass.java:32)
fail-safe Iterator
fail-safe итераторы не генерируют никаких исключений, если коллекция структурно изменена во время итерации по ней. Это связано с тем, что они работают с клоном коллекции, а не с исходной коллекцией, и поэтому их называют fail-safe итераторами. Итератор в классах CopyOnWriteArrayList, ConcurrentHashMap являются примерами fail-safe итератора.
import java.util.Iterator;
import java.util.concurrent.ConcurrentHashMap;
public class FailSafeIteratorExample {
public static void main(String[] args) {
// Создание ConcurrentHashMap
ConcurrentHashMap map =
new ConcurrentHashMap();
// Добавляем элементы на карту
map. put("ONE", 1);
map. put("TWO", 2);
map. put("THREE", 3);
// Получение итератора из карты
Iterator it = map.keySet().iterator();
while (it.hasNext()) {
String key = (String) it.next();
System.out.println(key+" : "+map.get(key));
// Это не будет отражено в Iterator
map.put("FOUR", 4);
}
}
}
Вывод:
TWO : 2
FOUR : 4
ONE : 1
THREE : 3
https://javarush.ru/groups/posts/399-skaz-o-dvukh-iteratorakh-strategii-konkurentnoy-modifikacii-v-java-
- Чем различаются Enumeration и Iterator?
Интерфейс Enumeration – определяет методы, с помощью которых вы можете перечислить (получить по одному) элементы в коллекции объектов.
Этот устаревший интерфейс был заменён Iterator
- с помощью Enumeration нельзя добавлять/удалять элементы;
- в Iterator исправлены имена методов для повышения читаемости кода (Enumeration.hasMoreElements() соответствует Iterator.hasNext(), Enumeration.nextElement() соответствует Iterator.next() и т.д);
- Enumeration присутствуют в устаревших классах, таких как Vector/Stack, тогда как Iterator есть во всех современных классах-коллекциях.
- Как между собой связаныIterable,Iteratorи «for-each»?
Классы, реализующие интерфейсIterable, могут применяться в конструкцииfor-each, которая используетIterator.
- Можно ли итерируясь по ArrayList удалить элемент? Какое вылетит
исключение?
Подвох в том, что итератор ArrayList, является fail-fast, то есть не поддерживает итерацию с параллельной модификацией. Следующий шаг итератора после удаления элемента выбросит ConcurrentModificationException.
Единственный способ удалить элемент из коллекции при обходе, не получив при этом ConcurrentModificationException или неопределенное поведение – удалить с помощью remove() того же инстанса итератора. Вариант ListIterator поможет, если в теле цикла требуется и работа с индексами.
Некоторые коллекции, такие как CopyOnWriteArrayList и ConcurrentHashMap адаптированные под многопоточную среду и имеют fail-safe итераторы.
- Как поведёт себя коллекция, если вызвать iterator.remove()
Если вызову iterator.remove() предшествовал вызов iterator.next(), то iterator.remove() удалит элемент коллекции, на который указывает итератор, в противном случае будет выброшено IllegalStateException().
- Чем Set отличается от List?
Первое различие состоит в том, что один и тот же элемент не может встречаться в наборе более одного раза. Это отличается от списка, где каждый элемент может встречаться более одного раза.
Второе отличие состоит в том, что элементы в Set не имеют гарантированного внутреннего порядка. Элементы в списке имеют внутренний порядок, и элементы могут быть повторены в этом порядке.
Источник: https://java-blog.ru/collections/interfeys-java-set
- Расскажите про интерфейс Set.
Set — интерфейс, описывающий такую структуру данных как множество, содержащее неупорядоченные уникальные (неповторяющиеся) элементы. У интерфейса есть стандартные реализации — TreeSet, HashSet и LinkedHashSet.
- Расскажите про реализации интерфейса Set
Set - набор/множество, не может содержать дубликаты.
HashSet - основан на HashMap.
LinkedHashSet - расширяет HashSet, позволяет получать элементы в порядке их добавления, но требует больше памяти.
TreeSet - основан на сбалансированном двоичном дереве, в результате элементы упорядочены по возрастанию hashCode()’ов. Можно управлять порядком при помощи компаратора.
- В чем отличия TreeSet и HashSet?
TreeSet обеспечивает упорядоченно хранение элементов в виде красно-черного дерева. Сложность выполнения основных операций в TreeSet lg N. HashSet использует для хранения элементов такой же подход, что и HashMap, за тем отличием, что в HashSet в качестве ключа выступает сам элемент, кроме того HashSet (как и HashMap) не поддерживает упорядоченное хранение элементов и обеспечивает временную сложность выполнения операций аналогично HashMap.
- Чем LinkedHashSet отличается от HashSet?
Основное различие в том, что LinkedHashSet сохраняет порядок вставки элементов, а HashSet - нет. При этом LinkedHashSet также как и HashSet использует хэш таблицу, в отличие от того же TreeSet.
- Что будет, если добавлять элементы в TreeSet по возрастанию?
в основе TreeSet лежит красно-черное дерево, которое умеет само себя балансировать. В итоге, TreeSet все равно в каком порядке вы добавляете в него элементы, преимущества этой структуры данных будут сохраняться.
- Как устроен HashSet, сложность основных операций.
HashSet основан на Map. Тк он наследует Set, то без дубликатов.
Ключи - это значения Set, значения = константы заглушки
В лучшем случае О(1)
В худшем случае О(N)
Коэффициент загрузки = Количество хранимых элементов в таблице / размер хэш-таблицы
при достижении 0,75 количество корзин удваивается.
- Как устроен LinkedHashSet, сложность основных операций.
Implements Set interface, extends HashSet classs
Not Synchronized
Initial capacity 16, loadfactor 0,75
LinkedHashSet — подобная HashSet, в которой элементы объединены между собой в порядковый список. В этом случае элементы хранятся в том же порядке, в котором и добавляются (благодаря содержанию в себе объекта LinkedHashMap). И итерируются в том же порядке
Временная сложность основного метода O (1). Если нет коллизий как HashMap
- Как устроен TreeSet, сложность основных операций.
TreeSet является одной из наиболее важных реализаций интерфейса SortedSet в Java, который использует дерево для хранения. Порядок элементов поддерживается набором с использованием их естественного порядка, независимо от того, предоставляется ли явный компаратор.
Коллекция, которая хранит свои элементы в виде упорядоченного по значениям дерева. TreeSet инкапсулирует в себе TreeMap, который в свою очередь использует сбалансированное бинарное красно-черное дерево для хранения элементов. TreeSet хорош тем, что для операций add, remove и contains потребуется гарантированное время log(n).
- TreeSet реализует интерфейс SortedSet, поэтому повторяющиеся значения не допускаются.
- Объекты в TreeSet хранятся в отсортированном и возрастающем порядке.
TreeSet не сохраняет порядок вставки элементов, но элементы сортируются по ключам. - TreeSet не позволяет вставлять гетерогенные объекты. Он выдаст исключение classCastException во время выполнения, если попытается добавить гетерогенные объекты.
- TreeSet служит отличным выбором для хранения больших объемов отсортированной информации, к которой предполагается быстрый доступ из-за более быстрого доступа и времени поиска.
- TreeSet — это, по сути, реализация самобалансирующегося бинарного дерева поиска, такого как Red-Black Tree . Поэтому такие операции, как добавление, удаление и поиск, занимают O (Log n) время А такие операции, как печать n элементов в отсортированном порядке, занимают O (n) времени.
- Расскажите про интерфейс List
Интерфейс List , описывает методы работы с упорядоченными коллекциями. Иногда их называют последовательностями (sequence ). Элементы такой коллекции пронумерованы, начиная от нуля, к ним можно обратиться по индексу. В отличие от коллекции Set элементы коллекции List могут повторяться.
- Как устроен ArrayList, сложность основных операций.
ArrayList это список, реализованный на основе динамического массива.
● доступ к произвольному элементу по индексу за константное время O(1);
● доступ к элементам по значению за линейное время O(N);
● вставка в конец в среднем производится за константное время O(1);
● удаление произвольного элемента из списка занимает значительное время
т.к. при этом все элементы находящиеся «правее» смещаются на одну
ячейку влево (реальный размер массива (capacity) не изменяется);
● вставка элемента в произвольное место списка занимает значительное
время т.к. при этом все элементы находящиеся «правее» смещаются на
одну ячейку вправо;
● минимум накладных расходов при хранении.
Weakly consistent iterator
Коллекции weakly consistent iterators:, которые полагаются на CAS( compare-and-swap), имеют слабо согласованные итераторы, которые отражают некоторые, но не обязательно все изменения, внесенные в их резервную коллекцию с момента их создания. Например, если элементы в коллекции были изменены или удалены до того, как итератор достигнет их, он определенно отразит эти изменения, но для вставок такая гарантия не предоставляется.
ConcurrentHashMap
Назовите преимущества использования коллекций
Массивы обладают значительными недостатками. Одним из них является конечный размер массива, как следствие, необходимость следить за размером массива. Другим — индексная адресация, что не всегда удобно, т.к. ограничивает возможности добавления и удаления объектов.Чтобы избавиться от этих недостатков уже несколько десятилетий программисты используютрекурсивные типы данных, такие какспискиидеревья. Стандартный набор коллекций Java служит для избавления программиста от необходимости самостоятельно реализовывать эти типы данных и снабжает его дополнительными возможностями.
Кто кого расширяет: Queue расширяет Deque, или Deque расширяет Queue?
Queue - это очередь, которая обычно (но необязательно) строится по принципу FIFO (First-In-First-Out) - соответственно извлечение элемента осуществляется с начала очереди, вставка элемента - в конец очереди. Хотя этот принцип нарушает, к примеру, PriorityQueue, использующая «natural ordering» или переданный Comparator при вставке нового элемента.
Deque (Double Ended Queue) расширяет Queue и согласно документации, это линейная коллекция, поддерживающая вставку/извлечение элементов с обоих концов. Помимо этого, реализации интерфейса Deque могут строится по принципу FIFO, либо LIFO.
Реализации и Deque, и Queue обычно не переопределяют методы equals() и hashCode(), вместо этого используются унаследованные методы класса Object, основанные на сравнении ссылок.
Оцените количество памяти на хранение одного примитива типаbyteвLinkedList?
Каждый элементLinkedListхранит ссылку на предыдущий элемент, следующий элемент и ссылку на данные.
private static class Node { E item; Node next; Node prev; //… }
Для 32-битных систем каждая ссылка занимает 32 бита (4 байта). Сам объект (заголовок) вложенного классаNodeзанимает 8 байт. 4 + 4 + 4 + 8 = 20 байт, а т.к. размер каждого объекта в Java кратен 8, соответственно получаем 24 байта. Примитив типаbyteзанимает 1 байт памяти, но в JCF примитивы упаковываются: объект типаByteзанимает в памяти 16 байт (8 байт на заголовок объекта, 1 байт на поле типаbyteи 7 байт для кратности 8). Также напомню, что значения от -128 до 127 кэшируются и для них новые объекты каждый раз не создаются. Таким образом, в x32 JVM 24 байта тратятся на хранение одного элемента в списке и 16 байт - на хранение упакованного объекта типаByte. Итого 40 байт.
Для 64-битной JVM каждая ссылка занимает 64 бита (8 байт), размер заголовка каждого объекта составляет 16 байт (два машинных слова). Вычисления аналогичны: 8 + 8 + 8 + 16 = 40байт и 24 байта. Итого 64 байта
