哈希函數(shù)與哈希表
哈希函數(shù)的性質(zhì)
哈希函數(shù)又叫散列函數(shù)，例如MD5,SHA1等错敢，哈希函數(shù)具有以下特性：
- 一個(gè)哈希函數(shù)的輸入域是無窮大的
- 一個(gè)哈希函數(shù)的輸出域雖然很大纸淮，但是是有限的
例如MD5輸出的hashcode為16位的16進(jìn)制數(shù)咽块，則MD5的輸出域S表示的范圍為：0~2^64-1 - 相同的輸入具有相同的輸出
即：same input , same output
例如：一個(gè)哈希函數(shù)接收一個(gè)字符串
那么有：h("A") = h("A") - 哈希碰撞
輸入不同糜芳，但有可能得到相同的輸出
試想峭竣，一個(gè)哈希函數(shù)的輸入域無窮大但輸出域有固定范圍皆撩，那么必然會有幾個(gè)不同的輸入可能返回一樣的輸出扛吞，這種情況叫做哈希碰撞或哈希沖突 - 哈希函數(shù)的離散型
假設(shè)有一樣本量是0~998的999個(gè)整數(shù)滥比，現(xiàn)有一哈希函數(shù)盲泛，輸出域固定為[0,2],那么每個(gè)樣本經(jīng)過哈希函數(shù)后得到的值會大致平均落在輸出域上寺滚，即：
落在0上的樣本有33個(gè)左右
落在1上的樣本有33個(gè)左右
落在2上的樣本有33個(gè)左右
這就叫做哈希函數(shù)的離散型
通過哈希函數(shù)具有離散性可以知道官套，哈希函數(shù)的輸入和輸出是無關(guān)的奶赔，如果輸入和輸出相關(guān)杠氢，那么結(jié)果必然不是離散的修然。所以即便是兩個(gè)很相近的輸入也有可能得到相差很大的輸出，所以利用哈希函數(shù)的離散性结榄，可以打亂輸入規(guī)律臼朗。
根據(jù)哈希函數(shù)的離散性還可以推出视哑，如果對所有輸入經(jīng)過hash函數(shù)得到的hashcode取模即：hashcode%M挡毅，那么在[0,M-1]這個(gè)域上結(jié)果也是均勻分布的。
哈希表
哈希表的本質(zhì)是“桶”取逾，對于哈希表而言砾隅，增刪改查操作都是O(1)的時(shí)間復(fù)雜度晴埂，經(jīng)典結(jié)構(gòu)的哈希表使用了鏈地址法來解決哈希沖突的問題
鏈地址法
對于一個(gè)輸入邑时，通過hash函數(shù)求出它所對應(yīng)的hashcode后再取模晶丘，那么結(jié)果所對應(yīng)的值就會落到[0,M-1]這個(gè)區(qū)間內(nèi)浅浮。
鏈地址法的本質(zhì)就是"數(shù)組+鏈表",數(shù)組中存儲的是一個(gè)個(gè)Node,如果出現(xiàn)了哈希沖突,那么就將沖突的值掛在鏈表的后面。
假設(shè)輸入i1落到了2這個(gè)位置上淮捆，i2落到了3的位置桐腌，i3算出hashcode并取模后為2案站，發(fā)生哈希沖突蟆盐，解決辦法就是將沖突的值添加到鏈上石挂。
那么哈希表是如何做到增刪改查為O(1)的時(shí)間復(fù)雜度誊稚？我們說過城瞎，哈希表是一個(gè)離散表脖镀，當(dāng)樣本量足夠大且某個(gè)鏈的長度達(dá)到一定的值蜒灰，比如說這個(gè)值為10强窖，那么我就可以認(rèn)為翅溺，每個(gè)鏈的平均長度都達(dá)到了10左右咙崎，這個(gè)時(shí)候再向哈希表中put元素效率就會變差褪猛，此時(shí)對數(shù)組進(jìn)行擴(kuò)容操作伊滋。擴(kuò)容后笑旺，"桶"的數(shù)量增加燥撞，但是也要相對付出擴(kuò)容代價(jià)，因?yàn)樵竟１砩蠏斓拿總€(gè)值都要重新模上擴(kuò)容后數(shù)組的長度再重新分配到新的表上戏锹。
java中的哈希表
Java中的HashMap的結(jié)構(gòu)本質(zhì)上是數(shù)組+TreeMap锦针，也就是數(shù)組上掛的是一個(gè)個(gè)紅黑樹悉盆。
Java8以前，哈希表的結(jié)構(gòu)為數(shù)組+鏈表脚翘，在Java8以后来农，當(dāng)裝載因子(數(shù)組承載的鏈表的長度)達(dá)到一定的閾值后沃于，每個(gè)位置從鏈表進(jìn)化成紅黑樹，這個(gè)閾值為8饿肺。
開放地址法
開放地址法可以做到所有輸入的元素全部盛放在桶中雪标，也就是說桶上面不需要掛鏈表或者紅黑樹村刨，裝載因子不會超過1嵌牺。
開放地址法的基本思路為：當(dāng)發(fā)生哈希沖突逆粹，根據(jù)再尋址的方法即僻弹，以當(dāng)前地址為基準(zhǔn)蹋绽，繼續(xù)探測哈希表中的其他存儲單元退敦，直到找到空位置為止。
HashMap的增刪改查
Java 中 HashMap 的增刪改查
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map.Entry;
public class HashMapTest {
public static void main(String[] args){
HashMap<String,Integer> hashMap = new HashMap<>();
hashMap.put("kim",25);
// 新的value值會覆蓋掉原來的value值
hashMap.put("kim",26);
hashMap.put("dog",2);
hashMap.put("cat",2);
hashMap.put("gary",39);
hashMap.put("laowang",27);
hashMap.put("laozhang",28);
// 是否存在 key: hashMap.containsKey(key)
System.out.println(hashMap.containsKey("kim"));
System.out.println("========================");
// 獲取key對應(yīng)的value值: value = hashMap.get(key)
System.out.println(hashMap.get("kim"));
System.out.println("========================");
// isEmpty & size
System.out.println(hashMap.isEmpty());
System.out.println(hashMap.size());
System.out.println("========================");
// 從哈希表中刪除key和value: hashMap.remove(key),返回刪除的key對應(yīng)的value
System.out.println(hashMap.remove("laozhang"));
System.out.println(hashMap.containsKey("laozhang"));
System.out.println(hashMap.size());
System.out.println("========================");
// 遍歷
// 遍歷hashMap中所有的key
for(String key : hashMap.keySet()){
System.out.print(key + " ");
}
System.out.println();
System.out.println("========================");
// 遍歷hashMap中所有的value
for(Integer value : hashMap.values()){
System.out.print(value + " ");
}
System.out.println();
System.out.println("========================");
// 遍歷hashMap中所有的 key 和 value
for(Entry<String,Integer> entry : hashMap.entrySet()){
System.out.println("key:"+entry.getKey()+" value:"+entry.getValue());
}
System.out.println("========================");
// 批量刪除,本示例中為刪除所有value為 2 的元素
List<String> removeKeys = new ArrayList<>();
for(Entry<String,Integer> entry : hashMap.entrySet()){
if(entry.getValue().equals(2)){
removeKeys.add(entry.getKey());
}
}
for(String removeKey:removeKeys){
hashMap.remove(removeKey);
}
for(Entry<String,Integer> entry : hashMap.entrySet()){
System.out.println("key:"+entry.getKey()+" value:"+entry.getValue());
}
}
}
hash的應(yīng)用-海量數(shù)據(jù)分流處理
對于一個(gè)大流量請求時(shí)，通過hash函數(shù)可以將流量分流到幾個(gè)服務(wù)器進(jìn)行處理，因?yàn)閔ash函數(shù)具有離散性战虏，所以我們認(rèn)為每個(gè)服務(wù)器是負(fù)載均衡的烦感。
但是這樣做也有缺點(diǎn)手趣，如果說某一臺服務(wù)器出現(xiàn)了故障或者說需要新添加一臺服務(wù)器，那么就需要重新去計(jì)算每一個(gè)請求的key的哈希值肥荔，這樣一來绿渣，大量的key會被重新定位到不同的服務(wù)器而造成大量的緩存不命中。一致性哈希則能有效解決此類問題燕耿，本文后面有具體的介紹中符。
(以上內(nèi)容參考了文章:海量數(shù)據(jù)分流處理-------一致性哈希算法)
哈希表相關(guān)題目
設(shè)計(jì)一種 RandomPool 結(jié)構(gòu)
設(shè)計(jì)一種結(jié)構(gòu)，在該結(jié)構(gòu)中有如下三種功能：
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)
當(dāng)看到插入胀瞪，刪除，查詢的操作均為O(1)時(shí)轴咱，我們就想到了使用哈希表去實(shí)現(xiàn)RandomPoll結(jié)構(gòu)戈稿，思路如下：
使用兩個(gè)哈希表和一個(gè)size變量般甲，map1存儲的key和value類型分別為K和Integer,map2存儲的key和value類型分別為Integer和K。
當(dāng)向RandPool結(jié)構(gòu)中插入數(shù)據(jù)時(shí)挽牢，兩表同時(shí)put相應(yīng)的數(shù)據(jù)和索引，變量size++;
當(dāng)執(zhí)行g(shù)etRandom操作返回一個(gè)隨機(jī)的key時(shí)，通過Math.random確定隨機(jī)數(shù)豁辉，這個(gè)隨機(jī)數(shù)即對應(yīng)map2中的key,隨之返回map2中的value即可;
當(dāng)執(zhí)行delete操作時(shí)餐抢，如圖所示:
依次向哈希表中 put 進(jìn) A~Z 26 個(gè)字符串苦蒿。假設(shè)現(xiàn)在要?jiǎng)h除的key為“C”
如果刪除了("C",3)這樣一組元素报强，那么在hashmap上面就會出現(xiàn)“空洞”，這樣就無法做到可以等概率隨機(jī)返回此結(jié)構(gòu)中的任何一個(gè)key了，解決方案如下：
即淳玩，將“最后一個(gè)元素”覆蓋掉刪除的元素承匣，這樣哈希表就可以保證連貫性宽闲。具體實(shí)現(xiàn)代碼如下：
import java.util.HashMap;
public class RandPoolProblem {
public static class Pool<K>{
private HashMap<K,Integer> map1;
private HashMap<Integer,K> map2;
private int size;
public Pool(){
this.map1 = new HashMap<>();
this.map2 = new HashMap<>();
this.size = 0;
}
public void insert(K key){
if(!map1.containsKey(key)){
map1.put(key,size);
map2.put(size,key);
size++;
}
}
public void delete(K key){
if(map1.containsKey(key)){
int delIndex = map1.get(key);
int lastIndex = --size;
K lastKey = map2.get(lastIndex);
map1.put(lastKey,delIndex);
map2.put(delIndex,lastKey);
map1.remove(key);
map2.remove(lastIndex);
}
}
public K getRandom(){
if(size == 0){
return null;
}
int randomIndex = (int)(Math.random() * size);
return map2.get(randomIndex);
}
}
}
布隆過濾器
布隆過濾器(Bloom Filter)實(shí)際上是一個(gè)比特?cái)?shù)組习蓬。布隆過濾器可以用于檢測一個(gè)元素是否在一個(gè)集合中浪规，它的優(yōu)點(diǎn)是省空間找御，以及時(shí)間讨永，缺點(diǎn)是有誤差率揪漩。
布隆過濾器的應(yīng)用案例主要有：爬蟲去重，黑名單問題等塘娶，我們從黑名單問題開始認(rèn)識布隆過濾器
黑名單問題
現(xiàn)在有10億個(gè)URL黑名單根吁，每個(gè)URL固定為32字節(jié)
需要設(shè)計(jì)一種結(jié)構(gòu)衡瓶，當(dāng)一個(gè)URL傳過來時(shí)，判斷這個(gè)URL是否在黑名單中缩抡。
如果我們使用HashSet嘴高，可以做到準(zhǔn)確查詢以及查詢的時(shí)間復(fù)雜度為O(1),但是這樣一來哈希表在服務(wù)器內(nèi)存上的消耗將會是巨大的套啤，至少需要320億字節(jié)争占。
布隆過濾器則可以做到減少內(nèi)存壓力握童，快速查詢片效。
首先準(zhǔn)備一個(gè)足夠大的長度為M的int類型的數(shù)組
int[] arr = new int[M];
因?yàn)閕nt類型為4字節(jié)蛮浑，每個(gè)字節(jié)有8位，所以開辟的數(shù)組空間可以存放32M個(gè)bit《旱眨現(xiàn)在準(zhǔn)備K個(gè)哈希函數(shù)，對10億個(gè)URL依次求出hashcode并取模
那么如何判斷hashcode取模后落在bit數(shù)組上的位置呢商源？拿hash1()%M舉例车份，假設(shè)該值為code1
int intIndex = code1 / 32; // 在int數(shù)組上的哪一個(gè)位置
int bitIndex = code1 % 32; // 在對應(yīng)的int數(shù)組上的哪一個(gè)bit位
arr[intIndex] = (arr[intIndex] | (1 << bitIndex));
// 1 << bitIndex 即，除了bitIndex外的bit位都為0牡彻，通過和arr[intIndex]進(jìn)行或運(yùn)算后
// code1在bit數(shù)組上對應(yīng)的位置被“抹黑”（該位置值為1）
除了code1以外扫沼，其他的哈希函數(shù)也在32M長度的bit數(shù)組上分別"抹黑"了相應(yīng)的位置
十億個(gè)URL在K個(gè)哈希函數(shù)下出爹，標(biāo)記的位置變?yōu)?，首先要確定的是M要足夠大缎除，要不然可以試想一下严就，如果32M個(gè)位置幾乎全部抹黑，那么誤差率就會大大提升器罐，另外我們也可以解釋為什么布隆過濾器會產(chǎn)生誤差梢为，產(chǎn)生的誤差類型是有可能為不在黑名單的URL,但是碰巧算出的hashcode都為黑，這樣就會返回true,不過可以確定的是如果是在黑名單的URL那么返回值一定為true,其通過hash函數(shù)后落在bit數(shù)組上的位置必然均為1轰坊，布隆過濾器的誤差率可以形象地說是“寧可錯(cuò)殺一千铸董，絕不放過一人”。
不難看出肴沫，當(dāng)檢驗(yàn)的哈希函數(shù)的個(gè)數(shù)K增加粟害，誤差率必然下降；如果bit數(shù)組的長度增加颤芬，誤差率也必然下降悲幅。
布隆過濾器樣本量n,bit數(shù)組長度m,哈希函數(shù)個(gè)數(shù)k與失誤率p的關(guān)系
給定樣本量以及預(yù)期失誤率可以推斷出需要開辟多少bit長度的數(shù)組
計(jì)算出需要開辟多少bit長度的數(shù)組后，可以推斷出需要多少個(gè)hash函數(shù)
直到m以及k的取值后驻襟，可以重新計(jì)算失誤率夺艰。試想公式一推斷出的m值向上取值芋哭，那么m的數(shù)量增加沉衣，bit數(shù)組長度增加失誤率則會相應(yīng)減少；通過公式二推斷出k值也向上取值减牺，k的數(shù)量增加豌习，哈希函數(shù)校驗(yàn)的個(gè)數(shù)增加失誤率也會相應(yīng)地減少，所以得到的真實(shí)失誤率必然要比預(yù)期失誤率好拔疚。
布隆過濾器的重要應(yīng)用
參考文章:大白話布隆過濾器
一致性哈希
在hash應(yīng)用-海量數(shù)據(jù)分流一節(jié)中：
我們知道肥隆，當(dāng)發(fā)起大流量的請求時(shí)，后端的服務(wù)器負(fù)載均衡稚失，但是也有缺點(diǎn)栋艳，如果某臺服務(wù)器故障，或者需要新增加一臺服務(wù)器的時(shí)候句各，那么所有的請求元都要在重新計(jì)算自己分配到了哪一臺服務(wù)器上吸占。有沒有方法可以優(yōu)化這一點(diǎn)并且還能做到負(fù)載均衡呢？一致性哈希和虛擬節(jié)點(diǎn)技術(shù)就解決了這樣的問題凿宾。
一致性哈希
以MD5舉例矾屯，MD5的S域表示的范圍為[0,2^64],那么就假想一個(gè)環(huán)：
假設(shè)對每臺服務(wù)器的ip求hashcode后分布在環(huán)上的情況如下
某數(shù)據(jù)經(jīng)過前端的MD5哈希函數(shù)得到的數(shù)值必然落在環(huán)上，從落點(diǎn)開始順時(shí)針走初厚，最近的服務(wù)器則會被分流到件蚕。如果增加服務(wù)器或者減少服務(wù)器：
如圖所示，新增s4，那么原本在s3的黃色部分?jǐn)?shù)據(jù)就會轉(zhuǎn)到s4上排作，減少服務(wù)器也是同理牵啦，可見不需要太大的犧牲。
每一臺前端服務(wù)器記錄著排好序的后端服務(wù)器hash(ip),當(dāng)有新的數(shù)據(jù)需要分配到后端服務(wù)器妄痪，則在前端服務(wù)器上通過二分法找到大于等于新的數(shù)據(jù)的那個(gè)server蕾久，然后再進(jìn)行分配。
不過拌夏，這種環(huán)結(jié)構(gòu)卻犧牲了傳統(tǒng)哈希分流負(fù)載均衡的優(yōu)點(diǎn)僧著，虛擬節(jié)點(diǎn)則解決了這一問題
虛擬節(jié)點(diǎn)
還是有三臺服務(wù)器，不過現(xiàn)在為每個(gè)服務(wù)器配1000個(gè)虛擬節(jié)點(diǎn)障簿。虛擬節(jié)點(diǎn)負(fù)責(zé)"搶"數(shù)據(jù)盹愚。通過路由表可以知道哪一個(gè)服務(wù)器對應(yīng)著那些虛擬節(jié)點(diǎn)。因?yàn)檫@樣下來平均就是3000個(gè)虛擬節(jié)點(diǎn)站故，在整個(gè)S域上可以做到負(fù)載均衡皆怕，搶數(shù)據(jù)的原理和上面介紹的一樣，順時(shí)針走西篓，遇到最近的虛擬節(jié)點(diǎn)然后通過路由表看該虛擬節(jié)點(diǎn)對應(yīng)的是哪一個(gè)實(shí)體服務(wù)器愈腾，那么數(shù)據(jù)就被分配到哪個(gè)服務(wù)器上。
新增服務(wù)器或者是減少服務(wù)器也是一樣的岂津，如果新增服務(wù)器虱黄，那么就再原有虛擬節(jié)點(diǎn)的基礎(chǔ)上再次增加1000個(gè)虛擬節(jié)點(diǎn)，原本散布在別的服務(wù)器上的數(shù)據(jù)吮成，也會通過虛擬節(jié)點(diǎn)移至新的服務(wù)器上橱乱，這樣一來通過一致性哈希不僅可以做到新增或減少服務(wù)器不需要消耗巨大代價(jià)，也可以做到服務(wù)器之間負(fù)載均衡粱甫。
