В пятницу на code review я наткнулся на метод, который обрабатывал список клиентов по 12 секунд. Терпимо для теста, убийственно для прода. Дата - 3 ноября 2026 г., а задача - классическая: O(n²) там, где нужен O
. Давайте разберём её на атомы. . Второй проход - O. Итого O. Время упало до 50 мс. Но вот что интересно: на бумаге хэш-таблица решает всё. На деле - если коллизий много, а GC давит, обычная сортировка с двумя указателями может дать фору. Я прогнал тест: в нашем случае (строки до 50 символов) сортировка + бинарный поиск проиграла хэшу в 2 раза. А вот на числах - выиграла. Мораль: не верь бенчмаркам из блогов. Замеряй на своих данных. Шаги к оптимизации: по времени - это O по памяти. 150к строк в хэше - это ~20 МБ. Для микросервиса - пустяк. Для embedded - смерть. Я видел код, где ради скорости запилили HashMap на 10 млн записей. Сервис жрал 2 ГБ на старте. Стоило ли оно того? Нет, потому что узким местом оказалась база данных, а не CPU. Кстати, про память на Java. Integer в HashMap - это объект. 150к Integer - это 150к объектов. Плюс boxing. Если очень хочется speed, а память жмёт - используй библиотеки с примитивами (например, Koloboke или Trove). На стандартной HashMap ты теряешь ~40% памяти на обёртки. Ещё момент - GC. Если твой хэш живёт вечно - ок. Если он создаётся на каждый HTTP-запрос - ты умрёшь под garbage collector-ом. Тут лучше простой массив или сортировка на месте. В продакшене я однажды встретил кэш на HashMap, который чистился раз в минуту. 60 миллионов объектов. GC Stop-the-world длился 500 мс. Всё ради того, чтобы не пересчитывать 3 поля. Решение: WeakHashMap или ручной TTL с проверкой при гетте.
Итог: не оптимизируй вслепую. Сначала замерь, потом бей. Конкретный план действий: читай Хабр про профилирование, ставь Async Profiler, прогоняй тесты. Кстати, если интересен разбор конкретной вашей задачи - кидайте код в тред. Я могу прогнать через профилировщик и написать пост с результатами.
. Давайте разберём её на атомы. Исходная задача и грабли
Дано: массив строк на 150к элементов. Найти первую неповторяющуюся. В лоб - два вложенных цикла. 150к × 150к = 22.5 миллиарда операций. На Java 21 это вылилось в 12 секунд ровного процессорного времени. Код выглядел так: for (i...) { for (j...) { if (arr.equals(arr[j])) { ... } } }. Профилировщик показал, что 95% времени уходит на equals. Строки длинные, до 200 символов. equals - дешёвый, но 22.5 млрд вызовов превращают его в тормоз. А если строки одинаковые? equals быстро отсечёт, но в худшем случае (все разные) он будет гонять весь массив. Почему так вышло? Потому что автор просто хотел «сделать быстро» и не подумал о масштабировании. Работает же! Типичные грабли:- Забыли про сложность алгоритма
- Не заглянули в требования по времени
- Проигнорировали дебаг-профилировщик
Брутфорс против хэшей: замеры
Первая мысль - LinkedHashMap. Сложил, проверил, получил 150 мс. Уже хорошо, но хочется быстрее. Используем HashMap для подсчёта. Первый проход - O. Второй проход - O. Итого O. Время упало до 50 мс. Но вот что интересно: на бумаге хэш-таблица решает всё. На деле - если коллизий много, а GC давит, обычная сортировка с двумя указателями может дать фору. Я прогнал тест: в нашем случае (строки до 50 символов) сортировка + бинарный поиск проиграла хэшу в 2 раза. А вот на числах - выиграла. Мораль: не верь бенчмаркам из блогов. Замеряй на своих данных. Шаги к оптимизации: - Поставить таймер (System.nanoTime)
- Написать тест с профилировщиком (JFR, Async Profiler)
- Сменить структуру данных
- Проверить на граничных кейсах
А что с памятью? Цена скорости
Тут и начинается самое мясо. O по времени - это O по памяти. 150к строк в хэше - это ~20 МБ. Для микросервиса - пустяк. Для embedded - смерть. Я видел код, где ради скорости запилили HashMap на 10 млн записей. Сервис жрал 2 ГБ на старте. Стоило ли оно того? Нет, потому что узким местом оказалась база данных, а не CPU. Кстати, про память на Java. Integer в HashMap - это объект. 150к Integer - это 150к объектов. Плюс boxing. Если очень хочется speed, а память жмёт - используй библиотеки с примитивами (например, Koloboke или Trove). На стандартной HashMap ты теряешь ~40% памяти на обёртки. Ещё момент - GC. Если твой хэш живёт вечно - ок. Если он создаётся на каждый HTTP-запрос - ты умрёшь под garbage collector-ом. Тут лучше простой массив или сортировка на месте. В продакшене я однажды встретил кэш на HashMap, который чистился раз в минуту. 60 миллионов объектов. GC Stop-the-world длился 500 мс. Всё ради того, чтобы не пересчитывать 3 поля. Решение: WeakHashMap или ручной TTL с проверкой при гетте. FAQ: частые вопросы по оптимизации
Вопрос: А что если данных мало? Стоит ли заморачиваться? Ответ: Для 100 элементов - нет. Для 1000 - смотри по TPS. Для 10к+ - обязательно. Вопрос: Stream API медленный? Ответ: Да, но не критично. Обычно 10-20% оверхеда. Если это не hot path - пиши в стримах, код чище. Вопрос: Стоит ли писать на C через FFI ради скорости? Ответ: Почти никогда. Только если ты считаешь хэши или парсишь гигабайты. Накладные расходы на вызов нативного кода съедят весь профит.