Действительно ли фильтры Блума быстрее, чем хэши, даже с учетом кеша?

Фильтры Блума выглядят действительно великолепно, если учесть, что вы можете определить, находится ли Int в наборе с вероятностью 99% в постоянном времени. Но так могут быть и хэши, с той лишь разницей, что в хэше большую часть времени вы обращаетесь к памяти только один раз. С фильтрами Блума вам нужно обращаться к ним ~ 7 раз за запрос в совершенно отдаленных местах , так что у вас будет несколько кеш-пропусков на запрос.

Я что-то пропустил?

Вам не хватает того, как две структуры данных справляются с коллизиями хэшей. Фильтры Блума не хранят фактические значения, поэтому требуемое пространство - это постоянный размер назначенного массива. Вместо этого, если вы используете традиционный хеш, он пытается сохранить все значения, которые вы ему даете, так что со временем он растет.

Рассмотрим упрощенную хеш-функцию (только для примера!) f(x) = x % 2. Теперь вы вводите следующие целые числа: 2, 3, 4, 5, 6, 7.

Стандартный хэш: данные значения будут хэшированы, и мы получим много коллизий из-за f(2) = f(4) = f(6) = 0и f(3) = f(5) = f(7) = 1. Тем не менее, хеш хранит все эти значения, и он сможет сказать вам, что 8не хранится в нем. Как оно это делает? Он отслеживает коллизии и сохраняет все значения с одинаковым хеш-значением, а затем, когда вы запрашиваете его, он дополнительно сравнивает ваш запрос. Итак, давайте запросим карту для 8:, f(8) = 0чтобы она посмотрела в корзину, в которую мы уже вставили, 2, 4, 6и нам нужно сделать 3 сравнения, чтобы сказать, что 8она не была частью ввода.

Фильтр Блума: обычно каждое входное значение хэшируется с kразличными хеш-функциями. Опять же, для простоты, давайте просто предположим, что мы используем только одну хеш-функцию f. Тогда нам нужен массив из 2 значений, и когда мы сталкиваемся с вводом, 2это означает, что из-за того, что f(2) = 0мы устанавливаем значение массива в положение 0равным значению 1. То же самое происходит в 4и 6. Аналогично, 3, 5, 7каждый из входов устанавливает значение массива 1в значение 1. Теперь мы запрашиваем, 8была ли часть ввода: f(8) = 0а массив в позиции 0равен 1, поэтому фильтр Блума будет ложно утверждать, что 8он действительно был частью ввода.

Для большей реалистичности давайте рассмотрим добавление второй хеш-функции g(x) = x % 10. При том, что входное значение 2приводит к двум хеш - значений f(2) = 0и g(2) = 2и две соответствующие позиции массива будет установлен 1. Конечно, массив теперь должен быть как минимум размером 10. Но когда мы запросим, 8мы проверим массив в позиции 8из-за g(8) = 8, и эта позиция все еще будет 0. Вот почему дополнительные хеш-функции уменьшают количество ложных срабатываний, которые вы получите.

Сравнение: Фильтр Блума использует kхеш-функции, что означает, kчто можно получить доступ к произвольным позициям массива. Но эта цифра точна. Вместо этого хеш гарантирует только амортизированное постоянное время доступа, но может де-генерировать в зависимости от характера вашей хеш-функции и входных данных. Так что это обычно быстрее, за исключением вырожденных случаев.

Однако после коллизии хеша стандартный хеш должен будет проверить равенство сохраненных значений по отношению к значению запроса. Эта проверка на равенство может быть сколь угодно дорогой и никогда не будет выполняться с фильтром Блума.

С точки зрения пространства, фильтр Блума является постоянным, так как никогда не нужно использовать больше памяти, чем назначенный массив. С другой стороны, хеш растет динамически и может стать намного больше из-за необходимости отслеживать конфликтующие значения.

Компромисс: Теперь, когда вы знаете, что дешево, а что нет и при каких обстоятельствах, вы сможете увидеть компромисс. Фильтры Блума хороши, если вы хотите очень быстро обнаружить, что значение было замечено ранее, но могут жить с ложными срабатываниями. С другой стороны, вы можете выбрать хэш-карту, если хотите получить гарантированную корректность за счет невозможности точно оценить время выполнения, но вы можете принимать случайные вырожденные случаи, которые могут быть намного медленнее, чем в среднем.

Точно так же, если вы находитесь в среде с ограниченной памятью, вы можете предпочесть фильтры Блума для гарантии их использования памяти.

Варианты использования фильтров и хэшей Блума различны и в основном не пересекаются, поэтому прямое сравнение не имеет смысла. Кроме того, это будет зависеть от технических деталей реализаций, так как существует множество способов обработки коллизий хешей с различными компромиссами.

Фильтр Блума может ответить, находится ли элемент в наборе для огромных наборов, с разумной вероятностью, но не совсем, используя скромный объем памяти. Огромные триллионы элементов. Но они никогда не бывают точными. Вы можете только уменьшить количество ложных срабатываний, используя больше памяти или больше хэш-функций.

С другой стороны, хеш-таблицы являются точными, но они должны хранить набор. Таким образом, триллионам элементов потребуется терабайт памяти (а это только американские триллионы). Они также могут хранить дополнительные данные для каждого элемента, чего не могут делать фильтры Блума.

Таким образом, фильтры Блума используются, когда у вас есть медленный метод получения данных для некоторого члена (который включает запросы к серверу, чтение с диска и т. Д.) Большого набора (который не помещается в памяти или нецелесообразно передавать его клиенту). или тому подобное) и хотят избежать запуска медленной операции для объектов, которых нет в наборе.