41
правка
Изменения
Нет описания правки
==Описание структуры данных==
Фильтр представляет собой [[:Хеш-таблица|хеш-таблицу]], в которой харанится часть ключа и 3 бита дополнительной информации. Они используются для разрешения ситуации, когда хеш различных ключей указывает на одну ячейку в хеш таблице. В <tex>Quotient filter</tex> хеш функция возвращает <tex>p</tex> битовый хеш, последние r бит которого называются остатком, а <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>D</tex>, его хеш обозначим <tex>Dh</tex>, остаток <tex>Dr</tex> и частное <tex>Dq</tex>. Попробуем поместить остаток в хеш таблицу в ячейку <tex>Dq</tex>, называемую канонической. Возможно, ячейка уже занята, так как существует шанс полных коллизий (остаток и частное разных ключей совпадают) или частичных коллизий (частное разных ключей совпадают). Когда каноническая ячейка занята, помещаем остаток в какую-то ячейку справа.
