摘要：哈希函數(shù)與哈希表一哈希函數(shù)哈希函數(shù)性質(zhì)輸入域是無窮的輸出域有窮的當(dāng)輸入?yún)?shù)固定的情況下，返回值一定一樣當(dāng)輸入不一樣，可能得到一樣的值。

input輸入域是無窮的

output輸出域有窮的

當(dāng)輸入?yún)?shù)固定的情況下，返回值一定一樣

當(dāng)輸入不一樣，可能得到一樣的值。(必然會(huì)出現(xiàn)，因?yàn)檩斎胗蚝艽螅敵鲇蚝苄?，產(chǎn)生哈希碰撞

均勻分布的特征，就相當(dāng)于一個(gè)香水噴了房間，讓它自由的布朗運(yùn)動(dòng)，那么房間內(nèi)就漫步了香水分子

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

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

注意每個(gè)下標(biāo)的鏈表是均勻往下漲的，哈希函數(shù)第五點(diǎn)性質(zhì)

哈希表擴(kuò)容(可以認(rèn)為擴(kuò)容代價(jià)為O(1)，因?yàn)閮?yōu)化技巧很多，實(shí)際數(shù)學(xué)上不是)：

假設(shè)一個(gè)哈希表長(zhǎng)度為17，某個(gè)下標(biāo)的個(gè)數(shù)為5，那么可以認(rèn)為其他下標(biāo)也放置了5個(gè)節(jié)點(diǎn)，假設(shè)效率不行，就需要擴(kuò)容了。如擴(kuò)容到104，那原來的mod（17）就失效了，

離線擴(kuò)容就是原來的哈希表還在使用(用戶不需要等待擴(kuò)容過程)，在后臺(tái)拿一個(gè)桶來，等數(shù)據(jù)都導(dǎo)入到新的桶，下一個(gè)請(qǐng)求就轉(zhuǎn)到新的桶。不存在在Java的JVM中(Java是用紅黑樹)。

Java中是怎么實(shí)現(xiàn)的呢？
一個(gè)桶，桶里放的是什么？不是鏈表而是紅黑樹treemap。是個(gè)平衡搜索二叉樹。

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

題目：設(shè)計(jì)randomPool結(jié)構(gòu)
題目?jī)?nèi)容：設(shè)計(jì)一種結(jié)構(gòu)，在該結(jié)構(gòu)中有如下三個(gè)功能：
insert(key):將某個(gè)key加入到該結(jié)構(gòu)，做到不重復(fù)加入
delete(key):將原本在結(jié)構(gòu)中的某個(gè)key移除，
getRandom():等概率隨機(jī)返回結(jié)構(gòu)中的任何一個(gè)key
要求：三個(gè)方法的時(shí)間復(fù)雜度都是O(1)

解法：準(zhǔn)備兩張hash表(一張hash表無法做到嚴(yán)格等概率隨機(jī)返回一個(gè))

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

做法：
A 第0個(gè)進(jìn)入hash表 ， 表A key A value 0 表B key 0 value A
B 第1個(gè)進(jìn)入hash表 ， 表A key B value 1 表B key 1 value B
insert(key)代碼實(shí)現(xiàn)：

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

利用math的random函數(shù)，隨機(jī)從size取一個(gè)數(shù)字，在哈希表2取對(duì)應(yīng)數(shù)字的key，就是隨機(jī)等概率的
getRandom()代碼實(shí)現(xiàn)：

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

如果要remove呢？
直接remove會(huì)出現(xiàn)問題：刪除key對(duì)應(yīng)要?jiǎng)h除某個(gè)index，那么就會(huì)產(chǎn)生“洞”，調(diào)用getRandom就一次調(diào)用得到等概率結(jié)果。
那么該如何去刪呢？
如假設(shè)有1000個(gè)key,要?jiǎng)h除str17，那么找到index17, 把str999在keyIndexMap的index變?yōu)?7，map2的17改為str999，刪除index999的洞，即產(chǎn)生洞的時(shí)候刪除最后一條，再刪除函數(shù)需要?jiǎng)h除的key。通過交換最后一行數(shù)據(jù)保證index是連續(xù)的。

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億個(gè)url,每個(gè)url64字節(jié)，當(dāng)用戶搜索某個(gè)url的時(shí)候，過濾。屬于黑名單返回true，不屬于返回false；用哈希表hashset做的話那么至少要6400億字節(jié)，實(shí)際還不止！640G放到內(nèi)存耗費(fèi)巨大代價(jià)；也可以用哈希分流給多個(gè)機(jī)器做，但是需要的機(jī)器較多)

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

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

布隆過濾器：比特?cái)?shù)組
如 int[] arr = new int[1000]; 那么就有32000比特(int 4個(gè)字節(jié) 32位)
怎么給某個(gè)位的比特抹黑？

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

數(shù)組長(zhǎng)度不夠！導(dǎo)致都是黑的。
正常非黑名單用戶可能結(jié)算的結(jié)果也對(duì)應(yīng)在描黑位置

數(shù)組空間越大，失誤率越低。
哈希函數(shù)好處：數(shù)組空間開多大與單樣本的大小無關(guān)，而和url的樣本個(gè)數(shù)有關(guān)。
四、認(rèn)識(shí)一致性哈希技術(shù)
幾乎集群都用到這個(gè)，需要抗壓服務(wù)器(牽扯，服務(wù)器設(shè)計(jì)，負(fù)載均衡)
服務(wù)器如何進(jìn)行抗壓的呢？
如前端要存儲(chǔ)
做法：存儲(chǔ)的數(shù)據(jù)，計(jì)算哈希值%后臺(tái)服務(wù)器數(shù)，然后存到對(duì)應(yīng)機(jī)器
前端計(jì)算分配到后臺(tái)服務(wù)器的數(shù)目會(huì)巨均衡。
問題：當(dāng)想要加機(jī)器和減機(jī)器就出現(xiàn)問題了，因?yàn)?的服務(wù)器數(shù)目變了。
解決方法：通過一致性哈希就能解決問題，遷移成本低
通過機(jī)器的IP或者M(jìn)AC來計(jì)算哈希的位置，劃分哈希值的環(huán)(把整個(gè)哈希結(jié)果想象成一個(gè)環(huán))來管理。
存在問題：機(jī)器少的時(shí)候，不能均分這個(gè)哈希的環(huán)。有可能只有兩個(gè)機(jī)器的情況，兩個(gè)機(jī)器很近，負(fù)載很不均勻！
解決方法：虛擬節(jié)點(diǎn)技術(shù)
m - 1（分配1000個(gè)虛擬節(jié)點(diǎn)）: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個(gè)虛擬節(jié)點(diǎn)搶這個(gè)環(huán)。搶到的給對(duì)應(yīng)機(jī)器處理。這樣就比較均勻了。幾乎均分這個(gè)環(huán)。