Структуры данных на практике. Глава 16: Фильтры Блума и вероятностные структуры данных

[navferty]

В части про фильтр Блума с подсчётом:

Компромисс: использует в 4 раза больше памяти (4 бита на счётчик вместо 1 бита), но поддерживает удаление.

В коде используется массив uint8_tб, с доступом по индексу, а по тексту и в комментарии в коде указано про 4 бита. Либо надо добавить битовые сдвиги byte >> 4 и byte & 0xF для работы с верхней и нижней частью, либо исправить текст (не 4, а 8 битов).

Также вопрос с переполнением - в приведённом примере есть "Защита от переполнения", но при добавлении и последующем удалении может привести (и рано или поздно обязательно приведёт) к неконсистентности, так что "молча" глотать переполнение - ИМХО худший вариант. Лучше бросать исключение или хотя бы возвращать bool isAdded из метода counting_bloom_insert (или передавать через out/ref параметр). Или вариант "зарезервировать" старшее значение 0xF для значения, которое уже не будет декрементировано при удалении. Тогда можно будет не сломать вставку, тем более что этот фильтр уже представляет собой вероятностную структуру.

Код из статьи, чтобы не скроллить вверх

typedef struct {
    uint8_t *counters;  // 4-битные счётчики (0-15)
    size_t m;
    int k;
} counting_bloom_t;

void counting_bloom_insert(counting_bloom_t *bf, const char *element) {
    for (int i = 0; i < bf->k; i++) {
        size_t pos = hash(element, i) % bf->m;
        if (bf->counters[pos] < 15) {  // Защита от переполнения
            bf->counters[pos]++;
        }
    }
}

void counting_bloom_delete(counting_bloom_t *bf, const char *element) {
    for (int i = 0; i < bf->k; i++) {
        size_t pos = hash(element, i) % bf->m;
        if (bf->counters[pos] > 0) {
            bf->counters[pos]--;
        }
    }
}

[Olegun]

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