算法

過濾器

如何在100 億URL中判斷某個URL是否存在

1. 布隆過濾器

使用：布隆過濾器?？梢杂糜跈z索一個元素是否在一個集合中。它的優(yōu)點是空間效率和查詢時間都遠(yuǎn)遠(yuǎn)超過一般的算法，缺點是有一定的誤識別率和刪除困難
效果：文章提到:如果將 100 億 url(64bit) 放到 HashMap 中需要 640GB，那么使用布隆過濾器后又需要多少空間呢？答案是約等于 23 GB

2. 布谷過濾器-cuckoo filter

優(yōu)化：布隆過濾器只支持新增、查找，布谷過濾器支持刪除

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 在前面的二分查找示例中，每當(dāng)用戶登錄Facebook時，F(xiàn)acebook都必須在一個龐大的數(shù)組中查找，核實其中是否...
    非問閱讀 269評論 0贊 0
  • 布隆過濾器 不安全網(wǎng)頁的黑名單包含100億個黑名單網(wǎng)頁，每個網(wǎng)頁的URL最多占用64字節(jié)，現(xiàn)在想要實現(xiàn)一種網(wǎng)頁過濾...
    亼亼閱讀 394評論 0贊 0
  • 其實我喜歡的不是花，而是花里的時間，花里的四季，花里的好天氣與花開花落間斑駁了的傾談回憶。
    拾染z閱讀 292評論 0贊 1
  • 整個城市在這個時刻靜了下來，于是我聽到了久違的手表指針發(fā)出的的嘀嗒聲，不禁想起了以前那些挑燈奮戰(zhàn)的夜晚，那些所謂的...
    Modest_Kevin閱讀 190評論 0贊 2
  • 你已不是17歲的時候，可能那個人笑起來好可愛，眼睛彎彎的。 可能那個人打籃球很帥，襯衣很干凈，就喜歡他。 但現(xiàn)在喜...
    禾子筱敏閱讀 259評論 0贊 0

友情鏈接更多精彩內(nèi)容