Вероятностные структуры данных
Вероятностные структуры (probabilistic data structures) дают приблизительный ответ, но экономят память и время по сравнению с точными структурами. Подходят для больших объёмов данных, где допустима небольшая погрешность.
Bloom filter (фильтр Блума)
Отвечает на вопрос «есть ли элемент в множестве» с одним видом ошибки:
- «элемент точно отсутствует» — гарантированно верно;
- «элемент возможно присутствует» — может быть ложноположительным (false positive).
Ложноотрицательных ответов не бывает. Использует битовый массив и несколько хэш-функций. Применяется для быстрой предварительной проверки перед дорогим обращением (например, «есть ли ключ в БД/кэше»).
HyperLogLog
Приблизительно оценивает количество уникальных элементов (cardinality) в очень больших наборах, используя крайне мало памяти (килобайты на миллиарды элементов). Погрешность — обычно несколько процентов.
Применяется для подсчёта уникальных посетителей, уникальных запросов и подобных метрик, где точное значение не критично.