[Перевод] Структуры данных на практике. Глава 16: Фильтры Блума и вероятностные структуры данных

28 июн 2026

Наш веб-краулер потреблял 128 МБ ОЗУ только на отслеживание посещённых URL. На встраиваемом устройстве с 256 МБ это была половина всей памяти.Задача краулера была простой: отслеживать посещённые URL, чтобы не краулить одну и ту же страницу дважды. После обработки 1 миллиона URL (средняя длина 80 байт) хэш-таблица, в которой хранились эти URL, разрослась до 96 МБ плюс оверхед.«Можем ли мы обменять точность на память? Нас вполне устроит несколько дублированных операций, если это позволит сэкономить большой объём памяти», — сказал мне мой менеджер во время ревью кода.Этот вопрос изменил всё. На самом деле, идеальная точность не требуется. Если мы случайно обработаем одну страницу дважды, то впустую потратим часть пропускной способности, но ничего не поломаем. Главным ограничением была память. Читать далее