本文主要作為自己的學(xué)習(xí)筆記暇屋，并不具備過(guò)多的指導(dǎo)意義。

哈希函數(shù)

哈希函數(shù)

1. 輸入域無(wú)窮大
2. 輸出域有邊界(1<<64)
3. 輸入相同的樣本撞牢，一定得到相同的輸出結(jié)果
4. 不同的樣本，有可能發(fā)生碰撞(結(jié)果相同)
5. 在輸入源樣本量足夠大的情況下叔营，結(jié)果將在輸出域上均勻分布屋彪。

哈希函數(shù)的離散性,能夠打亂樣本規(guī)律。

哈希函數(shù)實(shí)現(xiàn)的方式

通過(guò)大量的異或绒尊，交換畜挥。打亂原本的樣本結(jié)構(gòu)，放大樣本差異婴谱。

生成不相關(guān)的hash函數(shù)

正常一個(gè)hash函數(shù)的結(jié)果h為16字節(jié)蟹但，每個(gè)字節(jié)為一個(gè)16進(jìn)制(0_9,af中的)的任意值躯泰。將前8為作為h1，后8位作為h2华糖。

通過(guò)h1 + k * h2生成一個(gè)新的結(jié)果麦向。并且他將于原本的h無(wú)關(guān)。

哈希函數(shù)特性的使用

大任務(wù)(hash % n)分流成N個(gè)小任務(wù)客叉。

經(jīng)典哈希表

經(jīng)典的哈希表結(jié)構(gòu)通過(guò)數(shù)組+鏈表的結(jié)構(gòu)實(shí)現(xiàn)

哈希表的結(jié)構(gòu)

哈希表的本質(zhì)是一個(gè)數(shù)組诵竭，數(shù)組中每一個(gè)元素稱為一個(gè)箱子(bin)，箱子中存放的是鏈表兼搏，鏈表節(jié)點(diǎn)中存放的鍵值對(duì)卵慰。

哈希表存儲(chǔ)的過(guò)程

1. 根據(jù) key 計(jì)算出它的哈希值 h。
2. 假設(shè)箱子的個(gè)數(shù)為 n佛呻，那么這個(gè)鍵值對(duì)應(yīng)該放在第 (h % n) 個(gè)箱子中裳朋。
3. 哈希值h相同，通過(guò)鏈表存儲(chǔ)在同一個(gè)箱子中吓著。

自動(dòng)擴(kuò)容

當(dāng)哈希表的效率因數(shù)組量過(guò)大造成損耗鲤嫡，進(jìn)行擴(kuò)容并重新簡(jiǎn)歷哈希表

1. 當(dāng)某一個(gè)鏈表上的節(jié)點(diǎn)個(gè)數(shù)超過(guò)某個(gè)系數(shù)(負(fù)載因子)，將進(jìn)行擴(kuò)容夜矗。
2. 擴(kuò)容可以是離線的(在非活躍狀態(tài)下進(jìn)行擴(kuò)容泛范，重建哈希表，重建結(jié)束后再使用新的哈希表)

增刪改查的時(shí)間復(fù)雜度

對(duì)key進(jìn)行hash紊撕，通過(guò)下標(biāo)尋址罢荡，查找一個(gè)短鏈表均為常數(shù)時(shí)間操作。

時(shí)間復(fù)雜度===》O(1)

設(shè)計(jì)RandomPool結(jié)構(gòu)

【題目】 設(shè)計(jì)一種結(jié)構(gòu)对扶，在該結(jié)構(gòu)中有如下三個(gè)功能：

1. insert(key)：將某個(gè)key加入到該結(jié)構(gòu)恐似，做到不重復(fù)加入。

2. delete(key)：將原本在結(jié)構(gòu)中的某個(gè)key移除崩溪。

3. getRandom()： 等概率隨機(jī)返回結(jié)構(gòu)中的任何一個(gè)key尾膊。

【要求】 Insert、delete和getRandom方法的時(shí)間復(fù)雜度都是 O(1)

需要的結(jié)構(gòu)：

兩個(gè)哈希表络凿，一個(gè)size變量計(jì)數(shù)

每次添加一個(gè)新的key23：

1. 令size+1
2. 將key23作為key骡送，size作為value，記錄在第一個(gè)hashMap中
3. 將size作為key絮记，key23作為value摔踱，記錄在第二個(gè)haskMap中

讀取隨機(jī)key時(shí)，在第二個(gè)hashMap中用(1~size)作為key進(jìn)行查詢返回

image

刪除key時(shí)怨愤，將末尾元素與刪除元素的index互換派敷，刪除該元素。并將size-1。

image

布隆過(guò)濾器BloomFilter

布隆過(guò)濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中篮愉。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都比一般的算法要好的多腐芍，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。

可以解決爬蟲(chóng)去重试躏，黑名單問(wèn)題猪勇。

實(shí)現(xiàn)一個(gè)bit類型數(shù)組，將數(shù)據(jù)容量擴(kuò)容

