算法练习day12——190331（哈希函数、哈希表、布隆过滤器、一致性哈希）
1.哈希函數(shù)
1.1 特點(diǎn)：
- 可用來打亂輸入規(guī)律，輸出的規(guī)律和輸入規(guī)律是沒有關(guān)系的。
- 若輸出在整個(gè)輸出域上均勻分布，那么輸出mod m之后得到的結(jié)果在0~m-1上也是均勻分布的。
1.2 由給定的一個(gè)哈希函數(shù)得到1000個(gè)互相獨(dú)立的哈希函數(shù)
假設(shè)給定哈希函數(shù)h，它的輸出是16位的。
將其高8位作為h1，低8位作為h2。h1和h2相互獨(dú)立，因?yàn)?6位輸出中的每一位都和其他位無關(guān)。
那么，可構(gòu)造：
- ...
構(gòu)造的多個(gè)哈希函數(shù)之間是相互獨(dú)立的。
2.哈希表
2.1 put(K,V)
hashCode(K)-->h1
將(K,V)放到下標(biāo)為h1的桶中：
- 若桶不空，則判斷有無K；
- 有，V若不等，則更新V；
- 無，直接將(K,V)鏈在此桶元素的后面。
若桶中的鏈較長，需要擴(kuò)容。
重新以新容量進(jìn)行hashCode的運(yùn)算。
各種操作都是級別的。即使擴(kuò)容操作費(fèi)時(shí)，但這操作不頻繁，也可以押得很低。（還可在離線的時(shí)候進(jìn)行擴(kuò)容，不占用在線時(shí)間）。
JVM中每個(gè)桶中放的是一棵紅黑樹。不太需要擴(kuò)容。
有一個(gè)100T的大文件，其中每一行存的是一個(gè)字符串，去掉其中重復(fù)的字符串。假設(shè)可用的機(jī)器為1000臺。
具體做法：
用哈希函數(shù)作分流——讀出每一行字符串，然后進(jìn)行hashCode計(jì)算，之后模1000。這樣相同的字符串就會分配到同一臺機(jī)器。——利用哈希函數(shù)可以將100T大文件中的字符串（假設(shè)M種 ）按種類平均分配到1000臺機(jī)器上。
3.設(shè)計(jì)RandomPool結(jié)構(gòu)
【題目】 設(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。
【要求】 Insert、 delete和getRandom方法的時(shí)間復(fù)雜度都是O(1)
3.1 分析
哈希表的結(jié)構(gòu)中：
- 若數(shù)據(jù)量較少，有的桶可能會沒元素，此時(shí)無法做到均勻取出（遍歷取出的話，復(fù)雜度會達(dá)到O(N)）
- 若數(shù)據(jù)量較多，每個(gè)桶中的鏈長度也不是絕對相等的。無法做到等待率。
本題中使用兩個(gè)哈希表map1和map2實(shí)現(xiàn)。
比如A元素是第0個(gè)進(jìn)來的，那么:
- 在map1中就存（A,0）——A是第0個(gè)進(jìn)來的；
- 在map2中存（0,A）——第0個(gè)進(jìn)來的是A。
同時(shí)需要有個(gè)int型的變量記錄某個(gè)元素是第幾個(gè)進(jìn)來的。
3.1.1 先考慮add()，忽略remove()。
- 若目前進(jìn)來了26個(gè)元素，size=26，此時(shí)調(diào)用了getRandom()：
- 使用Math.random()*size生成0~25中隨機(jī)一個(gè)數(shù)indexm；
- 然后在map2中由Key=index找到對應(yīng)的value，返回 。
3.2.1 remove()
若刪除時(shí)不做任何操作，則在刪除之后，會產(chǎn)生多個(gè)“洞”，使得在計(jì)算index時(shí)無法做到等概率，因?yàn)槟承┪恢蒙蠜]元素。
假設(shè)有1000條記錄（str0~str999），現(xiàn)在要?jiǎng)h除str17，在刪除時(shí)：
- map1中：將str999放在str17的位置（即，將自己的value改為17即可）；
- map2中：將str999放在17的位置上（即，將自己的key改為17即可，也就是將17對應(yīng)的value由str17改為str999）；
- 刪除map1和map2中的最后一條記錄;
- size-1=999.
保證了存儲數(shù)據(jù)位置的連續(xù)。
3.2 代碼實(shí)現(xiàn)
package Hash;import java.util.HashMap;public class RandomPoolTest {public static class RandomPool{HashMap<String,Integer> map1;HashMap<Integer,String> map2;int size;public RandomPool() {this.map1=new HashMap<>();this.map2=new HashMap<>();this.size=0;}public void insert(String str) {if(!this.map1.containsKey(str)) {this.map1.put(str, this.size);this.map2.put(this.size, str);this.size++;}}public void delete(String str) {if(this.map1.containsKey(str)) {int index=this.map1.get(str);String laststr=this.map2.get(--this.size);this.map1.put(laststr, index);this.map2.put(index, laststr);this.map1.remove(str);this.map2.remove(index);size--;}}public String getRandom() {if(size==0)return null;int index=(int)(Math.random()*size);return this.map2.get(index);}} }4.布隆過濾器
4.1 簡介
應(yīng)用場景：判斷某一個(gè)東西是否在一個(gè)集合中（布隆過濾器本身就是一個(gè)集合）
舉例：看一個(gè)url是否在已有的黑名單（100億個(gè)64字節(jié)的url）中，在返回true，不在返回false。
若使用哈希函數(shù)，不存value，則使用HashSet，最起碼需要6400億字節(jié)（640G）才能把所有的黑名單url裝下。
缺點(diǎn)：有失誤率
- 若一個(gè)url確實(shí)屬于黑名單，則它肯定返回true；
- 若一個(gè)url不在黑名單中，可能返回true，也可能返回false。
布隆過濾器是一個(gè)比特類型的map
int[] arr=new int[1000]; //一個(gè)整型是4個(gè)字節(jié)，32個(gè)比特，則int[] arr=new int[1000];一句申請了32000個(gè)比特位int index=30000;int intIndex=index/32;//由除數(shù)定位到給定的數(shù)在哪個(gè)桶中（一個(gè)桶32bit） int bitIndex=intIndex%32;//由余數(shù)定位到給定的數(shù)在桶中的具體哪個(gè)比特位上 arr[intIndex]=arr[intIndex]|(1<<bitIndex);1左移16位=num——>只有第16位上為1，其余為0；
arr[937]和num進(jìn)行或運(yùn)算，則num的第16位就置為1了——表示30000這個(gè)值在集合中存在了。
怎么得到比特?cái)?shù)組？
用基礎(chǔ)類型拼，類似于前面的int[1000]——32000個(gè)比特位;
若給定的index太大，可換為long[1000]——64000個(gè)比特位；
若還是很大，可換為long[1000][1000]——1000*1000*64個(gè)比特位。
4.2 上面黑名單的實(shí)現(xiàn)
4.2.1 分析
一個(gè)url進(jìn)入布隆過濾器的過程：
- 先使用哈希函數(shù)h將url變?yōu)橐粋€(gè)hashcode，
- 然后hashcode%m得到一個(gè)范圍在0~m-1的值；
- 將得到的值對應(yīng)于數(shù)組的位置上的值置為1.
- 布隆過濾器是使用k個(gè)哈希函數(shù)h1~hk，計(jì)算k個(gè)hashcode，將得到的k個(gè)位置上的值置為1.
查一個(gè)url是否在黑名單中：
- 將這個(gè)url進(jìn)入k個(gè)哈希函數(shù)的運(yùn)算，得到k個(gè)值；
- 在給定的數(shù)組中查看這k個(gè)值對應(yīng)的位置是否都為1；
- 若都為1，返回true；
- 否則返回false。
數(shù)組范圍應(yīng)長一點(diǎn)，要不100億個(gè)url進(jìn)去之后，幾乎所有的位置都已置為1了，無法查詢——所有的url查詢都會返回true。
- 空間越大，失誤率越低；
- 空間越小，失誤率越高。
哈希函數(shù)的個(gè)數(shù)k，只和url個(gè)數(shù)有關(guān)系，和url具體大小，多少字節(jié)無關(guān)。
比特?cái)?shù)組大小m的計(jì)算公式：
- n：樣本量——100億；
- p：預(yù)期失誤率——萬分之一0.0001
- m：單位是bit，算出來小數(shù)的話，向上取整。
k也是向上取整
當(dāng)k和m向上取整之后，真實(shí)的錯(cuò)誤率為：
【當(dāng)給定題目后，首先給出經(jīng)典解法，——占用空間太大——允不允許失誤率？——允許——講解布隆過濾器、算出m（在給定范圍內(nèi)盡量大）,K，再算出真正的失誤率，比給定的失誤率要低——】
若在乎I/O，則將m內(nèi)存分布式存儲；
5.一致性哈希
5.1 經(jīng)典服務(wù)器抗壓結(jié)構(gòu)
當(dāng)需要加減機(jī)器的時(shí)候，這個(gè)結(jié)構(gòu)就不合適了。所有已存儲的數(shù)據(jù)歸屬全變了。
——引入了一致性哈希結(jié)構(gòu)
5.2 一致性哈希
可降低數(shù)據(jù)遷移的代價(jià)，同時(shí)又負(fù)載均衡。
將哈希函數(shù)的返回值（）想象為一個(gè)環(huán)：
有3臺機(jī)器m1、m2、m3，假設(shè)它們是以IP進(jìn)行區(qū)分的。
- 將m1、m2、m3的IP串經(jīng)過哈希運(yùn)算，對應(yīng)到環(huán)上一點(diǎn)。
假設(shè)存儲(zuo,31)，將zuo 進(jìn)行哈希運(yùn)算后，不用進(jìn)行模運(yùn)算，直接對應(yīng)到環(huán)上一點(diǎn)：
順時(shí)針找到離zuo在環(huán)上這一點(diǎn)最近的機(jī)器（m2），將（zuo,31）存儲在此機(jī)器上。
查的時(shí)候也一樣。
5.2.1 實(shí)現(xiàn)
后端還是三臺機(jī)器，前端還是無差別的負(fù)載服務(wù)器。
將m1、m2、m3的哈希值排序（有小到大）后組成一個(gè)數(shù)組{m1,m2,m3}，將這個(gè)數(shù)組存到前端的每一個(gè)服務(wù)器中。
當(dāng)zuo進(jìn)來后，以二分查找的方式確定它在那個(gè)機(jī)器上：
- 知道第一個(gè)大于等于zuo的哈希值的機(jī)器哈希值（以順時(shí)針選的機(jī)器）。
現(xiàn)在需要添加一個(gè)機(jī)器m4，將它的IP經(jīng)過哈希運(yùn)算映射到如圖所示的點(diǎn)中：
則需要做數(shù)據(jù)遷移的部分如圖所示：
哈希函數(shù)的性質(zhì)保證的是：量多的情況下，機(jī)器數(shù)據(jù)量均分。
這種結(jié)構(gòu)存在的問題是，機(jī)器負(fù)載會不均衡。
虛擬節(jié)點(diǎn)技術(shù)可以解決這個(gè)問題。
5.3 虛擬節(jié)點(diǎn)技術(shù)
有三臺機(jī)器：m1、m2、m3
給每個(gè)節(jié)點(diǎn)分配1000個(gè)虛擬節(jié)點(diǎn)：
- m1：m1-1，m1-2，m1-3，...
- m2：...
- m3：...
準(zhǔn)備一個(gè)物理映射表：
- 可以從表中得知一個(gè)機(jī)器有哪些節(jié)點(diǎn)；
- 也可知道一個(gè)節(jié)點(diǎn)屬于哪個(gè)機(jī)器。
令這3000個(gè)虛擬節(jié)點(diǎn)搶環(huán)上的位置，由虛擬節(jié)點(diǎn)負(fù)責(zé)的域，實(shí)際上是讓它屬于的實(shí)際機(jī)器去處理。——這樣就使得三臺機(jī)器負(fù)責(zé)的區(qū)域是差不多的。
加機(jī)器m4時(shí)，它也擁有1000個(gè)虛擬節(jié)點(diǎn)，這些虛擬節(jié)點(diǎn)進(jìn)環(huán)，瓜分之前節(jié)點(diǎn)的負(fù)責(zé)的區(qū)域。
淡化物理機(jī)器的概念，強(qiáng)調(diào)虛擬節(jié)點(diǎn)的概念。
5.5 應(yīng)用場景
用到集群特性，抗壓的
?
?
?
總結(jié)
以上是生活随笔為你收集整理的算法练习day12——190331（哈希函数、哈希表、布隆过滤器、一致性哈希）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 算法练习day11——190329（平衡
- 下一篇： 算法练习day12——190331（并查