Bloom Filter🌸 Пока все копаются в иишном схематическом поиске, кто-то продолжает копаться в вещах попроще классических алгоритмах фильтрации. Около года назад увидела Bloom filter в одном из обновлении кликхаус, и только сейчас захотелось его разобрать. Если кратко: это быстрая вероятностная проверка принадлежности элемента множеству без хранения самих элементов. То есть мы получаем ответ либо «точно нет», либо «возможно, да»: допускаем ложноположительные (lp) срабатывания, но выигрываем в скорости и памяти. Интуитивно блум работает очень просто: каждая из k хеш-функций указывает на свою позицию в битовом массиве и включает соответствующий бит. При проверке элемента мы снова прогоняем его через все хеш-функции и смотрим, включены ли все нужные биты. Если хотя бы один бит выключен - значит элемент точно не добавлялся; если включены все - элемент «возможно» есть. Полезен данный метод поиска в кейсах, где важно максимально быстро отсеивать заведомо отсутствующие элементы. Структуру блум фильтра можно описать так: type BloomFilter struct { m uint64 // количество бит в битовом массиве k uint64 // количество хеш-функций bitset []uint64 // сами биты, упакованные в слова по 64 бит hashFuncs []func([]byte) uint64 // список хеш-функций } При создании фильтра сначала рассчитываем количество бит. Для этого задаём число бит на элемент (оно влияет на вероятность ложных срабатываний, об этом расскажу позже) и умножаем его на ожидаемое количество элементов. // Общее число бит в битсете m := expectedItems bitsPerItem // Сколько слов нужно для bitset с округлением вверх: wordCount := (m + 63) / 64 После того, зная нужное количество uint64, остаётся выделить слайс под битовый массив и создать k хеш-функций.. bitset := make([]uint64, wordCount) hashFuncs := make([]func([]byte) uint64, k) Определение индекса слова и бита в нем строится на паре простых шагов: 1. Находим модуль от деления хеша на размер битсета (pos), делим на 64 (получаем индекс слова) 2. Находим модуль от деления pos на 64 (получаем индекс бита внутри слова), по нему строим маску с включенным битом на нужной позиции. func (bf BloomFilter) bitLocation(hashValue uint64) (uint64, uint64) { // Приводим хеш к диапазону [0, m) через остаток по m pos := hashValue % bf.m // Индекс слова wordIndex := pos / 64 // Индекс бита внутри слова bitIndex := pos % 64 mask := uint64(1) << bitIndex return wordIndex, mask } И вставка и поиск прогоняют элемент через хеш-функцию, на каждой итерации ищем индекс слова и маску для целевого бита внутри слова по алгоритму выше и: - включаем соответствующий бит (вставка): bf.bitset[wordIndex] |= mask - проверяем, включен ли нужный бит (поиск): return (bf.bitset[wordIndex] & mask) != 0 В случае поиска, если нужный бит включен, значит элемент возможно есть; и точно нет - если наоборот: func (bf *BloomFilter) Contains(item []byte) bool { // Для каждого хеша проверяем соответствующий бит for i := uint64(0); i < bf.k; i++ { h := bf.hashFuncs[i] hashValue := h(item) // Если хоть один бит не установлен - элемента точно нет if !bf.isBitSet(hashValue) { return false } } // Каждый найденный бит включен - элемент "возможно" есть return true } Отмечу, что важны как раз не коллизии хеша, а совпадения по модулю от m, тк разные элементы могут попадать в одну и ту же позицию - это и есть источник lp кейсов. Чтобы уменьшить вероятность таких пересечений, обычно увеличивают число бит m и подбирают их отношение к числу элементов n и количеству хеш‑функций k по одной формуле отсюда Отсюда и следует правило: если бит на элемент мало - значит много пересечений - значит будет высокая вероятность lp ответов; соответственно, если бит много, то фильтр будет точнее, но и по памяти просядет. Поэтому лучше отталкиваться от того, какую вероятность lp можно допустить :) А еще заметили важный плюс - можно смело распараллелить процесс за счет идемпоте