{"id":1211,"date":"2018-05-03T23:43:33","date_gmt":"2018-05-03T15:43:33","guid":{"rendered":"https:\/\/damogame.cn:15443\/wordpress\/?p=1211"},"modified":"2018-05-03T23:43:33","modified_gmt":"2018-05-03T15:43:33","slug":"%e5%b8%83%e9%9a%86%e8%bf%87%e6%bb%a4%e5%99%a8bloom-filter%e8%af%a6%e8%a7%a3","status":"publish","type":"post","link":"https:\/\/i007.cc\/wordpress\/archives\/1211","title":{"rendered":"\u5e03\u9686\u8fc7\u6ee4\u5668(Bloom Filter)\u8be6\u89e3"},"content":{"rendered":"<h2><a id=\"cb_post_title_url\" href=\"http:\/\/www.cnblogs.com\/liyulong1982\/p\/6013002.html\">\u5e03\u9686\u8fc7\u6ee4\u5668(Bloom Filter)\u8be6\u89e3<\/a><\/h2>\n<div class=\"postbody\">\n<div id=\"cnblogs_post_body\" class=\"blogpost-body\">\n<p>\u76f4\u89c2\u7684\u8bf4\uff0cbloom\u7b97\u6cd5\u7c7b\u4f3c\u4e00\u4e2ahash set\uff0c\u7528\u6765\u5224\u65ad\u67d0\u4e2a\u5143\u7d20\uff08key\uff09\u662f\u5426\u5728\u67d0\u4e2a\u96c6\u5408\u4e2d\u3002<br \/>\n\u548c\u4e00\u822c\u7684hash set\u4e0d\u540c\u7684\u662f\uff0c\u8fd9\u4e2a\u7b97\u6cd5\u65e0\u9700\u5b58\u50a8key\u7684\u503c\uff0c\u5bf9\u4e8e\u6bcf\u4e2akey\uff0c\u53ea\u9700\u8981k\u4e2a\u6bd4\u7279\u4f4d\uff0c\u6bcf\u4e2a\u5b58\u50a8\u4e00\u4e2a\u6807\u5fd7\uff0c\u7528\u6765\u5224\u65adkey\u662f\u5426\u5728\u96c6\u5408\u4e2d\u3002<\/p>\n<p>\u7b97\u6cd5\uff1a<br \/>\n1. \u9996\u5148\u9700\u8981k\u4e2ahash\u51fd\u6570\uff0c\u6bcf\u4e2a\u51fd\u6570\u53ef\u4ee5\u628akey\u6563\u5217\u6210\u4e3a1\u4e2a\u6574\u6570<br \/>\n2. \u521d\u59cb\u5316\u65f6\uff0c\u9700\u8981\u4e00\u4e2a\u957f\u5ea6\u4e3an\u6bd4\u7279\u7684\u6570\u7ec4\uff0c\u6bcf\u4e2a\u6bd4\u7279\u4f4d\u521d\u59cb\u5316\u4e3a0<br \/>\n3. \u67d0\u4e2akey\u52a0\u5165\u96c6\u5408\u65f6\uff0c\u7528k\u4e2ahash\u51fd\u6570\u8ba1\u7b97\u51fak\u4e2a\u6563\u5217\u503c\uff0c\u5e76\u628a\u6570\u7ec4\u4e2d\u5bf9\u5e94\u7684\u6bd4\u7279\u4f4d\u7f6e\u4e3a1<br \/>\n4. \u5224\u65ad\u67d0\u4e2akey\u662f\u5426\u5728\u96c6\u5408\u65f6\uff0c\u7528k\u4e2ahash\u51fd\u6570\u8ba1\u7b97\u51fak\u4e2a\u6563\u5217\u503c\uff0c\u5e76\u67e5\u8be2\u6570\u7ec4\u4e2d\u5bf9\u5e94\u7684\u6bd4\u7279\u4f4d\uff0c\u5982\u679c\u6240\u6709\u7684\u6bd4\u7279\u4f4d\u90fd\u662f1\uff0c\u8ba4\u4e3a\u5728\u96c6\u5408\u4e2d\u3002<\/p>\n<p>\u4f18\u70b9\uff1a\u4e0d\u9700\u8981\u5b58\u50a8key\uff0c\u8282\u7701\u7a7a\u95f4<\/p>\n<p>\u7f3a\u70b9\uff1a<br \/>\n1. \u7b97\u6cd5\u5224\u65adkey\u5728\u96c6\u5408\u4e2d\u65f6\uff0c\u6709\u4e00\u5b9a\u7684\u6982\u7387key\u5176\u5b9e\u4e0d\u5728\u96c6\u5408\u4e2d<br \/>\n2. \u65e0\u6cd5\u5220\u9664<\/p>\n<p>\u5178\u578b\u7684\u5e94\u7528\u573a\u666f\uff1a<br \/>\n\u67d0\u4e9b\u5b58\u50a8\u7cfb\u7edf\u7684\u8bbe\u8ba1\u4e2d\uff0c\u4f1a\u5b58\u5728\u7a7a\u67e5\u8be2\u7f3a\u9677\uff1a\u5f53\u67e5\u8be2\u4e00\u4e2a\u4e0d\u5b58\u5728\u7684key\u65f6\uff0c\u9700\u8981\u8bbf\u95ee\u6162\u8bbe\u5907\uff0c\u5bfc\u81f4\u6548\u7387\u4f4e\u4e0b\u3002<br \/>\n\u6bd4\u5982\u4e00\u4e2a\u524d\u7aef\u9875\u9762\u7684\u7f13\u5b58\u7cfb\u7edf\uff0c\u53ef\u80fd\u8fd9\u6837\u8bbe\u8ba1\uff1a\u5148\u67e5\u8be2\u67d0\u4e2a\u9875\u9762\u5728\u672c\u5730\u662f\u5426\u5b58\u5728\uff0c\u5982\u679c\u5b58\u5728\u5c31\u76f4\u63a5\u8fd4\u56de\uff0c\u5982\u679c\u4e0d\u5b58\u5728\uff0c\u5c31\u4ece\u540e\u7aef\u83b7\u53d6\u3002\u4f46\u662f\u5f53\u9891\u7e41\u4ece\u7f13\u5b58\u7cfb\u7edf\u67e5\u8be2\u4e00\u4e2a\u9875\u9762\u65f6\uff0c\u7f13\u5b58\u7cfb\u7edf\u5c06\u4f1a\u9891\u7e41\u8bf7\u6c42\u540e\u7aef\uff0c\u628a\u538b\u529b\u5bfc\u5165\u540e\u7aef\u3002<\/p>\n<p>\u8fd9\u662f\u53ea\u8981\u589e\u52a0\u4e00\u4e2abloom\u7b97\u6cd5\u7684\u670d\u52a1\uff0c\u540e\u7aef\u63d2\u5165\u4e00\u4e2akey\u65f6\uff0c\u5728\u8fd9\u4e2a\u670d\u52a1\u4e2d\u8bbe\u7f6e\u4e00\u6b21<br \/>\n\u9700\u8981\u67e5\u8be2\u540e\u7aef\u65f6\uff0c\u5148\u5224\u65adkey\u5728\u540e\u7aef\u662f\u5426\u5b58\u5728\uff0c\u8fd9\u6837\u5c31\u80fd\u907f\u514d\u540e\u7aef\u7684\u538b\u529b\u3002<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p><small><img decoding=\"async\" src=\"https:\/\/pic002.cnblogs.com\/images\/2012\/274814\/2012071317402283.png\" alt=\"\" \/><\/small><\/p>\n<div class=\"entry\">\n<div id=\"cnblogs_post_body\">\n<p><strong>\u00a0<\/strong><\/p>\n<p><strong>\u5e03\u9686\u8fc7\u6ee4\u5668\uff3b1\uff3d<\/strong>\uff08Bloom Filter\uff09\u662f\u7531\u5e03\u9686\uff08<span class=\"new\">Burton Howard Bloom\uff09\u57281970\u5e74\u63d0\u51fa\u7684\u3002\u5b83\u5b9e\u9645\u4e0a\u662f\u7531\u4e00\u4e2a\u5f88\u957f\u7684\u4e8c\u8fdb\u5236\u5411\u91cf\u548c\u4e00\u7cfb\u5217\u968f\u673a\u6620\u5c04\u51fd\u6570\u7ec4\u6210\uff0c\u5e03\u9686\u8fc7\u6ee4\u5668\u53ef\u4ee5\u7528\u4e8e\u68c0\u7d22\u4e00\u4e2a\u5143\u7d20\u662f\u5426\u5728\u4e00\u4e2a\u96c6\u5408\u4e2d\u3002\u5b83\u7684\u4f18\u70b9\u662f\u7a7a\u95f4\u6548\u7387\u548c\u67e5\u8be2\u65f6\u95f4\u90fd\u8fdc\u8fdc\u8d85\u8fc7\u4e00\u822c\u7684\u7b97\u6cd5\uff0c\u7f3a\u70b9\u662f\u6709\u4e00\u5b9a\u7684\u8bef\u8bc6\u522b\u7387\uff08\u5047\u6b63\u4f8bFalse positives\uff0c\u5373Bloom Filter\u62a5\u544a\u67d0\u4e00\u5143\u7d20\u5b58\u5728\u4e8e\u67d0\u96c6\u5408\u4e2d\uff0c\u4f46\u662f\u5b9e\u9645\u4e0a\u8be5\u5143\u7d20\u5e76\u4e0d\u5728\u96c6\u5408\u4e2d\uff09\u548c\u5220\u9664\u56f0\u96be\uff0c\u4f46\u662f\u6ca1\u6709\u8bc6\u522b\u9519\u8bef\u7684\u60c5\u5f62\uff08\u5373\u5047\u53cd\u4f8bFalse negatives\uff0c\u5982\u679c\u67d0\u4e2a\u5143\u7d20\u786e\u5b9e\u6ca1\u6709\u5728\u8be5\u96c6\u5408\u4e2d\uff0c\u90a3\u4e48Bloom Filter \u662f\u4e0d\u4f1a\u62a5\u544a\u8be5\u5143\u7d20\u5b58\u5728\u4e8e\u96c6\u5408\u4e2d\u7684\uff0c\u6240\u4ee5\u4e0d\u4f1a\u6f0f\u62a5\uff09\u3002<\/span><\/p>\n<p>\u5728\u65e5\u5e38\u751f\u6d3b\u4e2d\uff0c\u5305\u62ec\u5728\u8bbe\u8ba1\u8ba1\u7b97\u673a\u8f6f\u4ef6\u65f6\uff0c\u6211\u4eec\u7ecf\u5e38\u8981\u5224\u65ad\u4e00\u4e2a\u5143\u7d20\u662f\u5426\u5728\u4e00\u4e2a\u96c6\u5408\u4e2d\u3002\u6bd4\u5982\u5728\u5b57\u5904\u7406\u8f6f\u4ef6\u4e2d\uff0c\u9700\u8981\u68c0\u67e5\u4e00\u4e2a\u82f1\u8bed\u5355\u8bcd\u662f\u5426\u62fc\u5199\u6b63\u786e\uff08\u4e5f\u5c31\u662f\u8981\u5224\u65ad \u5b83\u662f\u5426\u5728\u5df2\u77e5\u7684\u5b57\u5178\u4e2d\uff09\uff1b\u5728 FBI\uff0c\u4e00\u4e2a\u5acc\u7591\u4eba\u7684\u540d\u5b57\u662f\u5426\u5df2\u7ecf\u5728\u5acc\u7591\u540d\u5355\u4e0a\uff1b\u5728\u7f51\u7edc\u722c\u866b\u91cc\uff0c\u4e00\u4e2a\u7f51\u5740\u662f\u5426\u88ab\u8bbf\u95ee\u8fc7\u7b49\u7b49\u3002\u6700\u76f4\u63a5\u7684\u65b9\u6cd5\u5c31\u662f\u5c06\u96c6\u5408\u4e2d\u5168\u90e8\u7684\u5143\u7d20\u5b58\u5728\u8ba1\u7b97\u673a\u4e2d\uff0c\u9047\u5230\u4e00\u4e2a\u65b0 \u5143\u7d20\u65f6\uff0c\u5c06\u5b83\u548c\u96c6\u5408\u4e2d\u7684\u5143\u7d20\u76f4\u63a5\u6bd4\u8f83\u5373\u53ef\u3002\u4e00\u822c\u6765\u8bb2\uff0c\u8ba1\u7b97\u673a\u4e2d\u7684\u96c6\u5408\u662f\u7528\u54c8\u5e0c\u8868\uff08hash table\uff09\u6765\u5b58\u50a8\u7684\u3002\u5b83\u7684\u597d\u5904\u662f\u5feb\u901f\u51c6\u786e\uff0c\u7f3a\u70b9\u662f\u8d39\u5b58\u50a8\u7a7a\u95f4\u3002\u5f53\u96c6\u5408\u6bd4\u8f83\u5c0f\u65f6\uff0c\u8fd9\u4e2a\u95ee\u9898\u4e0d\u663e\u8457\uff0c\u4f46\u662f\u5f53\u96c6\u5408\u5de8\u5927\u65f6\uff0c\u54c8\u5e0c\u8868\u5b58\u50a8\u6548\u7387\u4f4e\u7684\u95ee\u9898\u5c31\u663e\u73b0\u51fa\u6765 \u4e86\u3002\u6bd4\u5982\u8bf4\uff0c\u4e00\u4e2a\u8c61 Yahoo,Hotmail \u548c Gmai \u90a3\u6837\u7684\u516c\u4f17\u7535\u5b50\u90ae\u4ef6\uff08email\uff09\u63d0\u4f9b\u5546\uff0c\u603b\u662f\u9700\u8981\u8fc7\u6ee4\u6765\u81ea\u53d1\u9001\u5783\u573e\u90ae\u4ef6\u7684\u4eba\uff08spamer\uff09\u7684\u5783\u573e\u90ae\u4ef6\u3002\u4e00\u4e2a\u529e\u6cd5\u5c31\u662f\u8bb0\u5f55\u4e0b\u90a3\u4e9b\u53d1\u5783\u573e\u90ae\u4ef6\u7684 email \u5730\u5740\u3002\u7531\u4e8e\u90a3\u4e9b\u53d1\u9001\u8005\u4e0d\u505c\u5730\u5728\u6ce8\u518c\u65b0\u7684\u5730\u5740\uff0c\u5168\u4e16\u754c\u5c11\u8bf4\u4e5f\u6709\u51e0\u5341\u4ebf\u4e2a\u53d1\u5783\u573e\u90ae\u4ef6\u7684\u5730\u5740\uff0c\u5c06\u4ed6\u4eec\u90fd\u5b58\u8d77\u6765\u5219\u9700\u8981\u5927\u91cf\u7684\u7f51\u7edc\u670d\u52a1\u5668\u3002\u5982\u679c\u7528\u54c8\u5e0c\u8868\uff0c\u6bcf\u5b58\u50a8\u4e00\u4ebf \u4e2a email \u5730\u5740\uff0c \u5c31\u9700\u8981 1.6GB \u7684\u5185\u5b58\uff08\u7528\u54c8\u5e0c\u8868\u5b9e\u73b0\u7684\u5177\u4f53\u529e\u6cd5\u662f\u5c06\u6bcf\u4e00\u4e2a email \u5730\u5740\u5bf9\u5e94\u6210\u4e00\u4e2a\u516b\u5b57\u8282\u7684\u4fe1\u606f\u6307\u7eb9\uff08\u8be6\u89c1\uff1a<a href=\"http:\/\/googlechinablog.com\/2006\/08\/blog-post.html\" target=\"_blank\" rel=\"noopener\">googlechinablog.com\/2006\/08\/blog-post.html\uff09<\/a>\uff0c \u7136\u540e\u5c06\u8fd9\u4e9b\u4fe1\u606f\u6307\u7eb9\u5b58\u5165\u54c8\u5e0c\u8868\uff0c\u7531\u4e8e\u54c8\u5e0c\u8868\u7684\u5b58\u50a8\u6548\u7387\u4e00\u822c\u53ea\u6709 50%\uff0c\u56e0\u6b64\u4e00\u4e2a email \u5730\u5740\u9700\u8981\u5360\u7528\u5341\u516d\u4e2a\u5b57\u8282\u3002\u4e00\u4ebf\u4e2a\u5730\u5740\u5927\u7ea6\u8981 1.6GB\uff0c \u5373\u5341\u516d\u4ebf\u5b57\u8282\u7684\u5185\u5b58\uff09\u3002\u56e0\u6b64\u5b58\u8d2e\u51e0\u5341\u4ebf\u4e2a\u90ae\u4ef6\u5730\u5740\u53ef\u80fd\u9700\u8981\u4e0a\u767e GB \u7684\u5185\u5b58\u3002\u9664\u975e\u662f\u8d85\u7ea7\u8ba1\u7b97\u673a\uff0c\u4e00\u822c\u670d\u52a1\u5668\u662f\u65e0\u6cd5\u5b58\u50a8\u7684\uff3b2\uff3d\u3002\uff08\u8be5\u6bb5\u5f15\u7528\u8c37\u6b4c\u6570\u5b66\u4e4b\u7f8e\uff1ahttp:\/\/www.google.com.hk\/ggblog\/googlechinablog\/2007\/07\/bloom-filter_7469.html\uff09<\/p>\n<h3><span id=\".E5.9F.BA.E6.9C.AC.E6.A6.82.E5.BF.B5\" class=\"mw-headline\">\u57fa\u672c\u6982\u5ff5<\/span><\/h3>\n<p>\u5982\u679c\u60f3\u5224\u65ad\u4e00\u4e2a\u5143\u7d20\u662f\u4e0d\u662f\u5728\u4e00\u4e2a\u96c6\u5408\u91cc\uff0c\u4e00\u822c\u60f3\u5230\u7684\u662f\u5c06\u6240\u6709\u5143\u7d20\u4fdd\u5b58\u8d77\u6765\uff0c\u7136\u540e\u901a\u8fc7\u6bd4\u8f83\u786e\u5b9a\u3002\u94fe\u8868\uff0c\u6811\u7b49\u7b49\u6570\u636e\u7ed3\u6784\u90fd\u662f\u8fd9\u79cd\u601d\u8def. \u4f46\u662f\u968f\u7740\u96c6\u5408\u4e2d\u5143\u7d20\u7684\u589e\u52a0\uff0c\u6211\u4eec\u9700\u8981\u7684\u5b58\u50a8\u7a7a\u95f4\u8d8a\u6765\u8d8a\u5927\uff0c\u68c0\u7d22\u901f\u5ea6\u4e5f\u8d8a\u6765\u8d8a\u6162\u3002\u4e0d\u8fc7\u4e16\u754c\u4e0a\u8fd8\u6709\u4e00\u79cd\u53eb\u4f5c<span class=\"mw-redirect\">\u6563\u5217\u8868\uff08\u53c8\u53eb\u54c8\u5e0c\u8868\uff0cHash table\uff09\u7684\u6570\u636e\u7ed3\u6784\u3002\u5b83\u53ef\u4ee5\u901a\u8fc7\u4e00\u4e2aHash\u51fd\u6570\u5c06\u4e00\u4e2a\u5143\u7d20\u6620\u5c04\u6210\u4e00\u4e2a\u4f4d\u9635\u5217\uff08Bit Array\uff09\u4e2d\u7684\u4e00\u4e2a\u70b9\u3002\u8fd9\u6837\u4e00\u6765\uff0c\u6211\u4eec\u53ea\u8981\u770b\u770b\u8fd9\u4e2a\u70b9\u662f\u4e0d\u662f 1 \u5c31\u77e5\u9053\u53ef\u4ee5\u96c6\u5408\u4e2d\u6709\u6ca1\u6709\u5b83\u4e86\u3002\u8fd9\u5c31\u662f\u5e03\u9686\u8fc7\u6ee4\u5668\u7684\u57fa\u672c\u601d\u60f3\u3002<\/span><\/p>\n<p>Hash\u9762\u4e34\u7684\u95ee\u9898\u5c31\u662f\u51b2\u7a81\u3002\u5047\u8bbe Hash \u51fd\u6570\u662f\u826f\u597d\u7684\uff0c\u5982\u679c\u6211\u4eec\u7684\u4f4d\u9635\u5217\u957f\u5ea6\u4e3a m \u4e2a\u70b9\uff0c\u90a3\u4e48\u5982\u679c\u6211\u4eec\u60f3\u5c06\u51b2\u7a81\u7387\u964d\u4f4e\u5230\u4f8b\u5982 1%, \u8fd9\u4e2a\u6563\u5217\u8868\u5c31\u53ea\u80fd\u5bb9\u7eb3 m\/100 \u4e2a\u5143\u7d20\u3002\u663e\u7136\u8fd9\u5c31\u4e0d\u53eb\u7a7a\u95f4\u6709\u6548\u4e86\uff08Space-efficient\uff09\u3002\u89e3\u51b3\u65b9\u6cd5\u4e5f\u7b80\u5355\uff0c\u5c31\u662f\u4f7f\u7528\u591a\u4e2a Hash\uff0c\u5982\u679c\u5b83\u4eec\u6709\u4e00\u4e2a\u8bf4\u5143\u7d20\u4e0d\u5728\u96c6\u5408\u4e2d\uff0c\u90a3\u80af\u5b9a\u5c31\u4e0d\u5728\u3002\u5982\u679c\u5b83\u4eec\u90fd\u8bf4\u5728\uff0c\u867d\u7136\u4e5f\u6709\u4e00\u5b9a\u53ef\u80fd\u6027\u5b83\u4eec\u5728\u8bf4\u8c0e\uff0c\u4e0d\u8fc7\u76f4\u89c9\u4e0a\u5224\u65ad\u8fd9\u79cd\u4e8b\u60c5\u7684\u6982\u7387\u662f\u6bd4\u8f83\u4f4e\u7684\u3002<\/p>\n<h3><span id=\".E4.BC.98.E7.82.B9\" class=\"mw-headline\">\u4f18\u70b9<\/span><\/h3>\n<p>\u76f8\u6bd4\u4e8e\u5176\u5b83\u7684\u6570\u636e\u7ed3\u6784\uff0c\u5e03\u9686\u8fc7\u6ee4\u5668\u5728\u7a7a\u95f4\u548c\u65f6\u95f4\u65b9\u9762\u90fd\u6709\u5de8\u5927\u7684\u4f18\u52bf\u3002\u5e03\u9686\u8fc7\u6ee4\u5668\u5b58\u50a8\u7a7a\u95f4\u548c\u63d2\u5165\/\u67e5\u8be2\u65f6\u95f4\u90fd\u662f\u5e38\u6570\u3002\u53e6\u5916, Hash \u51fd\u6570\u76f8\u4e92\u4e4b\u95f4\u6ca1\u6709\u5173\u7cfb\uff0c\u65b9\u4fbf\u7531\u786c\u4ef6\u5e76\u884c\u5b9e\u73b0\u3002\u5e03\u9686\u8fc7\u6ee4\u5668\u4e0d\u9700\u8981\u5b58\u50a8\u5143\u7d20\u672c\u8eab\uff0c\u5728\u67d0\u4e9b\u5bf9\u4fdd\u5bc6\u8981\u6c42\u975e\u5e38\u4e25\u683c\u7684\u573a\u5408\u6709\u4f18\u52bf\u3002<\/p>\n<p>\u5e03\u9686\u8fc7\u6ee4\u5668\u53ef\u4ee5\u8868\u793a\u5168\u96c6\uff0c\u5176\u5b83\u4efb\u4f55\u6570\u636e\u7ed3\u6784\u90fd\u4e0d\u80fd\uff1b<\/p>\n<p>k \u548c m \u76f8\u540c\uff0c\u4f7f\u7528\u540c\u4e00\u7ec4 Hash \u51fd\u6570\u7684\u4e24\u4e2a\u5e03\u9686\u8fc7\u6ee4\u5668\u7684\u4ea4\u5e76\u5dee\u8fd0\u7b97\u53ef\u4ee5\u4f7f\u7528\u4f4d\u64cd\u4f5c\u8fdb\u884c\u3002<\/p>\n<h3>\u7f3a\u70b9<\/h3>\n<p>\u4f46\u662f\u5e03\u9686\u8fc7\u6ee4\u5668\u7684\u7f3a\u70b9\u548c\u4f18\u70b9\u4e00\u6837\u660e\u663e\u3002\u8bef\u7b97\u7387\uff08False Positive\uff09\u662f\u5176\u4e2d\u4e4b\u4e00\u3002\u968f\u7740\u5b58\u5165\u7684\u5143\u7d20\u6570\u91cf\u589e\u52a0\uff0c\u8bef\u7b97\u7387\u968f\u4e4b\u589e\u52a0\u3002\u4f46\u662f\u5982\u679c\u5143\u7d20\u6570\u91cf\u592a\u5c11\uff0c\u5219\u4f7f\u7528\u6563\u5217\u8868\u8db3\u77e3\u3002<\/p>\n<p>\u53e6\u5916\uff0c\u4e00\u822c\u60c5\u51b5\u4e0b\u4e0d\u80fd\u4ece\u5e03\u9686\u8fc7\u6ee4\u5668\u4e2d\u5220\u9664\u5143\u7d20. \u6211\u4eec\u5f88\u5bb9\u6613\u60f3\u5230\u628a\u4f4d\u5217\u9635\u53d8\u6210\u6574\u6570\u6570\u7ec4\uff0c\u6bcf\u63d2\u5165\u4e00\u4e2a\u5143\u7d20\u76f8\u5e94\u7684\u8ba1\u6570\u5668\u52a01, \u8fd9\u6837\u5220\u9664\u5143\u7d20\u65f6\u5c06\u8ba1\u6570\u5668\u51cf\u6389\u5c31\u53ef\u4ee5\u4e86\u3002\u7136\u800c\u8981\u4fdd\u8bc1\u5b89\u5168\u7684\u5220\u9664\u5143\u7d20\u5e76\u975e\u5982\u6b64\u7b80\u5355\u3002\u9996\u5148\u6211\u4eec\u5fc5\u987b\u4fdd\u8bc1\u5220\u9664\u7684\u5143\u7d20\u7684\u786e\u5728\u5e03\u9686\u8fc7\u6ee4\u5668\u91cc\u9762. \u8fd9\u4e00\u70b9\u5355\u51ed\u8fd9\u4e2a\u8fc7\u6ee4\u5668\u662f\u65e0\u6cd5\u4fdd\u8bc1\u7684\u3002\u53e6\u5916\u8ba1\u6570\u5668\u56de\u7ed5\u4e5f\u4f1a\u9020\u6210\u95ee\u9898\u3002<\/p>\n<h3><span id=\"Probability_of_false_positives\" class=\"mw-headline\">False positives \u6982\u7387\u63a8\u5bfc<\/span><\/h3>\n<p><span class=\"mw-headline\">\u5047\u8bbe Hash \u51fd\u6570\u4ee5\u7b49\u6982\u7387\u6761\u4ef6\u9009\u62e9\u5e76\u8bbe\u7f6e Bit Array \u4e2d\u7684\u67d0\u4e00\u4f4d\uff0cm \u662f\u8be5\u4f4d\u6570\u7ec4\u7684\u5927\u5c0f\uff0ck \u662f Hash \u51fd\u6570\u7684\u4e2a\u6570\uff0c\u90a3\u4e48\u4f4d\u6570\u7ec4\u4e2d\u67d0\u4e00\u7279\u5b9a\u7684\u4f4d\u5728\u8fdb\u884c\u5143\u7d20\u63d2\u5165\u65f6\u7684 Hash \u64cd\u4f5c\u4e2d\u6ca1\u6709\u88ab\u7f6e\u4f4d\u7684\u6982\u7387\u662f\uff1a<br \/>\n<\/span><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/pic002.cnblogs.com\/images\/2012\/274814\/2012071316492245.png\" alt=\"\" \/><\/p>\n<p>\u90a3\u4e48\u5728\u6240\u6709 k \u6b21 Hash \u64cd\u4f5c\u540e\u8be5\u4f4d\u90fd\u6ca1\u6709\u88ab\u7f6e &#8220;1&#8221; \u7684\u6982\u7387\u662f\uff1a<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/pic002.cnblogs.com\/images\/2012\/274814\/2012071316510534.png\" alt=\"\" \/><\/p>\n<p>\u5982\u679c\u6211\u4eec\u63d2\u5165\u4e86 n \u4e2a\u5143\u7d20\uff0c\u90a3\u4e48\u67d0\u4e00\u4f4d\u4ecd\u7136\u4e3a &#8220;0&#8221; \u7684\u6982\u7387\u662f\uff1a<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/pic002.cnblogs.com\/images\/2012\/274814\/2012071316525966.png\" alt=\"\" \/><\/p>\n<p>\u56e0\u800c\u8be5\u4f4d\u4e3a &#8220;1&#8221;\u7684\u6982\u7387\u662f\uff1a<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/pic002.cnblogs.com\/images\/2012\/274814\/2012071316520528.png\" alt=\"\" \/><\/p>\n<p>\u73b0\u5728\u68c0\u6d4b\u67d0\u4e00\u5143\u7d20\u662f\u5426\u5728\u8be5\u96c6\u5408\u4e2d\u3002\u6807\u660e\u67d0\u4e2a\u5143\u7d20\u662f\u5426\u5728\u96c6\u5408\u4e2d\u6240\u9700\u7684 k \u4e2a\u4f4d\u7f6e\u90fd\u6309\u7167\u5982\u4e0a\u7684\u65b9\u6cd5\u8bbe\u7f6e\u4e3a &#8220;1&#8221;\uff0c\u4f46\u662f\u8be5\u65b9\u6cd5\u53ef\u80fd\u4f1a\u4f7f\u7b97\u6cd5\u9519\u8bef\u7684\u8ba4\u4e3a\u67d0\u4e00\u539f\u672c\u4e0d\u5728\u96c6\u5408\u4e2d\u7684\u5143\u7d20\u5374\u88ab\u68c0\u6d4b\u4e3a\u5728\u8be5\u96c6\u5408\u4e2d\uff08False Positives\uff09\uff0c\u8be5\u6982\u7387\u7531\u4ee5\u4e0b\u516c\u5f0f\u786e\u5b9a\uff1a<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/pic002.cnblogs.com\/images\/2012\/274814\/2012071317030828.png\" alt=\"\" \/><\/p>\n<p>\u5176\u5b9e\u4e0a\u8ff0\u7ed3\u679c\u662f\u5728\u5047\u5b9a\u7531\u6bcf\u4e2a Hash \u8ba1\u7b97\u51fa\u9700\u8981\u8bbe\u7f6e\u7684\u4f4d\uff08bit\uff09 \u7684\u4f4d\u7f6e\u662f\u76f8\u4e92\u72ec\u7acb\u4e3a\u524d\u63d0\u8ba1\u7b97\u51fa\u6765\u7684\uff0c\u4e0d\u96be\u770b\u51fa\uff0c\u968f\u7740 m \uff08\u4f4d\u6570\u7ec4\u5927\u5c0f\uff09\u7684\u589e\u52a0\uff0c\u5047\u6b63\u4f8b\uff08False Positives\uff09\u7684\u6982\u7387\u4f1a\u4e0b\u964d\uff0c\u540c\u65f6\u968f\u7740\u63d2\u5165\u5143\u7d20\u4e2a\u6570 n \u7684\u589e\u52a0\uff0cFalse Positives\u7684\u6982\u7387\u53c8\u4f1a\u4e0a\u5347\uff0c\u5bf9\u4e8e\u7ed9\u5b9a\u7684m\uff0cn\uff0c\u5982\u4f55\u9009\u62e9Hash\u51fd\u6570\u4e2a\u6570 k \u7531\u4ee5\u4e0b\u516c\u5f0f\u786e\u5b9a\uff1a<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/pic002.cnblogs.com\/images\/2012\/274814\/2012071317175487.png\" alt=\"\" \/><\/p>\n<p>\u6b64\u65f6False Positives\u7684\u6982\u7387\u4e3a\uff1a<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/pic002.cnblogs.com\/images\/2012\/274814\/2012071317184158.png\" alt=\"\" \/><\/p>\n<p>\u800c\u5bf9\u4e8e\u7ed9\u5b9a\u7684False Positives\u6982\u7387 p\uff0c\u5982\u4f55\u9009\u62e9\u6700\u4f18\u7684\u4f4d\u6570\u7ec4\u5927\u5c0f m \u5462\uff0c<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/pic002.cnblogs.com\/images\/2012\/274814\/2012071317223869.png\" alt=\"\" \/><\/p>\n<p>\u4e0a\u5f0f\u8868\u660e\uff0c\u4f4d\u6570\u7ec4\u7684\u5927\u5c0f\u6700\u597d\u4e0e\u63d2\u5165\u5143\u7d20\u7684\u4e2a\u6570\u6210\u7ebf\u6027\u5173\u7cfb\uff0c\u5bf9\u4e8e\u7ed9\u5b9a\u7684 m\uff0cn\uff0ck\uff0c\u5047\u6b63\u4f8b\u6982\u7387\u6700\u5927\u4e3a\uff1a<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/pic002.cnblogs.com\/images\/2012\/274814\/2012071317253418.png\" alt=\"\" \/><\/p>\n<h3><\/h3>\n<p>\u4e0b\u56fe\u662f\u5e03\u9686\u8fc7\u6ee4\u5668\u5047\u6b63\u4f8b\u6982\u7387 p \u4e0e\u4f4d\u6570\u7ec4\u5927\u5c0f m \u548c\u96c6\u5408\u4e2d\u63d2\u5165\u5143\u7d20\u4e2a\u6570 n \u7684\u5173\u7cfb\u56fe\uff0c\u5047\u5b9a Hash \u51fd\u6570\u4e2a\u6570\u9009\u53d6\u6700\u4f18\u6570\u76ee\uff1a<img decoding=\"async\" src=\"https:\/\/pic002.cnblogs.com\/images\/2012\/274814\/2012071317394641.png\" alt=\"\" \/><\/p>\n<p>&nbsp;<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/pic002.cnblogs.com\/images\/2012\/274814\/2012071317362559.png\" alt=\"\" \/><\/p>\n<h3>Bloom Filter \u7528\u4f8b<\/h3>\n<p>Google \u8457\u540d\u7684\u5206\u5e03\u5f0f\u6570\u636e\u5e93 Bigtable \u4f7f\u7528\u4e86\u5e03\u9686\u8fc7\u6ee4\u5668\u6765\u67e5\u627e\u4e0d\u5b58\u5728\u7684\u884c\u6216\u5217\uff0c\u4ee5\u51cf\u5c11\u78c1\u76d8\u67e5\u627e\u7684IO\u6b21\u6570\uff3b3\uff3d\u3002<\/p>\n<p>Squid \u7f51\u9875\u4ee3\u7406\u7f13\u5b58\u670d\u52a1\u5668\u5728\u00a0<a class=\"external text\" href=\"http:\/\/wiki.squid-cache.org\/SquidFaq\/CacheDigests\" rel=\"nofollow\">cache digests\u00a0<\/a>\u4e2d\u4f7f\u7528\u4e86\u4e5f\u5e03\u9686\u8fc7\u6ee4\u5668\uff3b4\uff3d\u3002<\/p>\n<p>Venti \u6587\u6863\u5b58\u50a8\u7cfb\u7edf\u4e5f\u91c7\u7528\u5e03\u9686\u8fc7\u6ee4\u5668\u6765\u68c0\u6d4b\u5148\u524d\u5b58\u50a8\u7684\u6570\u636e\uff3b5\uff3d\u3002<\/p>\n<p>SPIN \u6a21\u578b\u68c0\u6d4b\u5668\u4e5f\u4f7f\u7528\u5e03\u9686\u8fc7\u6ee4\u5668\u5728\u5927\u89c4\u6a21\u9a8c\u8bc1\u95ee\u9898\u65f6\u8ddf\u8e2a\u53ef\u8fbe\u72b6\u6001\u7a7a\u95f4\uff3b6\uff3d\u3002<\/p>\n<p>Google Chrome\u6d4f\u89c8\u5668\u4f7f\u7528\u4e86\u5e03\u9686\u8fc7\u6ee4\u5668\u52a0\u901f\u5b89\u5168\u6d4f\u89c8\u670d\u52a1\uff3b7\uff3d\u3002<\/p>\n<p>\u5728\u5f88\u591aKey-Value\u7cfb\u7edf\u4e2d\u4e5f\u4f7f\u7528\u4e86\u5e03\u9686\u8fc7\u6ee4\u5668\u6765\u52a0\u5feb\u67e5\u8be2\u8fc7\u7a0b\uff0c\u5982 Hbase\uff0cAccumulo\uff0cLeveldb\uff0c\u4e00\u822c\u800c\u8a00\uff0cValue \u4fdd\u5b58\u5728\u78c1\u76d8\u4e2d\uff0c\u8bbf\u95ee\u78c1\u76d8\u9700\u8981\u82b1\u8d39\u5927\u91cf\u65f6\u95f4\uff0c\u7136\u800c\u4f7f\u7528\u5e03\u9686\u8fc7\u6ee4\u5668\u53ef\u4ee5\u5feb\u901f\u5224\u65ad\u67d0\u4e2aKey\u5bf9\u5e94\u7684Value\u662f\u5426\u5b58\u5728\uff0c\u56e0\u6b64\u53ef\u4ee5\u907f\u514d\u5f88\u591a\u4e0d\u5fc5\u8981\u7684\u78c1\u76d8IO\u64cd\u4f5c\uff0c\u53ea\u662f\u5f15\u5165\u5e03\u9686\u8fc7\u6ee4\u5668\u4f1a\u5e26\u6765\u4e00\u5b9a\u7684\u5185\u5b58\u6d88\u8017\uff0c\u4e0b\u56fe\u662f\u5728Key-Value\u7cfb\u7edf\u4e2d\u5e03\u9686\u8fc7\u6ee4\u5668\u7684\u5178\u578b\u4f7f\u7528\uff1a<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/pic002.cnblogs.com\/images\/2012\/274814\/2012071317513278.png\" alt=\"\" \/><\/p>\n<h3><\/h3>\n<h3>\u5e03\u9686\u8fc7\u6ee4\u5668\u76f8\u5173\u6269\u5c55<\/h3>\n<h4>\u00a0<span id=\"Counting_filters\" class=\"mw-headline\">Counting filters<\/span><\/h4>\n<p><span class=\"mw-headline\">\u57fa\u672c\u7684\u5e03\u9686\u8fc7\u6ee4\u5668\u4e0d\u652f\u6301\u5220\u9664\uff08Deletion\uff09\u64cd\u4f5c\uff0c\u4f46\u662f Counting filters \u63d0\u4f9b\u4e86\u4e00\u79cd\u53ef\u4ee5\u4e0d\u7528\u91cd\u65b0\u6784\u5efa\u5e03\u9686\u8fc7\u6ee4\u5668\u4f46\u5374\u652f\u6301\u5143\u7d20\u5220\u9664\u64cd\u4f5c\u7684\u65b9\u6cd5\u3002\u5728Counting filters\u4e2d\u539f\u6765\u7684\u4f4d\u6570\u7ec4\u4e2d\u7684\u6bcf\u4e00\u4f4d\u7531 bit \u6269\u5c55\u4e3a n-bit \u8ba1\u6570\u5668\uff0c\u5b9e\u9645\u4e0a\uff0c\u57fa\u672c\u7684\u5e03\u9686\u8fc7\u6ee4\u5668\u53ef\u4ee5\u770b\u4f5c\u662f\u53ea\u6709\u4e00\u4f4d\u7684\u8ba1\u6570\u5668\u7684Counting filters\u3002\u539f\u6765\u7684\u63d2\u5165\u64cd\u4f5c\u4e5f\u88ab\u6269\u5c55\u4e3a\u628a n-bit \u7684\u4f4d\u8ba1\u6570\u5668\u52a01\uff0c\u67e5\u627e\u64cd\u4f5c\u5373\u68c0\u67e5\u4f4d\u6570\u7ec4\u975e\u96f6\u5373\u53ef\uff0c\u800c\u5220\u9664\u64cd\u4f5c\u5b9a\u4e49\u4e3a\u628a\u4f4d\u6570\u7ec4\u7684\u76f8\u5e94\u4f4d\u51cf1\uff0c\u4f46\u662f\u8be5\u65b9\u6cd5\u4e5f\u6709\u4f4d\u7684\u7b97\u672f\u6ea2\u51fa\u95ee\u9898\uff0c\u5373\u67d0\u4e00\u4f4d\u5728\u591a\u6b21\u5220\u9664\u64cd\u4f5c\u540e\u53ef\u80fd\u53d8\u6210\u8d1f\u503c\uff0c\u6240\u4ee5\u4f4d\u6570\u7ec4\u5927\u5c0f m \u9700\u8981\u5145\u5206\u5927\u3002\u53e6\u5916\u4e00\u4e2a\u95ee\u9898\u662fCounting filters\u4e0d\u5177\u5907\u4f38\u7f29\u6027\uff0c\u7531\u4e8eCounting filters\u4e0d\u80fd\u6269\u5c55\uff0c\u6240\u4ee5\u9700\u8981\u4fdd\u5b58\u7684\u6700\u5927\u7684\u5143\u7d20\u4e2a\u6570\u9700\u8981\u63d0\u524d\u77e5\u9053\u3002\u5426\u5219\u4e00\u65e6\u63d2\u5165\u7684\u5143\u7d20\u4e2a\u6570\u8d85\u8fc7\u4e86\u4f4d\u6570\u7ec4\u7684\u5bb9\u91cf\uff0cfalse positive\u7684\u53d1\u751f\u6982\u7387\u5c06\u4f1a\u6025\u5267\u589e\u52a0\u3002\u5f53\u7136\u4e5f\u6709\u4eba\u63d0\u51fa\u4e86\u4e00\u79cd\u57fa\u4e8e D-left Hash \u65b9\u6cd5\u5b9e\u73b0\u652f\u6301\u5220\u9664\u64cd\u4f5c\u7684\u5e03\u9686\u8fc7\u6ee4\u5668\uff0c\u540c\u65f6\u7a7a\u95f4\u6548\u7387\u4e5f\u6bd4Counting filters\u9ad8\u3002<br \/>\n<\/span><\/p>\n<h4><span id=\"Data_synchronization\" class=\"mw-headline\">Data synchronization<\/span><\/h4>\n<p><span class=\"mw-headline\">Byers\u7b49\u4eba\u63d0\u51fa\u4e86\u4f7f\u7528\u5e03\u9686\u8fc7\u6ee4\u5668\u8fd1\u4f3c\u6570\u636e\u540c\u6b65\uff3b9\uff3d\u3002<br \/>\n<\/span><\/p>\n<h4><span id=\"Bloomier_filters\" class=\"mw-headline\">Bloomier filters<\/span><\/h4>\n<p><span class=\"mw-headline\">Chazelle \u7b49\u4eba\u63d0\u51fa\u4e86\u4e00\u4e2a\u901a\u7528\u7684\u5e03\u9686\u8fc7\u6ee4\u5668\uff0c\u8be5\u5e03\u9686\u8fc7\u6ee4\u5668\u53ef\u4ee5\u5c06\u67d0\u4e00\u503c\u4e0e\u6bcf\u4e2a\u5df2\u7ecf\u63d2\u5165\u7684\u5143\u7d20\u5173\u8054\u8d77\u6765\uff0c\u5e76\u5b9e\u73b0\u4e86\u4e00\u4e2a\u5173\u8054\u6570\u7ec4Map\uff3b10\uff3d\u3002\u4e0e\u666e\u901a\u7684\u5e03\u9686\u8fc7\u6ee4\u5668\u4e00\u6837\uff0cChazelle\u5b9e\u73b0\u7684\u5e03\u9686\u8fc7\u6ee4\u5668\u4e5f\u53ef\u4ee5\u8fbe\u5230\u8f83\u4f4e\u7684\u7a7a\u95f4\u6d88\u8017\uff0c\u4f46\u540c\u65f6\u4e5f\u4f1a\u4ea7\u751ffalse positive\uff0c\u4e0d\u8fc7\uff0c\u5728Bloomier filter\u4e2d\uff0c\u67d0 key \u5982\u679c\u4e0d\u5728 map \u4e2d\uff0cfalse positive\u5728\u4f1a\u8fd4\u56de\u65f6\u4f1a\u88ab\u5b9a\u4e49\u51fa\u7684\u3002\u8be5Map \u7ed3\u6784\u4e0d\u4f1a\u8fd4\u56de\u4e0e key \u76f8\u5173\u7684\u5728 map \u4e2d\u7684\u9519\u8bef\u7684\u503c\u3002<br \/>\n<\/span><\/p>\n<h4><span id=\"Compact_approximators\" class=\"mw-headline\">Compact approximators\uff3b11\uff3d<\/span><\/h4>\n<h4><span id=\"Stable_Bloom_filters\" class=\"mw-headline\">Stable Bloom filters\uff3b12\uff3d<\/span><\/h4>\n<h4><span id=\"Scalable_Bloom_filters\" class=\"mw-headline\">Scalable Bloom filters\uff3b13\uff3d<\/span><\/h4>\n<h4><span id=\"Attenuated_Bloom_filters\" class=\"mw-headline\">Attenuated Bloom filters\uff3b14\uff3d<\/span><\/h4>\n<h3><span class=\"mw-headline\">\u76f8\u5173\u94fe\u63a5<br \/>\n<\/span><\/h3>\n<ul>\n<li><a class=\"external text\" href=\"http:\/\/www.cs.wisc.edu\/~cao\/papers\/summary-cache\/node8.html\" rel=\"nofollow\">Table of false-positive rates for different configurations<\/a>\u00a0from a\u00a0<a title=\"University of Wisconsin\u2013Madison\" href=\"http:\/\/en.wikipedia.org\/wiki\/University_of_Wisconsin%E2%80%93Madison\">University of Wisconsin\u2013Madison<\/a>\u00a0website<\/li>\n<li><a class=\"external text\" href=\"http:\/\/tr.ashcan.org\/2008\/12\/bloomers.html\" rel=\"nofollow\">Interactive Processing demonstration<\/a>\u00a0from ashcan.org<\/li>\n<li><a class=\"external text\" href=\"http:\/\/www.youtube.com\/watch?v=947gWqwkhu0\" rel=\"nofollow\">&#8220;More Optimal Bloom Filters,&#8221; Ely Porat (Nov\/2007) Google TechTalk video<\/a>\u00a0on\u00a0<a title=\"YouTube\" href=\"http:\/\/en.wikipedia.org\/wiki\/YouTube\">YouTube<\/a><\/li>\n<li><a class=\"external text\" href=\"http:\/\/www.perl.com\/pub\/2004\/04\/08\/bloom_filters.html\" rel=\"nofollow\">&#8220;Using Bloom Filters&#8221;<\/a>\u00a0Detailed Bloom Filter explanation using\u00a0<a title=\"Perl\" href=\"http:\/\/en.wikipedia.org\/wiki\/Perl\">Perl<\/a><\/li>\n<\/ul>\n<h3>\u53c2\u8003\u8d44\u6599<\/h3>\n<p>\uff3b1\uff3d\u7ef4\u57fa\u767e\u79d1\uff1a\u5e03\u9686\u8fc7\u6ee4\u5668\uff1ahttp:\/\/zh.wikipedia.org\/zh\/%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8<\/p>\n<p>\uff3b2\uff3d\u6570\u5b66\u4e4b\u7f8e\u4e8c\u5341\u4e00\uff1a\u5e03\u9686\u8fc7\u6ee4\u5668\uff08Bloom Filter\uff09\uff1ahttp:\/\/www.google.com.hk\/ggblog\/googlechinablog\/2007\/07\/bloom-filter_7469.html<\/p>\n<p>\uff3b3\uff3d<span id=\"CITEREFChangDeanGhemawatHsieh2006\" class=\"citation\">Chang, Fay; Dean, Jeffrey; Ghemawat, Sanjay; Hsieh, Wilson; Wallach, Deborah; Burrows, Mike; Chandra, Tushar; Fikes, Andrew et al. (2006),\u00a0<a class=\"external text\" href=\"http:\/\/research.google.com\/archive\/bigtable.html\" rel=\"nofollow\">&#8220;Bigtable: A Distributed Storage System for Structured Data&#8221;<\/a>,\u00a0<em>Seventh Symposium on Operating System Design and Implementation<\/em><\/span><\/p>\n<p>\uff3b4\uff3d<span class=\"reference-text\">Wessels, Duane (January 2004), &#8220;10.7 Cache Digests&#8221;,\u00a0<em>Squid: The Definitive Guide<\/em>\u00a0(1st ed.), O&#8217;Reilly Media, p.\u00a0172,\u00a0<a title=\"International Standard Book Number\" href=\"http:\/\/en.wikipedia.org\/wiki\/International_Standard_Book_Number\">ISBN<\/a>\u00a0<a title=\"Special:BookSources\/0-596-00162-2\" href=\"http:\/\/en.wikipedia.org\/wiki\/Special:BookSources\/0-596-00162-2\">0-596-00162-2<\/a>, &#8220;Cache Digests are based on a technique first published by Pei Cao, called Summary Cache. The fundamental idea is to use a Bloom filter to represent the cache contents.&#8221;<\/span><\/p>\n<p>\uff3b5\uff3d<span class=\"reference-text\"><a class=\"external free\" href=\"http:\/\/plan9.bell-labs.com\/magic\/man2html\/8\/venti\" rel=\"nofollow\">http:\/\/plan9.bell-labs.com\/magic\/man2html\/8\/venti<\/a><\/span><\/p>\n<p>\uff3b6\uff3d<span class=\"reference-text\"><a class=\"external free\" href=\"http:\/\/spinroot.com\/\" rel=\"nofollow\">http:\/\/spinroot.com\/<\/a><\/span><\/p>\n<p>\uff3b7\uff3d<span class=\"reference-text\"><a>http:\/\/src.chromium.org\/viewvc\/chrome\/trunk\/src\/chrome\/browser\/safe_browsing\/bloom_filter.h?view=markup<\/a><\/span><\/p>\n<p><span class=\"reference-text\">\uff3b8\uff3d<a>http:\/\/en.wikipedia.org\/wiki\/Bloom_filter<\/a><br \/>\n<\/span><\/p>\n<p><span class=\"reference-text\">\uff3b9\uff3d<span id=\"CITEREFByersConsidineMitzenmacherRost2004\" class=\"citation\">Byers, John W.; Considine, Jeffrey; Mitzenmacher, Michael; Rost, Stanislav (2004), &#8220;Informed content delivery across adaptive overlay networks&#8221;,\u00a0<em>IEEE\/ACM Transactions on Networking<\/em>\u00a0<strong>12<\/strong>\u00a0(5): 767, DOI:<span class=\"external text\">10.1109\/TNET.2004.836103<br \/>\n<\/span><\/span><\/span><\/p>\n<p><span class=\"reference-text\">\uff3b10\uff3d<span id=\"CITEREFChazelleKilianRubinfeldTal2004\" class=\"citation\">Chazelle, Bernard; Kilian, Joe; Rubinfeld, Ronitt; Tal, Ayellet (2004),\u00a0<span class=\"external text\">&#8220;The Bloomier filter: an efficient data structure for static support lookup tables&#8221;,\u00a0<em>Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms<\/em>, pp.\u00a030\u201339<br \/>\n<\/span><\/span><\/span><\/p>\n<p><span class=\"reference-text\">\uff3b11\uff3d<span id=\"CITEREFBoldiVigna2005\" class=\"citation\">Boldi, Paolo; Vigna, Sebastiano (2005), &#8220;Mutable strings in Java: design, implementation and lightweight text-search algorithms&#8221;,\u00a0<em>Science of Computer Programming<\/em>\u00a0<strong>54<\/strong>\u00a0(1): 3\u201323, DOI:<span class=\"external text\">10.1016\/j.scico.2004.05.003<br \/>\n<\/span><\/span><\/span><\/p>\n<p><span class=\"reference-text\">\uff3b12\uff3d<span id=\"CITEREFDengRafiei2006\" class=\"citation\">Deng, Fan; Rafiei, Davood (2006),\u00a0<span class=\"external text\">&#8220;Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters&#8221;,\u00a0<em>Proceedings of the ACM SIGMOD Conference<\/em>, pp.\u00a025\u201336<br \/>\n<\/span><\/span><\/span><\/p>\n<p><span class=\"reference-text\">\uff3b13\uff3d<span id=\"CITEREFAlmeidaBaqueroPreguicaHutchison2007\" class=\"citation\">Almeida, Paulo; Baquero, Carlos; Preguica, Nuno; Hutchison, David (2007),\u00a0<span class=\"external text\">&#8220;Scalable Bloom Filters&#8221;,\u00a0<em>Information Processing Letters<\/em>\u00a0<strong>101<\/strong>\u00a0(6): 255\u2013261, DOI:10.1016\/j.ipl.2006.10.007<br \/>\n<\/span><\/span><\/span><\/p>\n<p><span class=\"reference-text\">\uff3b14\uff3dhttp:\/\/en.wikipedia.org\/wiki\/Bloom_filter#Attenuated_Bloom_filters<\/span><\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>\u5e03\u9686\u8fc7\u6ee4\u5668(Bloom Filter)\u8be6<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","footnotes":""},"categories":[],"tags":[118],"class_list":["post-1211","post","type-post","status-publish","format-standard","hentry","tag-02-"],"_links":{"self":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/1211","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/comments?post=1211"}],"version-history":[{"count":0,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/1211\/revisions"}],"wp:attachment":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/media?parent=1211"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/categories?post=1211"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/tags?post=1211"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}