Skip to content
Gallery
Theory for java developer
Share
Explore
Java

icon picker
Collections

Collections

Collection – для отдельных значений, Map – для пары ключ-значение. Отсюда разные методы этих интерфейсов. Если проще, разные сигнатуры методов put и add, добавления элемента.
image.png
image.png

Collection в свою очередь делится на три основных группы с интерфейсами:
List – упорядоченные списки с возможностью содержания дубликатов и доступа по индексу.
Queue – обычно FIFO-коллекции, предполагает добавление/удаление элементов с края. Интерфейс-наследник Deque – двунаправленная очередь.
Set – не обязательно упорядоченный набор уникальных (с точки зрения equals) значений;
HashMap можно привести к виду Collection вызвав например keySet(), entrySet() или values().
image.png
Свойства коллекций
image.png
Тип коллекций
image.png
Временная сложность
image.png
ArrayList - Является реализацией динамического массива объектов. В основе обычный массив.
По дефолту размер 10 при добавлении 11 элемента пересчитывается (дорогая операция) и становится 16 (на 50% больше). Расширяется путем копирования старого массива в новый большего объема.
Следует применять, если предполагается частое обращение к элементам по индексу.
Не надо применять, если требуется частое удаление/добавление элементов в середину коллекции.
Быстрый доступ к элементам по индексу за время O(1);
Доступ к элементам по значению за линейное время O(n);
Медленный, когда вставляются и удаляются элементы из «середины» списка;
LinkedList - Представляет связанный список в каждом элементе которого(кроме первого и последнего) хранится: ссылка на предыдущий элемент, значение, ссылка на следующий элемент.
У нас есть доступ к первому и последнему элементу в любой момент времени O(1).
Из LinkedList можно организовать стек, очередь, или двойную очередь, со временем доступа O(1);
На вставку и удаление из середины списка, получение элемента по индексу или значению потребуется линейное время O(n). Однако, на добавление и удаление из середины списка, используя потребуется O(1);
Использует много памяти.
По дефолту размер 16 - initial Capacity, 0.75 load Factor. Если не хватит 16, увеличится в 2 раза.
Условия увеличения (initial Capacity) * (load Factor) = 16 * 0.75 = 12. По достижению определенного количества бакетов или node в одном бакете – преобразуется в красно-черное дерево.
Ассоциативный массив(ключ - любой объект, значение - любой объект).
Структура данных для хранения связанных вместе пар “ключ-значение”.
Хэширует только ключи для быстрого поиска. Хэширование выполняется немного быстрее, чем вставка в дерево, поэтому данные отображение используется, когда не требуется отсортированный порядок ключей.
Нельзя сохранить 2 значения по одинаковым ключам, второе значение заменит первое
image.png
HashMap содержит в себе динамически расширяемый массив, элементы в котором называются
Bucket(Бочка). В каждой ячейка этого массива находится связный список наподобие LinkedList из элементов class Node.
image.png
Обычно один класс Node должен занимать одну ячейку и его поле next = null, но при обработки коллизии(когда несколько объектов распределяются в одну ячейку) мы сравниваем ключи если они разные тогда мы добавляем в ячейку еще один элемент, если одинаковые заменяем Node на новый.
Map<byte[](ссылка),String> ссылка ведет на разные области памяти в массиве. Мы можем не найти данные в мапе если изменили хэшкод у ранее записанного объекта.

Потокобезопасные коллекции

HashTable - методы обращения синхронизированы (медленно)
ConcurrentHashMap - синхронизирует только сегменты, не полностью, делая остальную часть доступной для многопоточности.
CopyOnWriteArrayList - по принципу fail-safe, каждый поток работает со своей копией листа(не возникает ConcurrentModificationException).
Comparator vs Comparable (Сортировка 1, -1, 0)
Comparator
Comparable
1
interface
Interface
2
Когда мы хотим менять характеристики для сравнения
Когда мы хотим сравнивать по главным характеристикам
3
compare(YourObject arg1, YourObject arg2)
compareTo(YourObject arg1)
4
public class PLevelComparator implements Comparator<P> {
@Override
public int compare(P p1, P p2) {
return Integer.compare(p1.getRanking(), p2.getRanking());
}
}
public class PAgeComparator implements Comparator<P> {
@Override
public int compare(P p1, P p2) {
return Integer.compare(p1.getAge(), p2.getAge());
}
}
public class P implements Comparable<P> {
@Override
public int compareTo(P op) {
return Integer.compare(getLevel(), op.getLevel());
}
}
5
PlayerRankingComparator playerComparator = new PlayerRankingComparator();
Collections.sort(footballTeam, playerComparator);
PlayerAgeComparator playerComparator = new PlayerAgeComparator();
Collections.sort(footballTeam, playerComparator);
P p1 = new P("Vlad", 4);
P p2 = new P("Lizard", 3);
return p1.compareTo(p2);
There are no rows in this table


Want to print your doc?
This is not the way.
Try clicking the ⋯ next to your doc name or using a keyboard shortcut (
CtrlP
) instead.