\u5728\u6b63\u5f0f\u8bb2\u89e3\u5e03\u9686\u8fc7\u6ee4\u5668\u4e4b\u524d\uff0c\u5148\u8ba9\u6211\u4eec\u770b\u770b\u8fd9\u4e2a\u4e1a\u52a1\u573a\u666f\uff1a<\/p>\n

Redis \u662f\u8f6f\u4ef6\u67b6\u6784\u4e2d\u5e38\u7528\u7684\u7ec4\u4ef6\uff0c\u6700\u5e38\u89c1\u7684\u7528\u6cd5\u662f\u5c06\u70ed\u70b9\u6570\u636e\u7f13\u5b58\u5230 Redis \u4e2d\uff0c\u4ee5\u51cf\u5c11\u6570\u636e\u5e93\u7684\u538b\u529b;\u67e5\u8be2\u8fc7\u7a0b\u4e2d\u6700\u5e38\u89c1\u7684\u7528\u6cd5\u662f\uff1a\u67e5\u8be2 Redis\uff0c\u5982\u679c\u80fd\u67e5\u8be2\u5230\u5219\u76f4\u63a5\u8fd4\u56de\uff0c\u5982\u679c Redis \u4e2d\u4e0d\u5b58\u5728\u5219\u7ee7\u7eed\u67e5\u8be2\u6570\u636e\u5e93\u3002<\/p>\n

\u8fd9\u79cd\u65b9\u5f0f\u53ef\u4ee5\u51cf\u5c11\u6570\u636e\u5e93\u7684\u8bbf\u95ee\u6b21\u6570\uff0c\u4f46\u662f\u201c\u5f53\u7f13\u5b58\u4e2d\u6ca1\u6709\uff0c\u5c31\u67e5\u8be2\u6570\u636e\u5e93\u201d\uff0c\u5728\u9ad8\u5e76\u53d1\u7684\u73af\u5883\u4e2d\u4f9d\u7136\u4f1a\u6709\u98ce\u9669\uff0c\u6bd4\u5982 90% \u7684\u8bf7\u6c42\u6570\u636e\u90fd\u4e0d\u5728\u7f13\u5b58\u4e2d\uff0c\u90a3\u4e48\u8fd9\u4e9b\u8bf7\u6c42\u5c31\u90fd\u4f1a\u843d\u5230\u6570\u636e\u5e93\u4e0a\uff0c\u8fd9\u5c31\u662f\u7f13\u5b58\u7a7f\u900f\u3002<\/p>\n

\u90a3\u4e48\u6709\u6ca1\u6709\u4ec0\u4e48\u529e\u6cd5\u89e3\u51b3\u8fd9\u4e2a\u95ee\u9898\u5462?\u8fd9\u5c31\u53ef\u4ee5\u4f7f\u7528\u3010\u5e03\u9686\u8fc7\u6ee4\u5668\u3011\u4e86\uff0c\u5b83\u53ef\u4ee5\u786e\u5b9a\u201c\u67d0\u9879\u6570\u636e\u80af\u5b9a\u4e0d\u5b58\u5728\u201d\u3002<\/p>\n

