Изменения

Фильтр представляет собой [[:Хеш-таблица|хеш-таблицу]], в которой харанится часть ключа и <tex>3</tex> бита дополнительной информации. Они используются для разрешения ситуации, когда хеш различных ключей указывает на одну ячейку в хеш-таблице. В quotient filter хеш-функция возвращает <tex>p</tex> битовый хеш, последние <tex>r </tex> бит которого называются '''остатком''' (англ. ''remainder''), а <tex>q = p - r</tex> старших бит называются '''частным''' (англ. ''quotient''), отсюда название структуры 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>3</tex> бита дополнительной информации (удобно хранить в целочисленном типе, используя <tex>3</tex> старших бита под дополнительную информацию, а оставшиеся биты под остаток, накладывает ограничение на размер остатка). Они используются для разрешения ситуации, когда частное различных ключей указывает на одну ячейку в хеш-таблице. Размер хеш-таблицы составляет <tex>2^q</tex>, так как есть всего <tex>2^q</tex> разных частных.

Пусть у нас есть ключ <tex>K</tex>, его хеш обозначим <tex>h(K)</tex>, остаток <tex>h_r</tex> и частное <tex>h_q</tex>. Попробуем поместить остаток в хеш-таблицу в ячейку с индексом <tex>h_q</tex>, называемую канонической. Возможно, ячейка уже занята, так как существует шанс полных коллизий (остаток и частное разных ключей совпадают) или частичных коллизий (частное разных ключей совпадают). При полной коллизии мы получим ложноположительное срабатывание, но при частичной коллизии с помощью дополнительных битов это избегается. Когда каноническая ячейка занята, помещаем остаток в какую-то ячейку справа. Этот способ решения колизий схож с [[:Разрешение_коллизий|линейным методом разрешения колизий]].

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