Иерархия Collections Framework

Java Collections Framework — это набор интерфейсов и классов для работы с группами объектов. Основные интерфейсы:

Collection — базовый интерфейс для коллекций

List — упорядоченная коллекция с дубликатами

Set — коллекция без дубликатов

Map — ассоциативный массив (ключ-значение)

Queue — очередь для обработки в FIFO порядке

ArrayList

▸Внутренняя реализация

ArrayList — это обёртка над массивом Object[]. При добавлении элементов, если массив заполнен, создаётся новый массив в 1.5 раза больше, и элементы копируются.

java

1public class ArrayList<E> extends AbstractList<E> {
2    private static final int DEFAULT_CAPACITY = 10;
3    private Object[] elementData;
4    private int size;
5
6    public boolean add(E e) {
7        ensureCapacityInternal(size + 1);
8        elementData[size++] = e;
9        return true;
10    }
11
12    private void ensureCapacityInternal(int minCapacity) {
13        if (minCapacity > elementData.length)
14            grow(minCapacity);
15    }
16
17    private void grow(int minCapacity) {
18        int oldCapacity = elementData.length;
19        int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5x
20        elementData = Arrays.copyOf(elementData, newCapacity);
21    }
22}

▸Сложность операций

Добавление в конец: O(1) амортизированное

Добавление по индексу: O(n)

Получение по индексу: O(1)

Удаление по индексу: O(n)

Поиск: O(n)

LinkedList

▸Внутренняя реализация

LinkedList — это двусвязный список. Каждый элемент (Node) содержит ссылки на предыдущий и следующий элементы.

java

1public class LinkedList<E> extends AbstractSequentialList<E> {
2    transient int size = 0;
3    transient Node<E> first;
4    transient Node<E> last;
5
6    private static class Node<E> {
7        E item;
8        Node<E> next;
9        Node<E> prev;
10
11        Node(Node<E> prev, E element, Node<E> next) {
12            this.item = element;
13            this.next = next;
14            this.prev = prev;
15        }
16    }
17}

▸Сложность операций

Добавление в начало/конец: O(1)

Добавление по индексу: O(n)

Получение по индексу: O(n)

Удаление по индексу: O(n)

Поиск: O(n)

HashMap

▸Внутренняя реализация

HashMap использует массив Node[] (называемый table) с связным списком для разрешения коллизий. Начиная с Java 8, при размере цепочки > 8 элементов она заменяется на красно-чёрное дерево (TreeBin).

java

1public class HashMap<K,V> {
2    static final int DEFAULT_INITIAL_CAPACITY = 16;
3    static final float DEFAULT_LOAD_FACTOR = 0.75f;
4
5    transient Node<K,V>[] table;
6    transient int size;
7    int threshold;
8    final float loadFactor;
9
10    public V put(K key, V value) {
11        return putVal(hash(key), key, value, false, true);
12    }
13
14    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
15        Node<K,V>[] tab; Node<K,V> p; int n, i;
16        if ((tab = table) == null || (n = tab.length) == 0)
17            n = (tab = resize()).length;
18        if ((p = tab[i = (n - 1) & hash]) == null)
19            tab[i] = newNode(hash, key, value, null);
20        else {
21            // Обработка коллизий...
22        }
23    }
24}

▸Key-моменты

Load Factor (0.75) — порог заполненности перед расширением

Initial Capacity (16) — начальный размер массива

Hash Function — hash = key.hashCode() ^ (h >>> 16)

Bucket — индекс: (n-1) & hash

▸Сложность операций

Put: O(1) амортизированное

Get: O(1) амортизированное

Remove: O(1) амортизированное

Contains: O(1)

Другие важные коллекции

▸HashSet

Внутренняя обёртка над HashMap. Элементы хранятся как ключи, значения — фиктивный Object.

▸TreeMap

Красно-чёрное дерево. O(log n) для всех операций. Элементы отсортированы.

▸ConcurrentHashMap

Потокобезопасный HashMap. Использует сегментирование (Java 7) или CAS + synchronized (Java 8).

