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

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

10 голосов
/ 04 марта 2012

Я хочу создать фильтр Блума в Clojure, но я не очень хорошо знаю все библиотеки хеширования, которые могут быть доступны для языков на основе JVM.

Что я должен использовать для самой быстрой (в отличие от самой точной) реализации карты Блума в Clojure?

Ответы [ 2 ]

11 голосов
/ 04 марта 2012

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

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

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

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

3 голосов
/ 04 марта 2012

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

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

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

Код 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.На первый взгляд реализация хэш-кода выглядит нормально, но использует байтовый массив, который, я думаю, немного менее эффективен, чем использование символов, из-за необходимости иметь дело с накладными расходами кодировки символов.

...