Изменения

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

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

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

Навигация