Изменения

Перейти к: навигация, поиск

Обсуждение участника:Kurkin

284 байта добавлено, 20:46, 6 июня 2015
Нет описания правки
=Quotient filter={{Определение|definition ='''Quotient filter''' {{---}} вероятностная структура данных, позволяющая проверить принадлежность элемента множеству. При этом существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное(элемент в множестве есть, но структура данных сообщает, что его нет).}}
Существует связь между размером хранилища и шансом ложноположительного срабатывания. Поддерживаются операции добавления нового элемента в множество. С увеличением размера хранимого множества повышается вероятность ложного срабатывания.
* Простое увеличение или уменьшение хеш таблицы, достаточно перенести один бит из остатка в частное или наоборот.
* Простое слияние двух фильтров.
 
==См. Также==
 
*[[:Идеальное_хеширование|Идеальное хеширование]]
*[[:Универсальное_хеширование|Универсальное хеширование]]
 
== Источники ==
41
правка

Навигация