Java Collections Framework - это набор связанных классов и интерфейсов, реализующих часто используемых коллекций структур данных
======================== класс ArrayList ========================
| add() | add(index,element) | get() | remove() | indexOf() | contains() |
| O(1) | O(n) | O(1) | O(n) | O(n) | O(n) |
- реализован в виде динамического массива
- иерархия: Iterable -> Collection -> List -> AbstractList -> ArrayList
- расширяет AbstractList
- реализует List , RandomAccess , Cloneable , Serializable
- потоко-небезопасен
- для работы в многопоточном режиме стоит использовать обертку: List list = Collections.synchronizedList(new ArrayList(...));
- Операции size , isEmpty , get , set , iterator и listIterator выполняются за постоянное время
- выдает исключение ConcurrentModificationException, если происходит попытка изменения структуры через итератор после создания списка
- может содержать null-элементы
======================== класс LinkedList ========================
| add() | add(index,element) | get() | remove() | contains() |
| O(1) | O(n) | O(n) | O(n) | O(n) |
- реализован в виде двусвязанного списка
- иерархия: Iterable -> Collection -> List -> AbstractSequentialList -> LinkedList
- расширяет AbstractSequentialList
- реализует List, Deque, Cloneable , Serializable
- потоко-небезопасен
- для работы в многопоточном режиме стоит использовать обертку: List list = Collections.synchronizedList(new LinkedList(...));
- выдает исключение ConcurrentModificationException, если происходит попытка изменения структуры через итератор после создания списка
- может содержать null-элементы
======================== класс HashMap ========================
| put() | get() | remove() | ContainsKey() |
| O(1) | O(1) | O(1) | O(1) |
Примечание: В версии 7 и ниже, временная сложность в худшем случае состовляет O(n), но начиная с версии 8 временная сложность будет составлять O(log N)
Примечание: Экземпляр HashMap имеет два параметра, влияющих на его производительность:
начальную емкость и коэффициент загрузки.
Емкость — это количество сегментов в хэш-таблице, а начальная емкость — это просто емкость на момент создания хэш-таблицы.
Коэффициент загрузки (по умолчанию 0,75) — это мера того, насколько полной может быть заполнена хеш-таблица, прежде чем ее емкость будет автоматически увеличена.
Когда количество записей в хеш-таблице превышает произведение коэффициента загрузки и текущей емкости, хеш-таблица повторно хешируется (то есть внутренние структуры данных перестраиваются), так что хеш-таблица имеет примерно удвоенное количество сегментов.
- реализован в виде хеш-таблицы, в ячейках которого хранится только связанный список (версия 7 и ниже)
- для версии 8 в ячейках хранится связанный список, который преобразуется в красно-черное дерево, если количество элементов в связанном списке становится равна 8, а общее количество корзин превышает 64
- иерархия: Map -> AbstractMap -> HashMap
- расширяет AbstractMap
- реализует Map, Cloneable , Serializable
- потоко-небезопасен
- для работы в многопоточном режиме стоит использовать обертку: Map map = Collections.synchronizedMap(new HashMap(...));
- выдает исключение ConcurrentModificationException, если, после создания iterator, происходит попытка изменения структуры любым способом, кроме как с помощью собственного метода remove.
- может содаржать только уникальные ключи
- может содержать только один null-ключ и несколько null-значений
- не гарантирует порядок
======================== класс LinkedHashMap ========================
| put() | get() | remove() | ContainsKey() |
| O(1) | O(1) | O(1) | O(1) |
Примечание: В версии 7 и ниже, временная сложность в худшем случае состовляет O(n), но начиная с версии 8 временная сложность будет составлять O(log N)
Примечание: итерация по LinkedHashMap требует времени, пропорционального размеру карты, независимо от ее емкости.
Примечание: Экземпляр LinkedHashMap имеет два параметра, влияющих на ее производительность: начальную емкость и коэффициент загрузки. Они определены точно так же, как и для HashMap
- реализован в виде хеш-таблицы и двусвязанного списка с предсказуемым порядком итераций
- для версии 8 в ячейках хранится связанный список, который преобразуется в красно-черное дерево, если количество элементов в связанном списке становится равна 8, а общее количество корзин превышает 64
- иерархия: Map -> AbstractMap -> HashMap -> LinkedHashMap
- расширяет HashMap
- реализует Map
- потоко-небезопасен
- для работы в многопоточном режиме стоит использовать обертку: Map map = Collections.synchronizedMap(new LinkedHashMap(...));
- выдает исключение ConcurrentModificationException, если, после создания iterator, происходит попытка изменения структуры любым способом, кроме как с помощью собственного метода remove.
- может содаржать только уникальные ключи
- может содержать только один null-ключ и несколько null-значений
- сохраняет порядок вставки
- порядок вставки не изменяется, если ключ повторно вставляется в карту
======================== класс TreeMap ========================
| put() | get() | remove() | ContainsKey() |
| O(log n) | O(log n) | O(log n) | O(log n) |
- реализован в виде красно-черного дерева
- иерархия: Map -> AbstractMap -> NavigableMap -> TreeMap
- расширяет AbstractMap
- реализует NavigableMap, Cloneable, Serializable
- потоко-небезопасен
- для работы в многопоточном режиме стоит использовать обертку: SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
- выдает исключение ConcurrentModificationException, если, после создания iterator, происходит попытка изменения структуры любым способом, кроме как с помощью собственного метода remove.
- может содержать только уникальные ключи
- может содержать только один null-ключ (если используется компаратор, разрешающий null) и несколько null-значений
- сортирует элементы в естественном порядке или исходя из заданного компаратора
- Корень должен быть окрашен в черный цвет.
- Листья дерева должны быть черного цвета.
- Красный узел должен иметь два черных, дочерних узла.
- Черный узел может иметь любые дочерние узлы.
- Путь от узла к его листьям должен содержать одинаковое количество черных узлов.
- Новые узлы добавляются на места листьев.
======================== класс HashSet ========================
| add() | remove() | contains() | size |
| O(1) | O(1) | O(1) | O(1) |
Примечание: Итерация по этому набору требует времени, пропорционального сумме размера экземпляра HashSet (количество элементов) плюс «емкость» резервного экземпляра HashMap(количество сегментов)
- реализован в виде хеш-таблицы (фактически экземпляром HashMap)
- иерархия: Iterable -> Collection -> Set -> AbstractSet -> HashSet
- расширяет AbstractSet
- реализует Set, Cloneable , Serializable
- потоко-небезопасен
- для работы в многопоточном режиме стоит использовать обертку: Set set = Collections.synchronizedSet(new HashSet(...));
- выдает исключение ConcurrentModificationException, если, после создания iterator, происходит попытка изменения структуры любым способом, кроме как с помощью собственного метода remove
- может хранить один null-элемент
- не гарантирует порядок
======================== класс LinkedHashSet ========================
| add() | remove() | contains() | size |
| O(1) | O(1) | O(1) | O(1) |
Примечание: Итерация по LinkedHashSet требует времени, пропорционального размеру набора, независимо от его емкости
Примечание: LinkedHashSet имеет два параметра, влияющих на его производительность: начальную емкость и коэффициент загрузки. Они определены точно так же, как и для HashSet
- реализован в виде хеш-таблицы и двусвязанного списка (фактически экземпляром HashMap)
- двусвязанный список проходит через все его записи
- иерархия: Iterable -> Collection -> Set -> AbstractSet -> HashSet -> LinkedHashSet
- расширяет HashSet
- реализует Set, Cloneable , Serializable
- потоко-небезопасен
- для работы в многопоточном режиме стоит использовать обертку: Set set = Collections.synchronizedSet(new LinkedHashSet(...));
- выдает исключение ConcurrentModificationException, если, после создания iterator, происходит попытка изменения структуры любым способом, кроме как с помощью собственного метода remove
- может хранить один null-элемент
- сохраняет порядок вставки
- порядок вставки не изменяется, если элемент повторно вставляется в набор
======================== класс TreeSet ========================
| add() | remove() | contains() | size |
| log(n) | log(n) | log(n) | O(1) |
Примечание: Порядок, поддерживаемый Set (независимо от того, предоставлен явный компаратор или нет), должен быть согласован с equals(), который реализуется классом TreeSet. Это связанно с тем, что класс TreeSet выполняет все сравнения элементов, используя свой метод compareTo() или compare()
- реализован в виде красно-черного дерева (на базе TreeMap)
- иерархия: Iterable -> Collection -> Set -> AbstractSet -> HashSet -> LinkedHashSet
- расширяет AbstractSet
- реализует NavigableSet, Cloneable , Serializable
- потоко-небезопасен
- для работы в многопоточном режиме стоит использовать обертку: SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));
- выдает исключение ConcurrentModificationException, если, после создания iterator, происходит попытка изменения структуры любым способом, кроме как с помощью собственного метода remove.
- может содержать только один null-элемент (если используется компаратор, разрешающий null)
- сортирует элементы в естественном порядке или исходя из заданного компаратора