問題：網頁爬蟲是搜索引擎中的非常重要的系統(tǒng)落午，負責爬取幾十億、上百億的網頁肚豺。爬蟲的工作原理是溃斋，通過解析已經爬取頁面中的網頁鏈接，然后再爬取這些鏈接對應的網頁吸申。而同一個網頁鏈接有可能被包含在多個頁面中梗劫，這就會導致爬蟲在爬取的過程中，重復爬取相同的網頁呛谜。如果你是一名負責爬蟲的工程師在跳，你會如何避免這些重復的爬取呢？
解析：
關于搜索引擎爬蟲網頁去重問題的解決隐岛，我們從散列表講到位圖猫妙，再講到布隆過濾器。布隆過濾器非常適合這種不需要 100% 準確的聚凹、允許存在小概率誤判的大規(guī)模判重場景割坠。除了爬蟲網頁去重這個例子，還有比如統(tǒng)計一個大型網站的每天的 UV 數妒牙，也就是每天有多少用戶訪問了網站彼哼，我們就可以使用布隆過濾器，對重復訪問的用戶進行去重湘今。我們前面講到敢朱，布隆過濾器的誤判率，主要跟哈希函數的個數摩瞎、位圖的大小有關拴签。當我們往布隆過濾器中不停地加入數據之后，位圖中不是 true 的位置就越來越少了旗们，誤判率就越來越高了蚓哩。所以，對于無法事先知道要判重的數據個數的情況上渴，我們需要支持自動擴容的功能岸梨。當布隆過濾器中喜颁，數據個數與位圖大小的比例超過某個閾值的時候，我們就重新申請一個新的位圖曹阔。后面來的新數據半开，會被放置到新的位圖中。但是赃份，如果我們要判斷某個數據是否在布隆過濾器中已經存在稿茉，我們就需要查看多個位圖，相應的執(zhí)行效率就降低了一些芥炭。位圖、布隆過濾器應用如此廣泛恃慧，很多編程語言都已經實現了园蝠。比如 Java 中的 BitSet 類就是一個位圖，Redis 也提供了 BitMap 位圖類痢士，Google 的 Guava 工具包提供了 BloomFilter 布隆過濾器的實現彪薛。
