Изменения

Существует связь между размером хранилища и шансом ложноположительного срабатывания. Поддерживаются операции добавления и удаления элементов нового элемента в множество. С увеличением размера хранимого множества повышается вероятность ложного срабатывания.

# <tex>is</tex> <tex>occupied</tex> бит занятости {{---}} равно единице, если ячейка является канонической для некого ключа в фильтре, сохраненого необязательно в этой ячейке. # <tex>is</tex> <tex>continuation</tex> бит продолжения {{---}} равно единице, если ячейка занята, но не первым элементов пробеге.# <tex>is</tex> <tex>shifted</tex> бит сдвига {{---}} равно единице, если пробег сдвинут относительно канонического слота. бит занятости бит продолжения бит сдвига0 0 0 : Пустая ячейка.0 0 1 : Ячейка содержит начало пробега, сдвинутого относительно канонического слота.0 1 0 : не используется.0 1 1 : Ячейка содержит элемент пробега(не первый), сдвинутого относительно канонического слота.1 0 0 : Ячейка содержит первый элемет пробега в его каноническом слоте.1 0 1 : Ячейка содержит первый элемет пробега, сдвинутого относительно канонического слота. Ячейка является канонической, для существующего пробега сдвинутого вправо.1 1 0 : не используется.1 1 1 : Ячейка содержит элемент пробега(не первый), сдвинутого относительно канонического слота. Ячейка является канонической, для существующего пробега сдвинутого вправо. === Поиск === Пусть мы ищем ключ D. Смотрим в его каноническую ячейку Dq. Если бит занятости не единица, то элемент точно не содержится в множестве.Если бит занятости единица, то нам нужно найти пробег для Dq. Так как начало нужного пробега может быть сдвинуто, найдем начало кластера. Идем влево от ячейки Dq и ищем первую с битом сдвига равным нулю, эта ячейка и будет началом кластера. Пока мы идем влево от Dq будем поддерживать счетчик, который бедет показывать сколько пробегов нам нужно будет пропустить от начала кластера. Каждая ячейка с битом занятости равным единице увеличивает счетчик на 1. После того как мы нашли начало кластера, пойдем от него в лево, каждая ячейка с битом продолжения равным нулю, говорит о завершении пробега, когда счетчик станет равным нулю мы найдем нажный нам пробег для Dq. Если в этом пробеге содержится Dr, то D вероятно содержится в множестве, иначе D точно не содержится в множестве. === Вставка === Анологично с поиском найдем найдем позицию для Dr, сдвигаем на одну позицию влево все эллементы кластера, начиная с выбранного, обновляем дополнительные биты.  * Сдвиг не влияет на бит занятости. Выставляем бит занятости в ячейке Dq в единицу.* Усли мы вставляем Dr в начало пробега, следовательно предыдущий элемент пробега стал вторым, у него нужно выставить бит продолжения.* Мы выставляем бит сдвига в единицу для каждой ячейки, что мы сдвинули.  == Преимущества == ***