▸Queue/Deque

ArrayDeque — кольцевой массив, быстрее LinkedList для стеков/очередей

PriorityQueue — куча (heap), элементы выходят по приоритету

Когда что использовать

▸ArrayList vs LinkedList

ArrayList — быстрый доступ по индексу, итерация, добавление в конец

LinkedList — вставка/удаление в середину (редкий случай), очередь/стек

▸HashMap vs TreeMap vs LinkedHashMap

HashMap — быстрый поиск, нет порядка

TreeMap — нужна сортировка по ключу

LinkedHashMap — нужен порядок вставки

Практические советы

▸Инициализация с начальной ёмкостью

java

1// Если знаем размер — лучше сразу указать
2Map<String, User> users = new HashMap<>(expectedSize * 4 / 3 + 1);

▸Immutable Collections

java

1List<String> immutable = List.of("a", "b", "c");
2Map<String, Integer> map = Map.of("one", 1, "two", 2);

Заключение

Понимание внутренней реализации Java Collections — обязательная тема для собеседования. Знайте разницу в сложности операций, когда использовать ArrayList vs LinkedList, как работает хэширование в HashMap. Эти знания помогают принимать обоснованные решения о производительности.

#java#collections#hashmap#arraylist#algorithm

Java≈ 13 мин чтения18 марта 2024 г.

Java Collections: HashMap, ArrayList, LinkedList

Глубокий разбор Java Collections: внутренняя реализация HashMap, ArrayList, LinkedList, производительность и когда что использовать.

Иерархия Collections Framework

Java Collections Framework — это набор интерфейсов и классов для работы с группами объектов. Основные интерфейсы:

Collection — базовый интерфейс для коллекций

List — упорядоченная коллекция с дубликатами

Set — коллекция без дубликатов

Map — ассоциативный массив (ключ-значение)

Queue — очередь для обработки в FIFO порядке

ArrayList

▸Внутренняя реализация

java

1public class ArrayList<E> extends AbstractList<E> {
2    private static final int DEFAULT_CAPACITY = 10;
3    private Object[] elementData;
4    private int size;
5
6    public boolean add(E e) {
7        ensureCapacityInternal(size + 1);
8        elementData[size++] = e;
9        return true;
10    }
11
12    private void ensureCapacityInternal(int minCapacity) {
13        if (minCapacity > elementData.length)
14            grow(minCapacity);
15    }
16
17    private void grow(int minCapacity) {
18        int oldCapacity = elementData.length;
19        int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5x
20        elementData = Arrays.copyOf(elementData, newCapacity);
21    }
22}

▸Сложность операций

Добавление в конец: O(1) амортизированное

Добавление по индексу: O(n)

Получение по индексу: O(1)

Удаление по индексу: O(n)

Поиск: O(n)

LinkedList

▸Внутренняя реализация

LinkedList — это двусвязный список. Каждый элемент (Node) содержит ссылки на предыдущий и следующий элементы.

java

1public class LinkedList<E> extends AbstractSequentialList<E> {
2    transient int size = 0;
3    transient Node<E> first;
4    transient Node<E> last;
5
6    private static class Node<E> {
7        E item;
8        Node<E> next;
9        Node<E> prev;
10
11        Node(Node<E> prev, E element, Node<E> next) {
12            this.item = element;
13            this.next = next;
14            this.prev = prev;
15        }
16    }
17}

▸Сложность операций

Добавление в начало/конец: O(1)

Добавление по индексу: O(n)

Получение по индексу: O(n)

Удаление по индексу: O(n)

Поиск: O(n)

HashMap

▸Внутренняя реализация

java

