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