Какие методы хеширования использовать при создании фильтра Блума в clojure?

Самое интересное в фильтрах Блума заключается в том, что для эффективной работы им нужно несколько хеш-функций.

Строки Java уже имеют одну встроенную хэш-функцию, которую вы можете использовать — String.hashCode() with возвращает 32-битный целочисленный хэш. Это нормальный хэш-код для большинства целей, и, возможно, этого достаточно: например, если вы разделите его на 2 отдельных 16-битных хэш-кода, этого может быть достаточно для работы вашего фильтра Блума. Вы, вероятно, получите несколько коллизий, но это нормально — фильтры Блума должны иметь некоторые коллизии.

Если нет, вы, вероятно, захотите создать свой собственный, и в этом случае я бы рекомендовал использовать String.getChars() для доступа к необработанным данным char, а затем используйте это для вычисления нескольких хэш-кодов. .

Код Clojure для начала работы (просто суммируя значения символов):

(let [s "Hello"
      n (count s)
      cs (char-array n)]
  (.getChars s 0 n cs 0)
  (areduce cs i v 0 (+ v (int (aget cs i)))))
=> 500

Обратите внимание на использование взаимодействия Java в Clojure для вызова getChars и использование areduce для очень быстрой итерации по массиву символов.

Вас также может заинтересовать эта реализация фильтра Блума Java, которую я нашел на Github: https://github.com/MagnusS/Java-BloomFilter . Реализация хеш-кода на первый взгляд выглядит нормально, но она использует массив байтов, который, как мне кажется, немного менее эффективен, чем использование символов, из-за необходимости иметь дело с накладными расходами кодирования символов.

Взгляните на реализацию фильтра Блума в Apache Cassandra. Он использует очень быстрый алгоритм MurmurHash3 и объединяет два хэша (или две части один и тот же хэш, начиная с обновления до MurmurHash3 вместо MurmurHash2) разными способами вычислить нужное количество хэшей.

Комбинаторный подход к генерации описан в этой статье.

и вот фрагмент исходного кода Cassandra:

    long[] hash = MurmurHash.hash3_x64_128(b, b.position(), b.remaining(), 0L);
    long hash1 = hash[0];
    long hash2 = hash[1];
    for (int i = 0; i < hashCount; ++i)
    {
        result[i] = Math.abs((hash1 + (long)i * hash2) % max);
    }

См. также Bloomfilter и Cassandra = Почему используется и почему хэшируется несколько раз?