Какую хеш-функцию использовать для блум-фильтра с 128-битными ключами?

Я не понимаю, почему вы хотели бы использовать здесь генератор случайных чисел ... однако я могу помочь вам ускорить процесс.

Фильтр Блума - это, по сути, битовый вектор, в котором вы устанавливаете биты. Если вы хотите выяснить, существует ли элемент, фильтр цветения выдаст вам истину, если элемент возможно существует, и ложь, если элемент наверняка не существует .

(Я делаю это в простом текстовом редакторе, поэтому в коде могут быть ошибки)

Я предполагаю, что ваше хеш-пространство может использовать 32-битные целочисленные вычисления; если у вас очень большая таблица цветения, вы, вероятно, захотите использовать 64-битное целое число.

Самая простая (и, вероятно, самая быстрая) реализация фильтра Блума:

byte[] bloomFilter = new byte[MyBloomFilterSize];

foreach (var item in myItems) 
{
    int hash = Hash(item) & 0x7FFFFFFF;
    int bit = 1 << (hash & 7); // you have 8 bits
    int index = (hash >> 3) % MyBloomFilterSize;
    bloomFilter[hash % MyBloomFilterSize] |= bit;
}

Вы можете поэкспериментировать с изменением byte[] на uint[] или ulong[]; Я не уверен, что это имеет значение.

Если затем вы хотите проверить, может ли элемент существовать, вы вычисляете тот же индекс и бит и получаете результат.

public bool PossiblyExists(MyItem item)
{
    int hash = Hash(item) & 0x7FFFFFFF;

    int bit = 1 << (hash & 7); // you have 8 bits
    int index = (hash >> 3) % MyBloomFilterSize;
    return (bloomFilter[hash % MyBloomFilterSize] & bit) != 0;
}

Единственное, что здесь остается, - это скорость, с которой вы можете вычислить хеш. Если вы используете целое число, я бы просто умножил его на большое простое число; если вы используете байт [] фиксированной длины SHA256 (что вы, кажется, делаете), вам нужно сделать его целым (или длинным).

Я использую небольшой трюк с Buffer.BlockCopy для преобразования типов. В целях безопасности я предпочитаю использовать несколько байтов из данных, но поскольку SHA256 уже должен быть случайным, простой BitConverter.ToInt32(data, [0..28]) также должен помочь.

public int CalculateHash(byte[] data) 
{
    // Data = >128 bits = >16 bytes -- which is the same as >4 integers

    int[] tmp = new int[4];
    Buffer.BlockCopy(data, 0, tmp, 0, data.Length);
    return tmp[0] ^ tmp[1] ^ tmp[2] ^ tmp[3];
}

Это должно сработать.

Эффективная реализация могла бы быть, например, следующей. Если у вас есть хеш-функция, которая возвращает 64 бита, лучше использовать ее вместо murmur3_64. Предупреждение: я не тестировал.

void Add(string item) {
    ulong hash = murmur3_64((ulong) item.GetHashCode());
    uint a = (uint) (hash >> 32);
    uint b = (uint) hash;
    for (int i = 0; i < k; i++) {
        _bitArray[reduce(a, _bitSize)] = true;
        // "Less Hashing, Same Performance: Building a Better Bloom Filter"
        a += b;
    }
}

ulong murmur3_64(ulong x) {
    x = (x ^ (x >> 33)) * 0xff51afd7ed558ccdL;
    x = (x ^ (x >> 23)) * 0xc4ceb9fe1a85ec53L;
    x = x ^ (x >> 33);
    return x;
}

uint reduce(uint hash, uint n) {
    // http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
    return (hash * n) >> 32;
}