摘要：哈希函數與哈希表一哈希函數哈希函數性質輸入域是無窮的輸出域有窮的當輸入參數固定的情況下，返回值一定一樣當輸入不一樣，可能得到一樣的值。

input輸入域是無窮的

output輸出域有窮的

當輸入參數固定的情況下，返回值一定一樣

當輸入不一樣，可能得到一樣的值。(必然會出現，因為輸入域很大，輸出域很小)，產生哈希碰撞

均勻分布的特征，就相當于一個香水噴了房間，讓它自由的布朗運動，那么房間內就漫步了香水分子

Input計算哈希值后的結果都很大，但是如果把他們都與m取余，那么就在一個0-m-1的這個域(hashmap就是這樣找下標的)。如果在S域上是均勻分布的，那么在mod上0~m-1也是均勻分布的。

先將一個hash結果拆分兩個(高8位，低8位，是相互獨立的)得到兩個h1,h2，然后組合，如h1+i*h2 得到1000個哈希函數。

注意每個下標的鏈表是均勻往下漲的，哈希函數第五點性質

哈希表擴容(可以認為擴容代價為O(1)，因為優化技巧很多，實際數學上不是)：

假設一個哈希表長度為17，某個下標的個數為5，那么可以認為其他下標也放置了5個節點，假設效率不行，就需要擴容了。如擴容到104，那原來的mod（17）就失效了，

離線擴容就是原來的哈希表還在使用(用戶不需要等待擴容過程)，在后臺拿一個桶來，等數據都導入到新的桶，下一個請求就轉到新的桶。不存在在Java的JVM中(Java是用紅黑樹)。

Java中是怎么實現的呢？
一個桶，桶里放的是什么？不是鏈表而是紅黑樹treemap。是個平衡搜索二叉樹。

技巧：哈希函數做分流(利用哈希函數相同輸入相同輸出，不同輸入均勻分布的性質)
題目：假設有一個大文件(比如100T)，大文件里每行是個字符串，但是是無序的，把所有重復的字符串打印出來。
假設有1000臺機器，標號，0-999臺機器。大文件存儲在一個分布式文件上，按行讀取字符串 計算哈希值，mod1000，然后分到1000臺機器，相同的文本一定會分到一臺機器上(相同hash輸入，得到的結果一定是一樣的)。

題目：設計randomPool結構
題目內容：設計一種結構，在該結構中有如下三個功能：
insert(key):將某個key加入到該結構，做到不重復加入
delete(key):將原本在結構中的某個key移除，
getRandom():等概率隨機返回結構中的任何一個key
要求：三個方法的時間復雜度都是O(1)

解法：準備兩張hash表(一張hash表無法做到嚴格等概率隨機返回一個)

HashMap keyIndexMap = new HashMap();
HashMap indexKeyMap = new HashMap();

做法：
A 第0個進入hash表 ， 表A key A value 0 表B key 0 value A
B 第1個進入hash表 ， 表A key B value 1 表B key 1 value B
insert(key)代碼實現：

public void insert(String key){
    if(keyIndexMap.containsKey(key)){
        return;
    }else{
        keyIndexMap.put(key,number);
        indexKeyMap.put(number,key);
        number++;
    }
}

利用math的random函數，隨機從size取一個數字，在哈希表2取對應數字的key，就是隨機等概率的
getRandom()代碼實現：

public String getRandom(){
    if(size ==0){
        return null;
    }
    int index = (int)(Math.random()*size);
    return map2.get(index);
}

如果要remove呢？
直接remove會出現問題：刪除key對應要刪除某個index，那么就會產生“洞”，調用getRandom就一次調用得到等概率結果。
那么該如何去刪呢？
如假設有1000個key,要刪除str17，那么找到index17, 把str999在keyIndexMap的index變為17，map2的17改為str999，刪除index999的洞，即產生洞的時候刪除最后一條，再刪除函數需要刪除的key。通過交換最后一行數據保證index是連續的。

public void delete(String key){
    if(keyIndexMap.containsKey(key)){
        Integer deleteIndex = keyIndexMap.get(key);
        int lastIndex = --number;
        String lastKey = indexKeyMap.get(lastIndex);
        indexKeyMap.put(deleteIndex,lastKey);
        keyIndexMap.put(lastKey,deleteIndex);
        keyIndexMap.remove(key);
        indexKeyMap.remove(number);
    }
}

解決的問題：爬蟲去重問題。

黑名單問題(100億個url,每個url64字節，當用戶搜索某個url的時候，過濾。屬于黑名單返回true，不屬于返回false；用哈希表hashset做的話那么至少要6400億字節，實際還不止！640G放到內存耗費巨大代價；也可以用哈希分流給多個機器做，但是需要的機器較多)

布隆過濾器可能存在較低失誤率：可能會把清白的判斷為黑名單，但是只要是黑名單，必會判斷為黑名單。

因此，如果面試官問這種問題：可以先用哈希分流的方法回答，再則問面試官是否允許較低失誤率？如果允許的話，采用布隆過濾器。

布隆過濾器：比特數組
如 int[] arr = new int[1000]; 那么就有32000比特(int 4個字節 32位)
怎么給某個位的比特抹黑？

int index = 30000; //要描黑的位置
int intIndex = index/32;  //找打數組的下標
int bitIndex = index%32;  //下標對應元素的哪個位置應該被描黑
arr[intIndex] = (arr[intIndex] | (1<
黑名單應該怎么設計？
思路：url -> 計算哈希值，%m,得到的結果可以對應到0~m-1的位置，算到的地方描黑；
此時并不是布隆過濾器。
準備hash1,hash2,…,hashk 個哈希函數描黑(可能多個hash函數會到同一個位置,url描黑意味著這個url進到這個布隆過濾器)
比特數組應該盡可能大一些，不然小了一下就數組全描黑了
利用布隆過濾器判斷：來一個url，就在這k個hash函數得到K個位置，如果都是黑的，就是在黑名單，如有一個不是，就不在黑名單內。
解釋：如果url曾經進過，肯定都是黑的。有一個位置不是黑的，那肯定沒進過,就是白的。
失誤原因：

數組長度不夠！導致都是黑的。
正常非黑名單用戶可能結算的結果也對應在描黑位置

數組空間越大，失誤率越低。
哈希函數好處：數組空間開多大與單樣本的大小無關，而和url的樣本個數有關。
四、認識一致性哈希技術
幾乎集群都用到這個，需要抗壓服務器(牽扯，服務器設計，負載均衡)
服務器如何進行抗壓的呢？
如前端要存儲
做法：存儲的數據，計算哈希值%后臺服務器數，然后存到對應機器
前端計算分配到后臺服務器的數目會巨均衡。
問題：當想要加機器和減機器就出現問題了，因為%的服務器數目變了。
解決方法：通過一致性哈希就能解決問題，遷移成本低
通過機器的IP或者MAC來計算哈希的位置，劃分哈希值的環(把整個哈希結果想象成一個環)來管理。
存在問題：機器少的時候，不能均分這個哈希的環。有可能只有兩個機器的情況，兩個機器很近，負載很不均勻！
解決方法：虛擬節點技術
m - 1（分配1000個虛擬節點）:m - 1 - 1, m-1-2,m-1-3,m-1-4,.. 
m - 2:m-2-1,m-2-3,m-2-3,…
m - 3…
用這3000個虛擬節點搶這個環。搶到的給對應機器處理。這樣就比較均勻了。幾乎均分這個環。