1public class HashMap<K,V> {
2    static final int DEFAULT_INITIAL_CAPACITY = 16;
3    static final float DEFAULT_LOAD_FACTOR = 0.75f;
4
5    transient Node<K,V>[] table;
6    transient int size;
7    int threshold;
8    final float loadFactor;
9
10    public V put(K key, V value) {
11        return putVal(hash(key), key, value, false, true);
12    }
13
14    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
15        Node<K,V>[] tab; Node<K,V> p; int n, i;
16        if ((tab = table) == null || (n = tab.length) == 0)
17            n = (tab = resize()).length;
18        if ((p = tab[i = (n - 1) & hash]) == null)
19            tab[i] = newNode(hash, key, value, null);
20        else {
21            // Обработка коллизий...
22        }
23    }
24}

▸Key-моменты

Load Factor (0.75) — порог заполненности перед расширением

Initial Capacity (16) — начальный размер массива

Hash Function — hash = key.hashCode() ^ (h >>> 16)

Bucket — индекс: (n-1) & hash

▸Сложность операций

Put: O(1) амортизированное

Get: O(1) амортизированное

Remove: O(1) амортизированное

Contains: O(1)

Другие важные коллекции

▸HashSet

Внутренняя обёртка над HashMap. Элементы хранятся как ключи, значения — фиктивный Object.

▸TreeMap

Красно-чёрное дерево. O(log n) для всех операций. Элементы отсортированы.

▸ConcurrentHashMap

Потокобезопасный HashMap. Использует сегментирование (Java 7) или CAS + synchronized (Java 8).

▸Queue/Deque

ArrayDeque — кольцевой массив, быстрее LinkedList для стеков/очередей

PriorityQueue — куча (heap), элементы выходят по приоритету

Когда что использовать

▸ArrayList vs LinkedList

ArrayList — быстрый доступ по индексу, итерация, добавление в конец

LinkedList — вставка/удаление в середину (редкий случай), очередь/стек

▸HashMap vs TreeMap vs LinkedHashMap

HashMap — быстрый поиск, нет порядка

TreeMap — нужна сортировка по ключу

LinkedHashMap — нужен порядок вставки

Практические советы

▸Инициализация с начальной ёмкостью

java

1// Если знаем размер — лучше сразу указать
2Map<String, User> users = new HashMap<>(expectedSize * 4 / 3 + 1);

▸Immutable Collections

java

1List<String> immutable = List.of("a", "b", "c");
2Map<String, Integer> map = Map.of("one", 1, "two", 2);

Заключение

#java#collections#hashmap#arraylist#algorithm

🛠

Попробуйте наш инструмент

Закрепите знания с помощью интерактивных упражнений

Перейти →

Иерархия Collections Framework

ArrayList

▸Внутренняя реализация

▸Сложность операций

LinkedList

▸Внутренняя реализация

▸Сложность операций

HashMap

▸Внутренняя реализация

▸Key-моменты

▸Сложность операций

Другие важные коллекции

▸HashSet

▸TreeMap

▸ConcurrentHashMap

▸Queue/Deque

Когда что использовать

▸ArrayList vs LinkedList

▸HashMap vs TreeMap vs LinkedHashMap

Практические советы

▸Инициализация с начальной ёмкостью

▸Immutable Collections

Заключение

Попробуйте наш инструмент

Похожие статьи

React: полное руководство для собеседования

JavaScript: глубокий анализ для собеседования

Node.js и backend: что спрашивают на собеседовании

DevOps: от основ до продвинутого уровня

Иерархия Collections Framework

ArrayList

▸Внутренняя реализация

▸Сложность операций

LinkedList

▸Внутренняя реализация

▸Сложность операций

HashMap

▸Внутренняя реализация

▸Key-моменты

▸Сложность операций

Другие важные коллекции

▸HashSet

▸TreeMap

▸ConcurrentHashMap

▸Queue/Deque

Когда что использовать

▸ArrayList vs LinkedList

▸HashMap vs TreeMap vs LinkedHashMap

Практические советы

▸Инициализация с начальной ёмкостью

▸Immutable Collections

Заключение

Попробуйте наш инструмент

Похожие статьи

React: полное руководство для собеседования

JavaScript: глубокий анализ для собеседования

Node.js и backend: что спрашивают на собеседовании

DevOps: от основ до продвинутого уровня