Чем отличается стоимость get, add и contains у реализаций List, Set и Map?
ArrayList даёт get по индексу за O(1) и амортизированное O(1) на добавление в конец, но contains сканирует за O(n). LinkedList даёт O(1) только на концах; get по индексу и contains — O(n). HashMap и HashSet в среднем дают O(1) на все три операции, деградируя до O(log n) в бакете-дереве и до O(n) при вырожденном hashCode. TreeMap и TreeSet — O(log n) на любую операцию в обмен на отсортированный порядок.
- ✗Считать, что
LinkedListиндексируется заO(1), раз это связная структура - ✗Называть
O(1)худшим случаемHashMap, игнорируя коллизии и плохойhashCode - ✗Забывать, что
containsу любогоList— линейный проход, а не поиск по хешу
- →Почему добавление в конец
ArrayList— амортизированноеO(1), а не простоO(1)? - →Когда
LinkedListреально выигрывает уArrayList, несмотря на худшую локальность кеша?
Таблица сложности
| Операция | ArrayList | LinkedList | HashMap / HashSet | TreeMap / TreeSet |
|---|---|---|---|---|
get по ключу/индексу | O(1) | O(n) | O(1) в среднем | O(log n) |
add | O(1) амортизированно (в конец) | O(1) на концах | O(1) в среднем | O(log n) |
contains | O(n) | O(n) | O(1) в среднем | O(log n) |
| порядок обхода | вставки | вставки | не гарантирован | сортированный |
Почему ArrayList.add — амортизированное O(1). Массив растёт удвоением: одна вставка изредка стоит O(n) на копирование, но эта цена размазывается по всем предыдущим дешёвым вставкам.
Где деградирует хеш. Средняя O(1) у HashMap держится на равномерном hashCode. Если все ключи попадают в один бакет, поиск превращается в проход по цепочке — O(n); с Java 8 длинная цепочка в достаточно большой таблице становится красно-чёрным деревом, ограничивая худший случай O(log n).
Чего стоит порядок. TreeMap/TreeSet платят O(log n) на каждой операции, потому что держат ключи отсортированными и умеют отвечать на диапазонные запросы (headMap, subSet), чего хеш-структуры не умеют вовсе.
⚠️ Типичная ловушка: LinkedList не индексируется быстро. get(i) идёт по ссылкам от ближайшего конца — O(n). Его сильная сторона — вставка и удаление на концах и по уже имеющемуся итератору.
