В этом вопросе у вас есть только две структуры данных в C #, так как словари в C # реализованы с использованием хеш-таблиц.Поэтому мы будем ссылаться на Dictionary и HashTable как на хеш-таблицы.Если вы используете один из них, то, вероятно, вам нужен словарь из-за безопасности типов и производительности, как описано здесь: Почему словарь предпочтительнее хеш-таблицы? Но так как словарь реализован с использованием хеш-таблицы, он не является огромнымразница в любом случае.
Но реальный вопрос - хеш-таблица (словарь) против фильтра Блума.Кто-то ранее задавал связанный вопрос: В чем преимущество использования фильтров Блума? Они также ссылаются на страницу Википедии по фильтрам Блума, которая является довольно информативной: https://en.wikipedia.org/wiki/Bloom_filter Короткие версииОтвет в том, что фильтры Блума меньше и быстрее.Однако у них есть стоимость, связанная с этим: они не совсем точны.В хэш-таблице исходная строка всегда сохраняется для точного сравнения.Сначала вы хэшируете значение, и это говорит вам, где в таблице искать.После того, как вы посмотрели в таблице, вы сравниваете расположенное там значение со значением, которое вы ищете.В фильтре Блума вы используете несколько хешей для вычисления набора местоположений.Если во всех этих местах есть единицы, то вы считаете, что строка найдена.Это означает, что иногда будут «найдены» строки, которые изначально не были вставлены.Если таблица слишком мала, на самом деле вы можете достичь точки насыщения, где может показаться, что любая строка, которую вы пробовали, будет в фильтре Блума.Поскольку вы знаете, сколько строк вы собираетесь вставить, вы можете соответствующим образом изменить размер таблицы.
Давайте рассмотрим соответствующие размеры.Чтобы цифры были четкими, я сделаю вид, что у вас ровно 4096 строк.Чтобы иметь относительно низкую коллизию хеш-таблицы, вы бы хотели, чтобы ваша таблица была как минимум такой же, как количество строк.Таким образом, реалистично (при условии 32-битных (4-байтовых) указателей), в этом случае вы бы смотрели размер таблицы 4096 * 4 байта = 16 КБ, плюс 4096 * (4 + 4 + 8) = 64 КБ для таблицы.узлы списка (следующий указатель + указатель строки) и строки.Таким образом, в общей сложности, вероятно, около 80 КБ, что, вероятно, не очень много памяти в большинстве ситуаций, когда вы будете использовать C #.
Для фильтров Блума мы должны решить, какую частоту ошибок мы хотим достичь внаши расчеты размера.Когда мы говорим о частоте ошибок 1%, это будет означать, что из каждых 100 строк, которые не были вставлены в фильтр Блума, 1 будет ошибочно указано как присутствующее.Вставленные строки всегда будут правильно обозначены как вставленные.Используя уравнение m = -n * ln (p) / (ln (2) ^ 2), мы можем вычислить минимальный размер, чтобы дать нам определенный коэффициент ошибок.В этом уравнении m - это количество слотов в таблице, p - частота ошибок, а n - количество вставляемых строк.Итак, если мы установим p равным 0,01 (ошибка 1%), то получим примерно 9,6 * 4096 бит = 9,6 * 512 байт = 4,8 КБ, что, очевидно, немного меньше.Но, на самом деле, 1% является чем-то высоким для уровня ошибок.Более того, на самом деле, мы, вероятно, должны пойти на что-то более 0,0001%, что составляет 28,8 * 4096b бит = 28,8 * 512 байт = 14,4 КБ.Очевидно, что любой из них существенно меньше, чем 80К, которые мы рассчитали для хеш-таблицы.Тем не менее, хэш-таблица имеет уровень ошибок 0, который явно меньше 1% или 0,0001%.
Так что, на самом деле, вам решать, стоит ли в вашей ситуации компромисспотерять некоторую точность, чтобы набрать небольшую скорость и немного времени стоит.В действительности, любой из этих вариантов может быть достаточно маленьким и быстрым для подавляющего большинства ситуаций в реальном мире.