<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                # 布隆過濾器 ## 場景 假設你現在要處理這樣一個問題,你有一個網站并且擁有`很多`訪客,每當有用戶訪問時,你想知道這個ip是不是第一次訪問你的網站。 ### hashtable 可以么 一個顯而易見的答案是將所有的 IP 用 hashtable 存起來,每次訪問都去 hashtable 中取,然后判斷即可。但是題目說了網站有`很多`訪客, 假如有10億個用戶訪問過,假設 IP 是 IPV4, 那么每個 IP 的長度是 4 byte,那么你一共需要4 \* 1000000000 = 4000000000Bytes = 4G 。 如果是判斷 URL 黑名單,由于每個 URL 會更長(可能遠大于上面 IPV4 地址的 4 byte),那么需要的空間可能會遠遠大于你的期望。 ### bit 另一個稍微難想到的解法是bit, 我們知道bit有 0 和 1 兩種狀態,那么用來表示**存在**與**不存在**再合適不過了。 假如有 10 億個 IP,就可以用 10 億個 bit 來存儲,那么你一共需要 1 \* 1000000000 = (4000000000 / 8) Bytes = 128M, 變為原來的1/32, 如果是存儲URL這種更長的字符串,效率會更高。 問題是,我們怎么把 IPV4 和 bit 的位置關聯上呢? 比如`192.168.1.1` 應該是用第幾位表示,`10.18.1.1` 應該是用第幾位表示呢? 答案是使用哈希函數。 基于這種想法,我們只需要兩個操作,set(ip) 和 has(ip),以及一個內置函數 hash(ip) 用于將 IP 映射到 bit 表。 這樣做有兩個非常致命的缺點: 1. 當樣本分布極度不均勻的時候,會造成很大空間上的浪費 > 我們可以通過優化散列函數來解決 1. 當元素不是整型(比如URL)的時候,BitSet就不適用了 > 我們還是可以使用散列函數來解決, 甚至可以多hash幾次 ### 布隆過濾器 布隆過濾器其實就是`bit + 多個散列函數`。k 次 hash(ip) 會生成多個索引,并將其 k 個索引位置的二進制置為 1。 如果經過 k 個索引位置的值都為 1,那么認為其**可能存在**(因為有沖突的可能)。 如果有一個不為1,那么**一定不存在**(一個值經過散列函數得到的值一定是唯一的),這也是布隆過濾器的一個重要特點。也就是說布隆過濾器回答了:**可能存在** 和 **一定不存在** 的問題。 ![](https://img.kancloud.cn/88/c2/88c2956c7881b687527989550afdc3d1_1586x605.jpg) 從上圖可以看出, 布隆過濾器本質上是由**一個很長的二進制向量**和**多個哈希函數**組成。 由于沒有 hashtable 的100% 可靠性,因此這本質上是一種**可靠性換取空間的做法**。除了可靠性,布隆過濾器刪除起來也比較麻煩。 ### 布隆過濾器的應用 1. 網絡爬蟲 判斷某個URL是否已經被爬取過 1. K-V數據庫 判斷某個key是否存在 比如 Hbase 的每個 Region 中都包含一個 BloomFilter,用于在查詢時快速判斷某個 key 在該 region 中是否存在。 1. 釣魚網站識別 瀏覽器有時候會警告用戶,訪問的網站很可能是釣魚網站,用的就是這種技術 > 從這個算法大家可以對 tradeoff(取舍) 有更入的理解。
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看