Kỹ thuật băm nào sử dụng khi xây dựng bộ lọc nở trong clojure?

Question

Tôi muốn xây dựng một bộ lọc nở hoa trong Clojure nhưng tôi không có nhiều kiến ​​thức về tất cả các thư viện băm có thể có sẵn cho các ngôn ngữ dựa trên JVM.

Tôi nên sử dụng gì để triển khai bản đồ nở hoa nhanh nhất (trái ngược với chính xác nhất) trong Clojure?

Answer 1

Vì vậy, điều thú vị về bộ lọc nở là để hoạt động hiệu quả, chúng cần nhiều hàm băm.

Các chuỗi Java đã có một hàm băm được tích hợp sẵn mà bạn có thể sử dụng - String.hashCode() với trả về băm số nguyên 32 bit. Đó là một mã băm OK cho hầu hết các mục đích, và có thể điều này là đủ: nếu bạn phân vùng này thành 2 mã băm 16 bit riêng biệt, ví dụ như vậy có thể đủ tốt để bộ lọc nở của bạn hoạt động. Bạn có thể sẽ nhận được một vài va chạm nhưng đó là tốt - bộ lọc nở dự kiến ​​sẽ có một số va chạm.

Nếu không, có thể bạn sẽ muốn cuộn của riêng mình, trong trường hợp đó tôi khuyên bạn nên sử dụng String.getChars() để truy cập dữ liệu char thô, sau đó sử dụng để tính toán nhiều mã băm.

Clojure mã để giúp bạn bắt đầu (chỉ tổng giá trị ký tự):

(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 

Lưu ý việc sử dụng Java Clojure của interop gọi getChars, và việc sử dụng các areduce để cung cấp cho bạn một sự lặp lại rất nhanh qua mảng ký tự.

Việc triển khai bộ lọc nở hoa Java này tôi tìm thấy trên Github: https://github.com/MagnusS/Java-BloomFilter. Việc thực hiện hashcode trông OK ở cái nhìn đầu tiên nhưng nó sử dụng một mảng byte mà tôi nghĩ là một chút ít hiệu quả hơn bằng cách sử dụng ký tự vì sự cần thiết phải đối phó với các chi phí mã hóa ký tự.

Answer 2

Hãy xem triển khai Bộ lọc Bloom trong Apache Cassandra. Điều này sử dụng thuật toán MurmurHash3 rất nhanh và kết hợp hai băm (hoặc hai phần của cùng một băm, kể từ khi nâng cấp lên MurmurHash3 thay vì MurmurHash2) theo các cách khác nhau để tính số lượng băm mong muốn.

Cách tiếp cận thế hệ tổ hợp được mô tả trong this paper

và đây là một đoạn trích từ sourcecode 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); 
    } 

Xem thêm Bloomfilter and Cassandra = Why used and why hashed several times?