01.\u5e03\u9686\u8fc7\u6ee4\u5668\u7684\u6982\u5ff5<\/strong><\/div>\n
\u5e03\u9686\u8fc7\u6ee4\u5668\u662f\u4e00\u4e2a\u53eb\u201c\u5e03\u9686\u201d\u7684\u4eba\u63d0\u51fa\u7684\uff0c\u5b83\u672c\u8eab\u662f\u4e00\u4e2a\u5f88\u957f\u7684\u4e8c\u8fdb\u5236\u5411\u91cf(\u60f3\u8c61\u6210\u6570\u7ec4)\u548c\u4e00\u7cfb\u5217\u968f\u673a\u6620\u5c04\u51fd\u6570(\u60f3\u8c61\u6210\u591a\u4e2a Hash \u51fd\u6570)\uff0c\u4e8c\u8fdb\u5236\u5411\u91cf\u4e2d\u5b58\u653e\u7684\u4e0d\u662f0\uff0c\u5c31\u662f1(\u5728\u5b66\u4e60\u5e03\u9686\u8fc7\u6ee4\u5668\u4e4b\u524d\uff0c\u53ef\u4ee5\u5148\u4e86\u89e3 BitMap \u7b97\u6cd5\uff0c\u4fbf\u4e8e\u7406\u89e3)\u3002<\/p>\n
\u6bd4\u5982\u8981\u6839\u636e\u5ba2\u6237\u624b\u673a\u53f7\u505a\u4e3a\u6761\u4ef6\u67e5\u8be2\u5ba2\u6237\u4fe1\u606f\uff0c\u901a\u5e38\u4f1a\u628a\u624b\u673a\u53f7\u7801\u8bbe\u7f6e\u6210\u7f13\u5b58\u4e2d\u7684 Key\uff0c\u8ba9\u6211\u4eec\u8bbe\u7f6e\u4e00\u4e2a\u957f\u5ea6\u4e3a 16 \u7684\u5e03\u9686\u8fc7\u6ee4\u5668\u3002<\/p>\n
\u5e03\u9686\u8fc7\u6ee4\u5668\u521d\u59cb\u5316\u90fd\u662f 0;<\/p>\n
\u5bf9 13800000000 \u5206\u522b\u8fdb\u884c hash1()\u3001hash2()\u3001hash3() \u8fd0\u7b97\uff0c\u5f97\u5230\u4e09\u4e2a\u7ed3\u679c 5\u30019\u300112\uff0c\u628a\u5bf9\u5e94\u4f4d\u7f6e\u8bbe\u7f6e\u6210 1;
\n $\"\"$
\n\u5bf9 18900000000 \u5206\u522b\u8fdb\u884c hash1()\u3001hash2()\u3001hash3() \u8fd0\u7b97\uff0c\u5f97\u5230\u4e09\u4e2a\u7ed3\u679c 2\u30018\u300112\uff0c\u628a\u5bf9\u5e94\u4f4d\u7f6e\u8bbe\u7f6e\u6210 1\uff0c\u73b0\u5728 2\u30015\u30018\u30019\u300112 \u90fd\u662f 1\uff0c\u5176\u4f59\u5143\u7d20\u90fd\u662f 0;
\n $\"\"$
\n\u5982\u679c\u6211\u4eec\u60f3\u8981\u9a8c\u8bc1\u67d0\u4e2a\u7535\u8bdd\u53f7\u7801\u662f\u5426\u5b58\u5728\uff0c\u9700\u8981\u600e\u4e48\u505a\u5462?<\/p>\n
\u5bf9 13700000000 \u5206\u522b\u8fdb\u884c hash1()\u3001hash2()\u3001hash3() \u8fd0\u7b97\uff0c\u5f97\u5230\u4e09\u4e2a\u7ed3\u679c 1\u30019\u300113\uff0c\u7136\u540e\u53bb\u5224\u65ad\u7b2c 1\u30019\u300113 \u4f4d\u4e0a\u7684\u503c\u662f 0 \u8fd8\u662f 1\uff0c\u5982\u679c\u4e0d\u5168\u662f 1 \u7684\u8bdd\uff0c\u5c31\u8bf4\u660e 13700000000 \u4e0d\u5728\u8fd9\u4e2a\u5e03\u9686\u8fc7\u6ee4\u5668\u4e0a;\u8fd9\u5c31\u786e\u5b9a\u4e86\u201c\u67d0\u9879\u6570\u636e\u80af\u5b9a\u4e0d\u5b58\u5728\u201d\u3002
\n $\"\"$
\n\u5f53\u7136\u6211\u4eec\u4e5f\u53ef\u4ee5\u770b\u51fa\u6765\u5e03\u9686\u8fc7\u6ee4\u5668\u6709\u4e2a\u95ee\u9898\uff0c\u90a3\u5c31\u662f\u4e0d\u80fd\u4fdd\u8bc1\u6570\u636e\u80af\u5b9a\u5b58\u5728\uff0c\u6bd4\u5982\u5bf9 18000000000 \u5206\u522b\u8fdb\u884c hash1()\u3001hash2()\u3001hash3() \u8fd0\u7b97\uff0c\u5f97\u5230\u7684\u7ed3\u679c\u662f 5\u30018\u30019\uff0c\u6070\u597d\u8fd9\u4e09\u4f4d\u90fd\u662f 1\uff0c\u4f46\u5b9e\u9645\u4e0a\u8fd9\u6761\u6570\u636e\u5e76\u4e0d\u5b58\u5728\uff0c\u6240\u4ee5\u5e03\u9686\u8fc7\u6ee4\u5668\u6709\u4e00\u5b9a\u7684\u8bef\u5224\u7387;<\/p>\n
\u800c\u4e14\u56e0\u4e3a\u591a\u4e2a\u6570\u636e\u7ecf\u8fc7\u8fd0\u7b97\u540e\u53ef\u80fd\u4f1a\u6620\u5c04\u5230\u540c\u4e00\u4e2a\u4f4d\u7f6e(138 \u548c 189 \u7684\u8fd0\u7b97\u7ed3\u679c\u90fd\u6709 12)\uff0c\u6240\u4ee5\u5e03\u9686\u8fc7\u6ee4\u5668\u5f88\u96be\u505a\u5230\u5220\u9664\uff0c\u9664\u975e\u8981\u4e3a\u6bcf\u4e00\u4f4d\u589e\u52a0\u4e00\u4e2a\u8ba1\u6570\u5668\uff0c\u5220\u9664\u7684\u65f6\u5019\u9700\u8981\u7ed9\u8ba1\u6570\u5668\u51cf 1\uff0c\u76f4\u5230\u8ba1\u6570\u5668\u4e3a 0 \u65f6\uff0c\u624d\u5c06\u5e03\u9686\u8fc7\u6ee4\u5668\u5bf9\u5e94\u4f4d\u7f6e\u4fee\u6539\u6210 0\u3002<\/p>\n
02.\u7279\u70b9\u603b\u7ed3<\/strong><\/div>\n
\u53ef\u4ee5\u786e\u5b9a\u4e00\u4e2a\u5143\u7d20\u80af\u5b9a\u4e0d\u5b58\u5728\uff0c\u4f46\u662f\u4e0d\u80fd\u786e\u5b9a\u4e00\u4e2a\u5143\u7d20\u80af\u5b9a\u5b58\u5728;<\/p>\n
\u4e8c\u8fdb\u5236\u5411\u91cf\u8d8a\u957f\uff0c\u6620\u5c04\u51fd\u6570\u8d8a\u591a\uff0c\u8bef\u5224\u7387\u8d8a\u4f4e;\u5982\u679c\u63d0\u524d\u53ef\u4ee5\u786e\u5b9a\u8bef\u5224\u7387\uff0c\u4e5f\u53ef\u4ee5\u53cd\u63a8\u51fa\u6765\u5e03\u9686\u8fc7\u6ee4\u5668\u7684\u957f\u5ea6;<\/p>\n
\u53ef\u4ee5\u6dfb\u52a0\u5143\u7d20\uff0c\u4f46\u662f\u4e0d\u80fd\u5220\u9664\u5143\u7d20(\u9664\u975e\u589e\u52a0\u8ba1\u6570\u5668);<\/p>\n
\u5728\u5b58\u50a8\u7a7a\u95f4\u548c\u63d2\u5165\u67e5\u8be2\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u90fd\u6709\u5de8\u5927\u4f18\u52bf\u3002<\/p>\n
\u56de\u5230\u672c\u6587\u5f00\u5934\u7684\u90a3\u4e2a\u4e1a\u52a1\u573a\u666f\uff0c\u4e3a\u4e86\u9632\u6b62\u7f13\u5b58\u7a7f\u900f\uff0c\u53ef\u4ee5\u4f7f\u7528\u5e03\u9686\u8fc7\u6ee4\u5668\u8fc7\u6ee4\u6389\u80af\u5b9a\u4e0d\u5b58\u5728\u7684\u6570\u636e\uff0c\u8bef\u5224\u7684\u8bf7\u6c42\u867d\u7136\u8fd8\u662f\u4f1a\u653e\u5230\u5230\u6570\u636e\u5e93\uff0c\u4f46\u5df2\u7ecf\u6781\u5927\u5730\u51cf\u5c11\u4e86\u7a7f\u900f\u7684\u6570\u91cf\u3002<\/p>\n
03.\u624b\u5199\u4e00\u4e2a\u5e03\u9686\u8fc7\u6ee4\u5668<\/strong><\/div>\n
Code \u4e0d\u662f\u76ee\u7684\uff0cCoding \u7684\u8fc7\u7a0b\u662f\u4e3a\u4e86\u52a0\u6df1\u7406\u89e3\u3002<\/p>\n
\u9996\u5148\u6211\u4eec\u9700\u8981\u5b9a\u4e49\u4e00\u4e2a bitmap\uff0c\u5728 JDK \u4e2d\uff0c\u5df2\u7ecf\u6709\u5bf9\u5e94\u5b9e\u73b0\u7684\u6570\u636e\u7ed3\u6784\u7c7b
\njava.util.BitSet\uff1a<\/p>\n
\/\/\u8bbe\u7f6e\u4e00\u4e2a\u5e03\u9686\u8fc7\u6ee4\u5668 \r\nprivate int DEFAULT_SIZE = 1 << 30; \r\n \r\nprivate BitSet bitset ;\r\n<\/pre>\n
\u6211\u4eec\u8fd8\u9700\u8981\u4e00\u7ec4\u6620\u5c04\u51fd\u6570\uff0c\u8fd9\u91cc\u53ef\u4ee5\u4f7f\u7528\u52a0\u6cd5 hash \u51fd\u6570\uff0c\u8bbe\u7f6e 6 \u4e2a\u8d28\u6570\uff0c\u5bf9\u5e94 6 \u4e2a\u4e0d\u540c\u7684 hash \u51fd\u6570\uff1a<\/p>\n
\/\/\u5b9a\u4e49\u4e00\u4e2a\u8d28\u6570\u6570\u7ec4\uff0c\u957f\u5ea6\u4e3a6\uff0c\u53ef\u4ee5\u751f\u62106\u4e2ahash\u51fd\u6570\uff0c\u7528\u4e8e\u968f\u673a\u6620\u5c04 \r\nprivate int[] seeds = {3, 7, 13, 31, 37, 61}; \r\n \r\nprivate HashFunction[] functions = new HashFunction[seeds.length]; \r\n<\/pre>\n
\u5728\u6784\u9020\u51fd\u6570\u4e2d\u8fdb\u884c\u521d\u59cb\u5316\uff0c\u8bbe\u7f6e BitSet \u7684\u957f\u5ea6\uff0c\u751f\u6210\u6620\u5c04\u51fd\u6570\uff1a<\/p>\n
\/** \r\n* \u521d\u59cb\u5316 \r\n*\/ \r\npublic BloomFilter() { \r\n bitset = new BitSet(DEFAULT_SIZE); \r\n \r\n for (int i = 0; i < seeds.length; i++) { \r\n functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]); \r\n } \r\n} \r\n<\/pre>\n
\u589e\u52a0\u5143\u7d20\u7684\u65f6\u5019\uff0c\u5bf9\u5165\u53c2\u8fdb\u884c 6 \u6b21 hash \u8fd0\u7b97\uff0c\u5e76\u5c06\u7ed3\u679c\u5bf9\u5e94\u7684\u4f4d\u7f6e\u4fee\u6539\u6210 1(BitSet \u5bf9\u5e94\u7684\u4f4d\u7f6e\u4fee\u6539\u6210 true)\uff1a<\/p>\n
\/** \r\n* \u6dfb\u52a0\u4e00\u4e2a\u5143\u7d20\uff0c\u5f97\u5230hash\u8fd0\u7b97\u540e\u7684\u7ed3\u679c\uff0c\u5c06\u5bf9\u5e94\u7684\u4f4d\u7f6e\u4fee\u6539\u62101\uff08true\uff09 \r\n* @param value \r\n*\/ \r\npublic void add(String value) { \r\n if (value != null) { \r\n for (HashFunction f : functions) { \r\n bitset.set(f.hash(value), true); \r\n } \r\n } \r\n} \r\n<\/pre>\n
\u5224\u65ad\u5143\u7d20\u662f\u5426\u5728\u5e03\u9686\u7ba1\u7406\u5668\u4e2d\uff0c\u9700\u8981\u5bf9\u5165\u53c2\u8fdb\u884c 6 \u6b21 hash \u8fd0\u7b97\uff0c\u518d\u67e5\u770b\u7ed3\u679c\u5bf9\u5e94\u7684\u4f4d\u7f6e\u4e0a\u662f 0 \u8fd8\u662f 1(true or false)\uff0c\u5982\u679c\u5176\u4e2d\u4e00\u4f4d\u662f 0\uff0c\u8868\u793a\u6570\u636e\u80af\u5b9a\u4e0d\u5b58\u5728\uff0c\u5982\u679c\u90fd\u662f 1\uff0c\u8868\u793a\u6570\u636e(\u5927\u6982\u7387)\u53ef\u80fd\u5b58\u5728\u3002<\/p>\n
\/** \r\n* \u5224\u65ad\u5143\u7d20\u662f\u5426\u5728\u5e03\u9686\u8fc7\u6ee4\u5668\u4e2d \r\n* @param value \r\n* @return \r\n*\/ \r\npublic boolean contains(String value) { \r\n if (value == null) { \r\n return false; \r\n } \r\n \r\n for (HashFunction f : functions) { \r\n if(!bitset.get(f.hash(value))){ \r\n \/\/\u4e00\u4e2a\u4f4d\u7f6e\u4e0a\u4e0d\u4e3a1\uff08true\uff09\uff0c\u5c31\u8bc1\u660e\u4e0d\u5b58\u5728\uff0c\u76f4\u63a5\u8fd4\u56defalse \r\n return false; \r\n } \r\n } \r\n \r\n return true; \r\n} \r\n<\/pre>\n
04.Guava \u4e2d\u7684 BloomFilter<\/strong><\/div>\n
\u5df2\u7ecf\u6709\u5f88\u591a\u5f00\u6e90\u6846\u67b6\u5e2e\u6211\u4eec\u5b9e\u73b0\u4e86\u5e03\u9686\u7ba1\u7406\u5668\uff0c\u6bd4\u5982 Google \u51fa\u54c1\u7684 Guava \u5de5\u5177\u5e93\uff0c\u5176\u4e2d\u5c31\u6709\u5f00\u7bb1\u5373\u7528\u7684\u5e03\u9686\u8fc7\u6ee4\u5668;<\/p>\n
public class BloomFilterTest { \r\n public static void main(String[] args){ \r\n int size = 1000000; \r\n \/\/\u5e03\u9686\u8fc7\u6ee4\u5668 \r\n BloomFilter bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, 0.001); \r\n \r\n for (int i = 0; i < size; i++) { \r\n bloomFilter.put(i); \r\n } \r\n \r\n List list = new ArrayList(1000); \r\n for (int i = size + 1; i < size + 10000; i++) { \r\n if (bloomFilter.mightContain(i)) { \r\n list.add(i); \r\n } \r\n } \r\n System.out.println(\"\u8bef\u5224\u6570\u91cf\uff1a\" + list.size()); \r\n } \r\n} \r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
\u5728\u6b63\u5f0f\u8bb2\u89e3\u5e03\u9686\u8fc7\u6ee4\u5668\u4e4b\u524d\uff0c\u5148\u8ba9\u6211\u4eec\u770b\u770b\u8fd9\u4e2a\u4e1a\u52a1\u573a\u666f\uff1a Redis \u662f\u8f6f\u4ef6\u67b6\u6784\u4e2d\u5e38\u7528\u7684\u7ec4\u4ef6\uff0c\u6700\u5e38\u89c1\u7684\u7528\u6cd5\u662f\u5c06\u70ed\u70b9 […]<\/p>\n","protected":false},"author":1898,"featured_media":199942,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[55],"tags":[594],"class_list":["post-199934","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-thread","tag-594"],"acf":[],"_links":{"self":[{"href":"https:\/\/lrxjmw.cn\/wp-json\/wp\/v2\/posts\/199934","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lrxjmw.cn\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lrxjmw.cn\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lrxjmw.cn\/wp-json\/wp\/v2\/users\/1898"}],"replies":[{"embeddable":true,"href":"https:\/\/lrxjmw.cn\/wp-json\/wp\/v2\/comments?post=199934"}],"version-history":[{"count":4,"href":"https:\/\/lrxjmw.cn\/wp-json\/wp\/v2\/posts\/199934\/revisions"}],"predecessor-version":[{"id":199941,"href":"https:\/\/lrxjmw.cn\/wp-json\/wp\/v2\/posts\/199934\/revisions\/199941"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/lrxjmw.cn\/wp-json\/wp\/v2\/media\/199942"}],"wp:attachment":[{"href":"https:\/\/lrxjmw.cn\/wp-json\/wp\/v2\/media?parent=199934"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lrxjmw.cn\/wp-json\/wp\/v2\/categories?post=199934"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lrxjmw.cn\/wp-json\/wp\/v2\/tags?post=199934"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}