В буквальном смысле, я не знаю ни одной существующей реализации Map или Set, которая никогда не производит никакого мусора при добавлении и удалении ключа.
Фактически, единственный способ, которым этобыло бы даже технически возможно (в Java, используя API Map
и Set
, как определено), если бы вы установили строгую верхнюю границу для количества записей.Практические реализации Map и Set нуждаются в дополнительном состоянии, пропорциональном количеству элементов, которые они содержат.Это состояние должно храниться где-то, и когда текущее выделение будет превышено, хранилище необходимо расширить.В Java это означает, что должны быть выделены новые узлы.
(ОК, вы могли бы спроектировать класс структуры данных, который бы навсегда удерживал старые бесполезные узлы и, следовательно, никогда не генерировал мусор коллекционируемый ... но он все еще генерирует мусор.)
Итак, что вы можете сделать с этим на практике ... до уменьшить количество создаваемого мусора.Возьмем HashMap
в качестве примера:
Мусор создается при удалении записи.Это неизбежно, если вы не замените цепочки хеширования реализацией, которая никогда не освобождает узлы, представляющие записи цепочки.(И это плохая идея ... если только вы не можете гарантировать, что размер пула свободных узлов всегда будет маленьким. См. Ниже , почему это плохая идея.)
Мусор создается при изменении размера основного хеш-массива.Этого можно избежать двумя способами:
В конструкторе HashMap можно указать аргумент «емкость», чтобы задать размер исходного хеш-массива, достаточно большой, чтобы вам никогда не понадобилосьизменить его размер(Но это может привести к бесполезному расходу места ... особенно, если вы не можете точно предсказать, насколько большим будет HashMap
.)
Вы можете указать смешное значение для 'аргумент загрузки фактора, заставляющий HashMap никогда не изменять свой размер.(Но в результате получается HashMap, цепочки хеширования которого не ограничены, и в результате вы получаете O(N)
поведение для поиска, вставки, удаления и т. Д.
На самом деле создание мусора не является обязательно плохим для производительности. Действительно, зависание на узлах, чтобы сборщик мусора не собирал их на самом деле может быть хуже для производительности.
Стоимость запуска GC (при условии, что современный копировальный сборщик) в основном состоит из трех областей:
- Поиск узлов, которые не являются мусором.
- Копирование этих не-мусораузлы в "to-space".
- Обновление ссылок в других узлах без мусора для указания на объекты в "to-space".
(Если вы используете низкий-pause коллектор есть и другие затраты тоже ... обычно пропорционально количеству не-мусора.)
Единственная часть работы GC, которая на самом деле зависит от количества мусора, это обнуление памяти, чтомусорные объекты, когда-то занятые маготово к повторному использованию.И это можно сделать с помощью одного bzero
вызова для всего «пространства» ... или с помощью хитростей виртуальной памяти.
Предположим, что ваша структура приложения / данных зависает на узлах, чтобы избежать создания мусора.Теперь, когда GC запускается, он должен выполнить дополнительную работу, чтобы обойти все эти дополнительные узлы и скопировать их в «пространство», даже если они не содержат никакой полезной информации.Кроме того, эти узлы используют память, а это означает, что, если остальная часть приложения генерирует мусор, будет меньше места для его хранения, и GC необходимо будет запускать чаще.
И если вы использовалислабые / мягкие ссылки, позволяющие ГХ захватывать узлы из вашей структуры данных, тогда это еще больше работы для ГХ ... и пространство для представления этих ссылок.
Примечание: я не претендую на этот объектобъединение в пул всегда ухудшает производительность, как это часто бывает, особенно если пул становится неожиданно большим.
И, конечно, именно поэтому HashMap и аналогичные классы структуры данных общего назначения не выполняют никаких пулов объектов. Если бы они это сделали, они бы работали значительно хуже в ситуациях, когда программист этого не ожидал ... и они были бы действительно сломаны , IMO.
Наконец, существует простой способ настройки HashMap, так что добавление, за которым сразу следует удаление того же ключа, не создает мусора (гарантировано). Оберните его в класс Map, который кэширует последнюю «добавленную» запись и выполняет put
для действительного HashMap
, когда добавляется следующая запись. Конечно, это НЕ универсальное решение, но оно касается варианта использования вашего предыдущего вопроса.