Please enable JavaScript.
Coggle requires JavaScript to display documents.
public interface Collection<E> extends Iterable<E> {} …
public interface
Collection<E>
extends Iterable<E> {}
Это набор классов в которых реализован функционал по хранению объектов.
(Все коллекции параметризованные)
МЕТОДЫ
add(Object E) : boolean
(Вставить элемент в коллекцию, в порядке очереди)
add(int intdex, Object E) : void
(Вставка элемента в коллекцию по индексу)
get(int index) : E
(Получение элемента по индексу) - скорость
О(1)
set(int index, Object E) : E
(Заменяет элемент в списке по индексу)
remove(int index) : E
(Удалить элемент по индексу)
remove(Object E) : boolean
(Удалить этот элемент из коллекции)
addAll(ArrayLIst al) : boolean
(Добавить коллекцию в текущую коллекцию.
Операция объединения коллекций
)
addAll(int index, ArrayList al) : boolean
(Добавить коллекция в текущую коллекцию начиная с определенной позиции)
retainAll(ArrayLIst al) : boolean
.
(Удаляет элементы из коллекции, если этих элементов нет в параметрах метода.
Операция пересечения множеств
)
removeAll(ArrayLIst al) : boolean
(Удалить все элементы из коллекции.
Операция разности множеств
)
containsAll(ArrayLIst al) : boolean
(Узнать содержит ли ArrayList все элементы листа из параметра)
clear() : void
(Очистить коллекцию)
indexOf(Object E) : int
Возвращает позицию объекта(первое нахождение) или -1 если объект не найден
lastIndexOf(Object E) : int
Возвращает позицию объекта(последнее нахождение) или -1 если объект не найден
size() : int
(Размер коллекции)
isEmpty() : boolean
(Проверка, является ли коллекция пустой)
contains(Object) : boolean
(Узнать, есть ли такой объект в коллекции)
toString() : String
equals(Object) : boolean
Arrays.asList(DataType []) : List<DataType>
(Преобразовать массив в коллекцию)
toArray() : Object[]
(Преобразовать коллекцию в массив. Желательно указывать тип в аргументе
String[] array = list.toArray(new String[5]);)
subList(int fromIndex, int toIndex) : Lisе<E>
(создает из имеющегося листа другой лист на основании начального и конечного индексов)
List.of(E... elements) : List<E>
(Создает неизменяемую коллекцию)
List.copyOf(Collection <E> c) : List<E>
(Создаёт неизменяемую коллекцию. Эти листы не могут содержать null)
forEach(Consumer<? super T>) : void
(Позволяет итерироваться по каждому элементу коллекции)
iterator() : Iterator<E>
parallelStream() : Stream<E>
removeIf(Predicate<? super E>) : boolean
stream() : Stream<E>
public interface
List
<E> extends Collection<E> {}
List
упорядоченная коллекция элементов, позволяющих хранить дубликаты и null. Каждый элемент имеет индекс.
Лучше всегда ссылать коллекции именно на интерфейс, а не на класс коллекции, которую мы создаем. Там код будет более гибким.
Позже мы сможем менять на ходу
ArrayList
на
LinkedList
для наших нужд.
public class
ArrayList<E>
extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final long
serialVersionUID
= 868345281122892189L;
private static final int
DEFAULT_CAPACITY
= 10; // размер массива по умолчанию
private static final Object[]
EMPTY_ELEMENTDATA
= {};
private static final Object[]
DEFAULTCAPACITY_EMPTY_ELEMENTDATA
= {};
transient Object[] elementData;
private int size;
}
Это "массив", который может изменять свой размер.
В основе ArrayList лежит массив Object.
Cтандартная начальная ёмкость (default capacity) ArrayList составляет 10 элементов. Однако эту начальную ёмкость можно изменить при создании объекта, передав в конструктор коллекции желаемое число элементов. Если в процессе использования массив заполняется более чем на
load factor
(по умолчанию 75%) ёмкость ArrayList будет автоматически увеличена по мере необходимости.
ArrayList создаст новый массив большего размера. Обычно размер нового массива будет в два раза больше старого, но это может быть настроено путем передачи других значений в конструктор.
Быстрая и удобная коллекция для работы с простыми списками.
Методы add и get работают за константное время.
Поиск и удаление по индексу очень быстрый О(1) - константное время, но, чтобы вставить или удалить элемент в середине списка мы затратим время О(n). Так как после удаление элемента, все элементы, которые находятся справа от него переносятся на один элемент влево. ArrayList тут по памяти проигрывает.
Ещё раз:
Если нужно производить много удалений и добавлений элементов не из конца, а из середины или начала, то лучше использовать не ArrayList, а LinkedList.
RandomAcces говорит о том, что наш ArrayList имеет доступ по индексу и мы можем за константное время(О(1)) получить любой объект
Serializable
говорит о том, что мы можем сериализовать объект
Cloneable
позволяет клонировать наш лист
public class
LinkedList<E>
extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable {
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
}
Это связный список у которого есть два указателя - first и last это ссылки на класс Node(ссылки на первый и последний элемент в списке)
Если хотим найти элемент по значению, то здесь, так же, как и в ArrayLIst скорость поиска O(n), то есть будем перебирать каждый элемент коллекции.
Поиск по индексу О(n), потому что мы не можем перейти сразу же в нужный нам индекс, а мы должны итерироваться начиная от первого и до искомого элемента.
Если мы хотим добавить или удалить элемент в середине, то скорость будет О(n), так как перед тем как найти то место куда мы будем вставлять элемент мы будем итерироваться до него по каждому элементу по очереди. А затем вставим элемент со сложностью по памяти О(1).
LinkedList более предпочтителен для вставок или удаления в начало или середину.
public interface
Deque<E>
extends Queue<E> {}
Queue это интерфейс очередей
FIFI и LIFO
public class
ArrayDeque
add() - выбрасывает exeption, а offer() нет
addFirst()
addLast()
offerFirst()
offerLast()
removeFirst()
removeLast()
pollFirst()
pollLast()
getFirst()
getLast()
peekFIrst()
peekLast()
Vector
Ставит блокировку второму пользователю. Методы работаю медленнее, однопоточный.
firstElement()
lastElement()
Stack
Устаревший synchronized class. Использует принцип LIFO. Не рекомендован для использования.
push()
(Добавляет элемент)
pop()
(Возвращает элемент, который находится на самом верху стека и удаляет его)
pick()
(Возвращает элемент, который находится на самом верху стека, но не удаляет его)
isEmpty() : boolean
(Проверяет не пустой ли стек)
public interface
Set
<E> extends Collection<E> {
Так же, как и List, хранит в себе только одно значение, только в Set нельзя хранить одинаковые значения. Если добавляется объект с со значением, которое уже есть в списке, то новый объект перезаписывает старый
Можно выводить на экран через sout
HashSet
HashSet это урезанная версия HashMap. У элементов данного HashMap: ключи - это элементы HashSet, значения - это константа заглушка. Благодаря этому производительность очень хорошая. Может содержать null.
Класс HashSet не гарантирует никакого порядка объектов в коллекции.
TreeSet
first()
(Сортирует по возрастанию)
last()
(Сортирует по убыванию)
headSet(arg)
(Выводит элементы ниже чем аргумент)
tailSet(arg)
(Выводит элементы выше чем аргумент)
subSet(arg,arg)
(Позволяет получить множества, элементы которого находятся между двумя аргументами)
Хранит элементы в отсортированном по возрастанию порядке, хранит уникальные элементы.
В основе TreeSet лежит TreeMap. У элементов данного TreeMap: ключи - это элементы TreeSet, значение - это константа-заглушка. Не может содержать null.
Для вывода на экран нужно имплементировать Comparator.
Методы очень быстры.
LinkedHashSet
Класс LinkedHashMap сохраняет порядок добавления элементов
В основе LinkedHashSet лежит HashSet. У элементов данного HashMap: ключи - это элементы LinkedHashSet, значения - это заглушка-константа.
Производительность методов немного ниже, чем у методов HashSet.
public interface
SortedDet
public interface
NavigableSet
public interface Queue
offer()
В отличии от метода
add()
, при добавлении элемента в коллекцию, в которой уже нет места, не будет исключения. Этот метод не даст добавить.
remove()
Удаляет не из конца, а из начала.
Метод FIFO
Если элементов больше нет, то будет ИСКЛЮЧЕНИЕ.
poll()
То же самое, что и remove(), только будет не исключением, а возвращение null.
element()
Показывает первый элемент в очереди. Если элемента больше нет, то будет ИСКЛЮЧЕНИЕ.
peek()
То же самое, что и element(), только будет не исключение, а возвращение null.
public interface
AbstractQueue
public class
PriorityQueue
Это специальный вид очереди, в которой используется натуральная сортировка или та, которую мы описываем с помощью Comparable или Comparator. Таким образом используется тот элемент из очереди, приоритет которого выше.
public interface
Map<K,V>
{
int size();
boolean isEmpty();
put(K,V);
Уникальность ключа - главное требование для Map.
Если добавляется новый объект с уже существующим ключом, то он перезаписывает старый объект. Ключ может быть null.
Значения элементов могут повторяться. Значения могут быть null.
HashMap
Класс HashMap не гарантирует никакого порядка объектов в коллекции.
Его методы работают очень быстро. Скорость близка к O(1).
В основе HashMap лежит массив. Элементами этого массива являются структуры LinkedList. Данные структуры LinkedList и заполняются элементами, которые мы добавляем в HashMap. При достижении определенного порога LinkedList превращается в красно-черное дерево.
Рекомендуется, чтобы ключ в HashMap был immutable.
Так же, как и в List, при создании HashMap мы можем задать два параметра, которые очень влияют на производительность:
-Initial capacity - начальный размер массива,
-Load factor - коэффицент того, насколько массив должен быть заполнен, после чего его размер будет увеличен вдвое.
МЕТОДЫ
put()
(Устанавливаем значение. Если ключ занят, то значение перезаписывается)
get(int i)
(Получить значение по ключу)
remove()
(Удаление элемента)
keySet()
(Возвращает множество ключей)
values()
(Возвращает множество значений)
for(Person person : map.values() {
System.out.println(person.getFirstName()); }
entrySet()
(итерация по ключам и значениям)
for(Map.Entry<Integer, Person> entry : map.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue()); }
containsKey(Object key) : boolean
(Определяем есть ли в коллекции объект с таким ключом)
containsValue(Object value) : boolean
(Определяем есть ли в коллекции объект с таким значением)
containsKey
более приоритетнее, чем
containsValue
, так как выполняется со скоростью О(1)
size() : int
(Размер коллекции)
isEmpty() : boolean
(Проверка, является ли коллекция пустой)
putIfAbsent()
(Есть такое значение уже есть в коллекции, то мы его не кладем туда и не перезаписываем)
getOrDefault(K,V)
(Если в коллекции нет такого элемента, но мы пытаемся его вызвать, то вернется указанное дефолтное значение)
LinkedHashMap
Похоже на LinkedList, у которого есть два указателя - first и last это ссылки на класс Node(ссылки на первый и последний элемент в списке)
Класс LinkedHashMap сохраняет порядок добавления элементов или порядок их использования.
Производительность методов немного ниже, чем у методов HashMap.
Если в конструкторе после initialCapacity и loadFactor в значение "accesOrder поставить значение true, то порядок элементов будет меняться в зависимости от их использования."
TreeMap
descendingMap()
(Сортирует в обратном порядке)
tailMap(fromKey)
(Найти значения выше определенного в аргументе)
headMap(fromKey)
(Найти значения ниже определенного в аргументе)
lastEntry()
(возвращает значение, которое в самом конце)
firstEntry()
(возвращает значение, которое в самом начале)\
При работе с красно-черным деревом сложность поиска и вставки О(log n). "Это хорошо, но HashMap быстрее.
Сортирует добавленные пары<Ключ, Значение> по ключу
Значения могут быть не уникальными, в отличии, от ключей. Если ключ одинаковый, то значение перезаписывается на новое.
HashTable
Это устаревший класс, который работает по тем же принципам, что и HashMap, но является synchronized. По этой причине его методы далеко не такие быстрые.
Ни ключ ни значение не могут быть null.
Даже если нужна поддержка многопоточности HashTable лучше не использовать. Следует использовать ConcurrentHashMap.
public interface
Iterable<T>
{ Iterator<T> iterator(); }
Это шаблон проектирования, который представляет нам возможность итерироваться по всем элементам коллекций. Потому что коллекции бывают разные, их структуры тоже разные, следовательно и итерирование по этим коллекциям тоже разное.
boolean hasNext()
(Проверяет, есть ли в нашей коллекции элемент, к которому можно перейти)
E next()
(Возвращает элемент после вызова hasNext())
remove()
(Удаляет элемент)
Итератор это шаблон проектирования. Пример:
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()) {
System.out.println(iterator.next();;
или
for(Iterator<Integer> iterator = list.iterator(); iterator.hasNext();) {
System.out.println(iterator.next()); }
Удаление элемента:
for(Iterator<Integer> iterator = list.iterator(); iterator.hasNext();) {
Integer next = iterator.next();
if (next == 4) { iterator.remove }
}
public interface
ListIterator<E>
extends Iterator<E>
boolean hasPrevious()
(Проверяет, есть ли в коллекции следующий элемент, старт поиска с конца)
E previous()
(Возвращает элемент после вызова hasPrevious)
int previousIndex()
(Возвращает индекс предыдущего элемента списка. Если такого элемента нет, метод возвращает -1.)
listIterator()
(Метод для получения итератора списка)
BIG O
notation
О(1)
Самый эффективный
О(n)
сложность порядка n(Линейный алгоритм)
O(logn)
(Логарифмический)
public interface
Comparable<T>
{
public int compareTo(T o); }
Этот интерфейс позволяет нам сортировать только по какому то одному параметру, что ограничивает нас.
Пример сравнивания объектов по id: (может использоваться, когда нужна сортировка объектов)
Override
public int
compareTo
(Person o) {
if (id = o.id) {
return 0;
} else if (id > o.id) {
return 1;
} else return -1;
}}
либо же просто return id - o.id; (где мы получаем положительное число, отрицательное число, либо 0).
либо return Integer.compare(id, o.id); если мы боимся переполнения интов.
main {
Collections.sort(personList); }
public interface
Comparator<T>
{
int compare(T o1, T o2); }
Пример сравнения объектов по первому имени добавляя собственно созданный компаратор в метод
sort
public static class FirstNameComparator implements Comparator<Person> {
Override
public int
compare
(Person o1, Person o2) {
return o1.getFirstName().compareTo(o2.getFirstName()); } } }
main {
personList.sort(new FirstNameComparator());
либо:
Collections.sort(personList, new FirstNameComparator()); }
либо вообще без создания Компаратора со сложной сортировкой по нескольким полям:
personList.sort(Comparator.comparing(Person : : getFirstName).thenComparing(Person : : getLastName));