Как оценить память решения с хеш-таблицей

Условие

Алгоритм проходит n целых чисел и хранит в map частоту каждого уникального значения. Какова дополнительная память и почему нельзя считать её только как размер ключей?

Ответ

Дополнительная память — O(k), где k число разных значений, в худшем случае O(n). Кроме ключей хранятся счётчики и служебная структура хеш-таблицы.

Учитывайте запас capacity, buckets, выравнивание и возможные временные аллокации при росте. Точные байты зависят от реализации и типов, поэтому их измеряют профилировщиком на репрезентативном наборе. Если диапазон значений мал и известен, массив счётчиков может быть компактнее map, но это другое ограничение задачи.