Изменения

Фильтр представляет собой [[:Хеш-таблица|хеш-таблицу]], в которой харанится часть ключа и <tex>3</tex> бита дополнительной информации. Они используются для разрешения ситуации, когда хеш различных ключей указывает на одну ячейку в хеш -таблице. В Quotient quotient filter хеш -функция возвращает <tex>p</tex> битовый хеш, последние r бит которого называются '''остатком''' (англ. ''remainder''), а <tex>q = p - r</tex> старших бит называются '''частным ''' (англ. ''quotient''), отсюда название структуры Quotient filter<ref>Knuth, Donald (1973). The Art of Computer Programming:Searching and Sorting, volume 3. Section 6.4, exercise 13: Addison Wesley</ref>. Размер хеш -таблицы составляет <tex>2^q</tex>.

Пусть у нас есть ключ <tex>K</tex>, его хеш обозначим <tex>H(k)</tex>, остаток <tex>H_r</tex> и частное <tex>H_q</tex>. Попробуем поместить остаток в хеш -таблицу в ячейку <tex>H_q</tex>, называемую канонической. Возможно, ячейка уже занята, так как существует шанс полных коллизий (остаток и частное разных ключей совпадают) или частичных коллизий (частное разных ключей совпадают). Когда каноническая ячейка занята, помещаем остаток в какую-то ячейку справа.

Последовательность ячеек, имеющих одинаковые частные называется '''пробегом ''' (англ. ''run''). Возможно, что начало пробега не занимает канонический слот, если он уже занят каким-то другим пробегом.

Пробег, у которого первый элемент занимает каноническую ячейку, является началом кластера. '''Кластер ''' (англ. ''cluster'') {{---}} объединение последовательных пробегов, концом кластера является пустая ячейка или начало другого кластера.

# * бит занятости {{---}} равен единице, если ячейка является канонической для некого ключа в фильтре, сохраненого необязательно в этой ячейке. ,# * бит продолжения {{---}} равен единице, если ячейка занята, но не первым элементов пробеге.,# * бит сдвига {{---}} равен единице, если пробег сдвинут относительно канонического слота.

* Простое увеличение или уменьшение хеш -таблицы, достаточно перенести один бит из остатка в частное или наоборот.