Lab work : hash table with quotient filter
Статья (english) с описанием фильтра, его преимущества перед фильтром блума, математическое обоснование, тесты, описание алгоритмов.
Идея quotient фильтра заключается в разбиении хэша на частное и остаток, где частное играет роль индекса в таблице, а остаток записывается в слот таблицы вместе с 3-мя битами метаданных:
- Бит занятости: в слоте 𝑖 указывает, что в таблице содержится как минимум один хэш, частное которого равно 𝑖.
- Бит продолжения: указывает, что в этом слоте 𝑖 хранится хэш, частное которого то же самое, что и у хэша в предыдущем слоте 𝑖 − 1.
- Бит сдвига: в слоте 𝑖 указывает, что хранящийся в нём хэш имеет частное меньше, чем 𝑖.
Отрезком назовём область памяти хэш-таблицы, в которой упорядоченно записаны остатки хэшей, с одинаковым частным, в порядке возрастания. Началом отрезка назовём элемент, бит продолжения которого равен 0. Вместе с тем скажем, что начало отрезка сдвинуто (или: отрезок сдвинут), если бит сдвига равен 1, и не сдвинуто в противоположном случае. Серединой/концом отрезка назовём элемент, бит продолжения и сдвига которого равны 1. Кластером назовём последовательность отрезков без пустых слотов между ними, то есть, любой кластер предшествует пустому слоту или концу таблицы. Вообще говоря, в такой ситуации кластеры отделяются друг от друга пустыми слотами, но если рассматривать началом кластера первый не сдвинутый отрезок, то не бязательно началу кластера должен предшествовать пустой слот.
| Бит занятости | Бит продожения | Бит сдвига | Значение |
|---|---|---|---|
| 0 | 0 | 0 | Слот пуст. |
| 0 | 0 | 1 | Сдвинутое начало отрезка. |
| 0 | 1 | 0 | Не используется. Не смещённый элемент не может быть продолжением отрезка. |
| 0 | 1 | 1 | Середина или конец отрезка. |
| 1 | 0 | 0 | Не сдвинутое начало отрезка. |
| 1 | 0 | 1 | Сдвинутое начало отрезка. |
| 1 | 1 | 0 | Не используется. Не смещённый элемент не может быть продолжением отрезка. |
| 1 | 1 | 1 | Середина или конец отрезка. |
- E : пустой слот
- A : не сдвинутое начало отрезка
- C : Сдвинутое начало отрезка
- Z : Сдвинутое начало отрезка
- D : Продолжение отрезка
- B : Продолжение отрезка
C, Z и D, B отличаются только битом занятости, указывающим, что далее существует отрезок, сдвинутый из этой позиции. Стрелочка указывает, из какой именно позиции было смещено начало отрезка.
В проекте используется хэш-таблица размера 2^19 с 16-битными слотами для записи 32-битных хэшей. Таким образом, 32-битный хэш делится на 19-битное частное и 13-битный остаток. Такая таблица требует большего объёма памяти, но операции в ней будут выполняться быстрее (благодаря меньшему среднему размеру кластеров), а количество коллизий будет меньше (при условии умеренного заполнения таблицы).
Также, в комментариях к коду используется понятие пакет – группа остатков, принадлежащих одному частному.
Здесь не реализованы операции слияния хэш-таблиц, но преимущество quotient фильтра состоит и в том, что объединение таблиц производится тривиальным слиянием.