深入拆解：Hash函數、Bitmap位圖、BloomFilter布隆過濾器

Hash函數

byte[] hash(String inData)

hash函數的特點：

（1）輸入域可以是無窮大的。

（2）輸出域是有限的，比如輸出長度固定為64bit、128bit、256bit、512bit等等，以達到壓縮資料、提取指紋的目的。

（3）沒有任何随機機制，相同的輸入得到相同的輸出。

（4）有可能出現輸入不同輸出相同（Different in–>Same out），這種情況叫做哈希碰撞。

（5）最重要的特點：輸出值盡可能均勻散列（離散性和均勻性，其實是一回事）到輸出域上。

- 輸入的微小差别，在結果集上會放大到相隔很遠；

- 結果集近乎均勻分布。

（6）結果集模一個數M（%），取模的結果在0~M-1上也會比較均勻地分布；

（7）如果因為結果集有限發生大量碰撞，則碰撞的“厚度”也是幾乎相等的；

常見的hash函數：

md5

sha1

通過位運算（取模、移位、異或），以及乘以一個素數等方式，實作的哈希函數。

HashMap put時間複雜度分析

一般認為，HashMap的put和get、remove操作時間複雜度都是O(1)，即常數時間複雜度。

可能有人會說，不對呀，比如put操作的時候，HashMap容量不夠會有擴容操作，将會重新計算已放入Map中資料的Key的hash值。

好，我們以put操作為例，來分析擴容操作的整體時間複雜度。

假設一開始容量為1，分析連續put進N條不同記錄的情況。容量不夠的話，容量擴大到原來的2倍。
擴容操作總共進行log2(N)次。
第一擴容需要重新計算hash的次數為1，
第二次，為2
第三次，為4
...
第logN次，為N/2。
總共為（1+2+4+...+N/4+N/2）≈ N
           

即放入N個元素，總共的擴容操作是額外計算N次hash值？，是以平均到每一次是O(1)。

Bitmap位圖

計算機中最小的資訊機關是比特(bit)。一個bit中隻能是0或者1，如果用0代表false，1代表true的話，用1個bit就能夠代表某個事物是否出現過。這樣用M個比特就能夠表達M個事物是否出現過。

這就是位圖，通過查找某個bit是1還是0，來表達是出現過，還是沒出現過。

這樣做的好處是，能夠以極低的存儲空間表達很大的資料量（M可以很大）。

舉個例子，1G大概是10億bit，那麼100億的資料，隻需要10G。

BloomFilter布隆過濾器

布隆過濾器：類似于黑名單，是沒有删除行為的黑名單。

預期資料量的上限為n，可以接受的誤判率為p。

則可以算出需要的bit數m，以及需要的獨立hash函數個數。

（未完待續）