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

Ответ 1

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

В строках Java уже есть одна хеш-функция, встроенная в которую вы можете использовать - String.hashCode() с возвратом 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

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

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

Ответ 2

Взгляните на реализацию фильтра Bloom в 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 = Почему и почему хешировали несколько раз?