Skip to content

Latest commit

 

History

History
282 lines (268 loc) · 17.9 KB

README.md

File metadata and controls

282 lines (268 loc) · 17.9 KB

Java-Collections-Framework

Java Collections Framework - это набор связанных классов и интерфейсов, реализующих часто используемых коллекций структур данных


======================== класс ArrayList ========================

Временная сложность (Big-O):

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 ========================

Временная сложность (Big-O):

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 ========================

Временная сложность (Big-O):

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 ========================

Временная сложность (Big-O):

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 ========================

Временная сложность (Big-O):

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 ========================

Временная сложность (Big-O):

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 ========================

Временная сложность (Big-O):

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 ========================

Временная сложность (Big-O):

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)
  • сортирует элементы в естественном порядке или исходя из заданного компаратора