哈希函數
又見哈希
首先回顧下一般計算機課程都會學到的哈希函數
在查詢存儲在線性表或是樹形結構或是數據庫類中的數據時候，在這類結構中查找記錄時如果是通過比較關鍵字的大小，那用這種方式就會可能經過多次比較，查詢是非常耗時的。
于是就有提出一種通過直接映射方式提升效率的哈希函數法，又稱為散列函數，直接通過一定的函數關系稱為哈希函數將查詢關鍵字映射到指定的地址值，從而快速查找。一般是有個連續(xù)存儲空間哈希表。將數據元素的關鍵字K作為自變量，通過哈希函數，計算出的值，即為該元素的存儲地址。
常用的哈希函數比如平方取中法、折疊法、隨機數法、除留余數法等。
哈希函數有以下一些特性：
輸入的關鍵值范圍無窮大或者就是無法預期的大小，比如數據庫記錄，
輸出的范圍有限，比如0到500，
輸入一個樣輸出肯定一樣，這是函數性質，
當輸入不一樣輸出也可能一樣（哈希碰撞），也是函數性質導致，
不同輸入會均勻分布在輸出域上（哈希函數的散列性）。比如輸入的是0-99 等100個數字，用哈希函數除3取模那輸出域就是0,1,2，當我們將這100個數字通過哈希函數進行映射后，0,1,2的數量都會接近33個，也就是分布比較均勻。
哈希的應用
在實際哈希表應用中，它的查詢速度近乎 O(1)，就是線性復雜度內，這是因為通過 key 計算 hashcode 的時間是常數項時間，而數組尋址的時間也是常數時間。在實際應用中，每個位置的鏈表長度不會太長，當到達一定長度后，哈希表會經歷一次擴容，這就意味著遍歷鏈表的時間也是常數時間。所以我們增刪改查哈希表中的一條記錄也是常數時間。開發(fā)中我們就會比較多考慮使用它
比如在大數據中的應用，這也是面試中會問到的問題，當然主要是學會應用一些基礎方法思想到設計應用過程中。
比如，我們有一個 10TB 的大文件存在分布式文件系統(tǒng)上，存的是 100 億行字符串，并且字符串無序排列，現(xiàn)在我們要統(tǒng)計該文件中重復的字符串。
我們可以調用 100 臺機器來計算該文件，需要將這一百臺機器分別從 0-99 標好號，然后在分布式文件系統(tǒng)中一行行讀取文件，這時候多臺機器是并行的，通過哈希函數計算 hashcode，將計算出的 hashcode 模100 ，根據模出來的值，將該行存入對應的機器中。
這樣相同的字符串會存入相同的機器中，再并行 100 臺機器，各自分別計算相應的數據，加快統(tǒng)計的速度。
哈希在大數據場景下的不足
但是在大數據場景中，我們其實很難直接使用哈希函數，因為哈希函數需要有限的哈希表存在內存里，而我們如果是PB 、TB級別的數據下，即使用哈希也沒足夠的內存空間可以使用。例如在黑名單過濾當中，我們有 100 億的網站黑名單 url 需要過濾，假設一個 url 是 64bytes。如果我們用 hash 表來做，那么我們至少需要 6400 億字節(jié)即 640G 的內存空間（實際所需空間還遠大于此），空間消耗巨大，必須要多個服務器來同時分攤內存。
這就又引出了我們的主角，BloomFIlter 布隆過濾器。它的核心思想是充分利用字符串位數組二進制碼的表示范圍，它充分利用了空間時間的同時，又引入概率思維。
讓我們看下什么是BloomFilter
布隆過濾器
布隆過濾器原理
布隆過濾器（英語：Bloom Filter）是1970年由布隆提出的。可以用于檢索一個元素是否在一個集合中。
首先有一個很長的位數組，類似哈希表，在我們將數據插入集合的時候，通過多個互不相關的哈希函數映射到數組多個位置，將算出的位置設為1, 在查詢數據是否在集合中時候，通過同樣的K個哈希函數看各個對應的位置是否都為1，如果是在集合中，不然就不在集合中。但是這里在也是可能出錯，也就可能其實不在。它可以更好利用空間同時加大效率，使用k個哈希函數對應k個bit位。
簡單說bloom filter的規(guī)則就是不在的一定是不在，在的則不一定在。這也是布隆過濾器的不足，查找成功是有概率的，有一定的錯誤概率。因此，Bloom Filter不適合那些“零錯誤”的應用場合。
另一個不足就是不好刪除數據，刪除的時候不能簡單的直接把對應的1置為0，可能會影響其他元素的判斷?？梢圆捎肹Counting Bloom Filter]
比如a 、b、c是集合S內的元素，通過h1，h2、h3三個哈希函數進行計算
Bloom Filter 實現(xiàn)
接下來問題來了，面的具體問題，我們怎么設置數組長度和哈希函數呢，多少個函數比較好。
這就要計算機科學家去分析證明最優(yōu)解了，可以看出這個算法提出在70年代，到了大數據時代是大放光彩，科技的魅力可見于此有時候一個基礎看似很小的改變可以經久不衰改變世界，敬佩這么多科學家工程師們。
原理和具體證明可以查看論文或是： https://blog.csdn.net/jiaomeng/article/details/1495500
主要的思想是從考慮那個錯誤率開始，如果我們可以知道誤判的概率，那么設計的目標就是盡可能小的組合。
哈希函數個數k、位數組大小m、加入的字符串數量n的關系可以參考Bloom Filters - the math，Bloom_filter-wikipedia
由預估集合數據量n以及位數組長度m，可以得到一個哈希函數的個數k為：
失誤率的計算為
用這些公式估算，像上面url黑名單的例子，如果100 億個，那么對比哈希表，原來我們需要 640GB，而現(xiàn)在只需要 23GB，而同時實際失誤率約為十萬分之六?？梢赃m合工程應用了。
BloomFilter的應用
- 除了黑名單，我們在網絡應用中也很多這種場景，比如爬蟲爬取的時候判斷是否爬過這個網址，已經抓取的url可以用bloom filter過濾。
- 過濾垃圾郵件地址，這個類似黑名單的過濾，
- 還比如我們的HBase中用到bloom filter 來進行分配region
HBase 的布隆過濾器
布隆過濾器是 HBase 中的高級功能，它能夠減少特定訪問模式（get/scan）下的查詢時間。不過由于這種模式增加了內存和存儲的負擔，所以被默認為關閉狀態(tài)。
HBase 支持如下類型的布隆過濾器：
1、NONE 不使用布隆過濾器
2、ROW 行鍵使用布隆過濾器
3、ROWCOL 列鍵使用布隆過濾器
其中 ROWCOL 是粒度更細的模式。
我們可以在代碼里看到在util中做了自己定義
為何使用布隆過濾器
前面知道HBase在scan或get的時候，先進如MemStore中，再選擇在哪個Region ，再進入都具體的HFile，也就是具體存儲數據的HDFS文件，HFIle 是由一個個數據塊與索引塊組成，他們通常默認為 64KB。HBase 是通過塊索引來訪問這些數據塊的。而索引是由每個數據塊的第一行數據的 rowkey 組成的。當 HBase 打開一個 HFile 時，塊索引信息會優(yōu)先加載到內存當中。HBase通過這些塊索引進行查詢。
但是塊索引是相當粗粒度的，我們可以簡單計算一下。假設一個行占 100bytes 的空間，所以一個數據塊 64KB，所包含的行大概有：(64 * 1024)/100 = 655.53 ~= 700 行。而我們只能從索引給出的一個數據塊的起始行開始查詢。
如果用戶隨機查找一個行鍵，則這個行鍵很可能位于兩個開始鍵（即索引）之間的位置。對于 HBase 來說，它判斷這個行鍵是否真實存在的唯一方法就是加載這個數據塊，并且掃描它是否包含這個鍵。
同時，還存在很多情況使得這種情況更加復雜。
對于一個應用來說，用戶通常會以一定的速率進行更新數據，這就將導致內存中的數據被刷寫到磁盤中，并且之后系統(tǒng)會將他們合并成更大的存儲文件。在 HBase 的合并存儲文件的時候，它僅僅會合并最近幾個存儲文件，直至合并的存儲文件到達配置的最大大小。最終系統(tǒng)中會有很多的存儲文件，所有的存儲文件都是候選文件，其可能包含用戶請求行鍵的單元格，
當我們隨機讀 get 數據時，如果采用 HBase 的塊索引機制，HBase 會加載很多塊文件。如果采用布隆過濾器后，它能夠準確判斷該 HFile 的所有數據塊中，是否含有我們查詢的數據，從而大大減少不必要的塊加載，從而增加 HBase 集群的吞吐率。
采用 ROW 還是 ROWCOL 布隆過濾器？
這取決于用戶的使用模式。如果用戶只做行掃描，使用更加細粒度的行加列布隆過濾器不會有任何的幫助，這種場景就應該使用行級布隆過濾器。當用戶不能批量更新特定的一行，并且最后的使用存儲文件都含有改行的一部分時，行加列級的布隆過濾器更加有用。
例如：
ROW 使用場景
假設有 2 個 Hfile 文件 hf1 和 hf2：
hf1 包含 kv1(r1 cf:q1 v)、kv2(r2 cf:q1 v)
hf2 包含 kv3(r3 cf:q1 v)、kv4(r4 cf:q1 v)
如果設置了 CF 屬性中的 bloomfilter（布隆過濾器）為 ROW，那么 get(r1) 時就會過濾 hf2，get(r3) 就會過濾 hf1 。
ROWCOL 使用場景
假設有 2 個 Hfile 文件 hf1 和 hf2：
hf1 包含 kv1(r1 cf:q1 v)、kv2(r2 cf:q1 v)
hf2 包含 kv3(r1 cf:q2 v)、kv4(r2 cf:q2 v)
如果設置了 CF 屬性中的 bloomfilter 為 ROW，無論 get(r1,q1) 還是 get(r1,q2)，都會讀取 hf1+hf2；而如果設置了 CF 屬性中的 bloomfilter 為 ROWCOL，那么 get(r1,q1) 就會過濾 hf2，get(r1,q2) 就會過濾 hf1。
思考練習
Bloom Filter（BF）是一種空間效率很高的隨機數據結構，下面描述錯誤的是__
A. 它是一個判斷元素是否存在集合的概率算法
B. 判斷如果不在,集合肯定不在;如果在,集合有一定的概率判錯
C. 它支持從集合中刪除一個元素
D. Hash函數的選擇會影響到算法的效果
參考
https://www.shiyanlou.com/courses/37
https://blog.csdn.net/jiaomeng/article/details/1495500
http://edu.cda.cn/course/2239
https://www.cnblogs.com/z941030/p/9218356.html
https://developer.aliyun.com/article/683602
http://lxw1234.com/archives/2015/12/580.htm
