Сложность O(1) vs O(n)
Когда выбираешь коллекцию, важно понимать: сколько шагов нужно операции, чтобы выполниться. Это и называется сложностью алгоритма (Big-O) — подробный разбор самого понятия в теме «Big-O», здесь — применительно к коллекциям.
O(1) — константное время. Не важно, 10 элементов в коллекции или 10 миллионов — операция выполняется за одно и то же время:
HashMap<String, Integer> map = new HashMap<>();
map.get("ключ"); // O(1) — мгновенно, независимо от размера mapO(n) — линейное время. Сложность растёт прямо пропорционально размеру коллекции:
List<String> list = new ArrayList<>();
list.contains("Артур"); // O(n) — в худшем случае проверит каждый элементКопнуть глубже
Сравнительная таблица по самым частым операциям:
| Операция | ArrayList | LinkedList | HashMap/HashSet | TreeMap/TreeSet |
|---|---|---|---|---|
| доступ по индексу | O(1) | O(n) | — | — |
| поиск по значению | O(n) | O(n) | O(1) | O(log n) |
| вставка в конец | O(1)* | O(1) | O(1) | O(log n) |
| вставка в начало | O(n) | O(1) | — | — |
*в среднем — иногда ArrayList нужно расширить внутренний массив, тогда дороже разово.
Вывод простой: для поиска по значению — HashMap/HashSet. Для доступа по индексу — ArrayList. Для частых вставок в начало/середину — LinkedList. Когда нужен порядок — TreeMap/TreeSet, ценой O(log n) вместо O(1).
• какую коллекцию выбрать под задачу поиска/вставки/порядка (если дошёл до 2-го слоя).