Отличный обзор по асимптотике! Есть несколько нюансов, которые часто упускают:
- Big-O обычно не равно реальная производительность. Асимптотика описывает масштабирование, но в JVM важны кеш-локальность и аллокации. Поэтому ArrayList на практике почти всегда выигрывает у LinkedList, даже там, где формально у последнего есть O(1) операции.
- HashMap: защита от деградации - не норма работы. Treeification происходит при >= 8 элементов в бакете и при размере таблицы >= 64 - иначе сначала будет resize. Это защитный механизм от коллизий, но в проде важно не надеяться на него, а обеспечивать корректный hashCode() и правильный initial capacity.
- Инициализация размера. Чтобы избежать resize, правильнее считать expectedSize / loadFactor + 1. Для 10_000 элементов при loadFactor 0.75 это примерно 13_334. Простое умножение на 2 - рабочее, но не точное приближение.
- Очереди. Для deque/queue сейчас почти всегда лучше ArrayDeque - меньше памяти на элемент и лучше кэширование, чем у LinkedList.
В остальном - прекрасный базовый материал, полезный для систематизации знаний у новичков.
Статья и правда опирается на корпус данных 2000-х. Сейчас типология (Bondarenko), синергетика (Котин) и вероятностные модели (Thomason & Kaufman) дают точные оценки, но полную сепарацию адстрата от имманентного развития называют "уровнем постановки проблем" (Bondarenko). Максимум - повышают вероятность интерпретаций через типологию и геолингвистику. Новых исследований по теме нет - фокус ушёл в нейролингвистику.
Отличный обзор по асимптотике!
Есть несколько нюансов, которые часто упускают:
- Big-O обычно не равно реальная производительность. Асимптотика описывает масштабирование, но в JVM важны кеш-локальность и аллокации. Поэтому ArrayList на практике почти всегда выигрывает у LinkedList, даже там, где формально у последнего есть O(1) операции.
- HashMap: защита от деградации - не норма работы. Treeification происходит при >= 8 элементов в бакете и при размере таблицы >= 64 - иначе сначала будет resize. Это защитный механизм от коллизий, но в проде важно не надеяться на него, а обеспечивать корректный hashCode() и правильный initial capacity.
- Инициализация размера. Чтобы избежать resize, правильнее считать expectedSize / loadFactor + 1. Для 10_000 элементов при loadFactor 0.75 это примерно 13_334. Простое умножение на 2 - рабочее, но не точное приближение.
- Очереди. Для deque/queue сейчас почти всегда лучше ArrayDeque - меньше памяти на элемент и лучше кэширование, чем у LinkedList.
В остальном - прекрасный базовый материал, полезный для систематизации знаний у новичков.
Статья и правда опирается на корпус данных 2000-х. Сейчас типология (Bondarenko), синергетика (Котин) и вероятностные модели (Thomason & Kaufman) дают точные оценки, но полную сепарацию адстрата от имманентного развития называют "уровнем постановки проблем" (Bondarenko). Максимум - повышают вероятность интерпретаций через типологию и геолингвистику. Новых исследований по теме нет - фокус ушёл в нейролингвистику.