1. 建立一個(gè)[基礎(chǔ)類型]類型的數(shù)組
2. 一個(gè)Int類型可以表示成32bit的二進(jìn)制數(shù)據(jù)冗酿，long類型則是64bit
3. 一個(gè)[Int]數(shù)組將是普通數(shù)組的32倍容量

以一個(gè)100長(zhǎng)度的Int數(shù)組([bit]長(zhǎng)度為3200)arr為例埠对，當(dāng)我們想修改第3000個(gè)bit：

1. 3000/32獲得arr組的indexI

2. 3000%32獲得arr[indexI]下，[bit]想要修改的indexB

3. 通過(guò)arr[indexI] = (arr[IndexI] | (1 << indexB))進(jìn)行修改

   1左移indexB個(gè)位置裁替，將會(huì)變成00000010000這種形式项玛。然后與原本的arr[IndexI]相交，對(duì)應(yīng)位置將會(huì)被修改為1

可以用矩陣弱判，將數(shù)據(jù)容量繼續(xù)擴(kuò)容

以Int數(shù)組為例

[1000]的數(shù)組可以代表3200個(gè)bit位

[1000][1000]的矩陣則可以代表3200*1000個(gè)bit位

布隆過(guò)濾器的實(shí)現(xiàn)

1. 準(zhǔn)備一個(gè)長(zhǎng)度為m的數(shù)組襟沮，通常是bit數(shù)組
2. 將指定的key用一個(gè)hash函數(shù)求出hash值
3. 將hash % m 確定一個(gè)位置，并將該位置從0修改成1
4. 重復(fù)用k不相關(guān)個(gè)hash函數(shù)昌腰，確定多個(gè)位置并修改成1

經(jīng)過(guò)這個(gè)處理之后的數(shù)組开伏，就是布隆過(guò)濾器。

5. 當(dāng)一個(gè)新的key進(jìn)行查詢時(shí)遭商，也通過(guò)多次hash計(jì)算固灵，確定是否存在于布隆過(guò)濾器

布隆過(guò)濾器的誤差

由于數(shù)組長(zhǎng)度的限制，有可能導(dǎo)致描黑位置過(guò)多劫流，導(dǎo)致失誤命中概率過(guò)高巫玻。

通過(guò)調(diào)整hash函數(shù)個(gè)個(gè)數(shù)k，以及數(shù)組長(zhǎng)度m祠汇∪猿樱可以得到不同的失誤率。

布隆過(guò)濾器的優(yōu)勢(shì)

由于內(nèi)部通過(guò)hash函數(shù)定位可很，最終過(guò)濾器所占內(nèi)存的大小與單樣本的內(nèi)存大小無(wú)關(guān)诗力。

比如一個(gè)長(zhǎng)度為1000000的字符串，也并不需要存進(jìn)數(shù)組我抠。只需要在數(shù)組中修改k個(gè)位置即可苇本。

布隆過(guò)濾器長(zhǎng)度公式

[bit]的長(zhǎng)度m，樣本量n菜拓，預(yù)期失誤率p瓣窄，ln是自然對(duì)數(shù)

image

布隆過(guò)濾器hash函數(shù)個(gè)數(shù)公式

image

布隆過(guò)濾器真是失誤率

當(dāng)m和k確定之后的失誤率

image

經(jīng)典服務(wù)器抗壓結(jié)構(gòu)

通過(guò)對(duì)key進(jìn)行hash % n 可以將讀寫(xiě)的壓力均勻的分布給三個(gè)服務(wù)器

image

而這種結(jié)構(gòu)，當(dāng)加入新的服務(wù)器或減少原有的服務(wù)器尘惧。我們需要像hashMap的自動(dòng)擴(kuò)容一樣需要重建整個(gè)映射康栈。

一致性哈希

經(jīng)典抗壓結(jié)構(gòu)在擴(kuò)容時(shí)递递，需要對(duì)數(shù)據(jù)做全量遷移喷橙，計(jì)算每一條數(shù)據(jù)的歸屬啥么。

一致性哈希可以降低數(shù)據(jù)遷移的代價(jià)贰逾，同時(shí)保證負(fù)載均衡悬荣。

正常的工作流程

1. 根據(jù)關(guān)鍵信息計(jì)算出三個(gè)負(fù)載服務(wù)器的hashCode：h1,h2,h3。
2. 將三個(gè)值交由前方的前段服務(wù)器持有
3. 當(dāng)進(jìn)行讀寫(xiě)操作時(shí)疙剑，對(duì)key進(jìn)行hash氯迂，用二分的方式尋找順時(shí)針?lè)较蜃罱呢?fù)載服務(wù)器并交付。

image

數(shù)據(jù)遷移的流程

只需要將黑色部分?jǐn)?shù)據(jù)從1號(hào)服務(wù)器遷移給4號(hào)服務(wù)器即可言缤。

image

虛擬節(jié)點(diǎn)技術(shù)

通過(guò)將每個(gè)服務(wù)器分配N個(gè)虛擬節(jié)點(diǎn)映射嚼蚀，讓整個(gè)環(huán)上的分割區(qū)域約等于平均。

參考資料

左神牛課網(wǎng)算法課