Являются ли разные соленые хэши эквивалентными разным алгоритмам хеширования для фильтра Блума?

По мере того, как ваш набор данных становится больше, вам нужно больше алгоритмов хеширования, чтобы поддерживать низкий уровень ложных срабатываний на уровне 1%.

Если я хочу, чтобы мой фильтр Блума динамически рос во время выполнения, неизвестно, сколько алгоритмов хеширования мне потребуется. Если я использую тот же (скажем, MD5) хэшер, но со случайно сгенерированными солями, которые добавляются к значению перед его хешированием, будет ли это иметь тот же эффект, что и использование другого хэшера (скажем, MD5, SHA1 и т. д.)?

Я использую .NET C# для справки, но язык почти не имеет значения для этого вопроса.


hash data-structures bloom-filter
person user1909158    schedule 24.03.2014    source источник

Ответы (1)


arrow_upward
2
arrow_downward

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

Как вы заметили, для фильтра Блума требуется множество хеш-функций. Придумать 17 уникальных хэш-функций в лучшем случае сложно. К счастью, есть способ избежать этого. Я использовал технику, описанную в статье Меньше хеширования, та же производительность: построение Улучшенный фильтр Блума. Это оказалось очень просто на C#, и производительность была очень хорошей.

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

Кроме того, фильтры Блума, как правило, не так легко динамически изменять. Если вы хотите, чтобы фильтр Блума увеличивался, вам нужно специально создать масштабируемый фильтр Блума, который его поддерживает. Поиск в Google по [масштабируемому фильтру Блума] предоставит ряд ссылок и несколько примеров кода.

person Jim Mischel    schedule 24.03.2014